During natural or anthropogenic disasters, humanitarian organizations (HO) are faced with the time sensitive task of sending critical resources from multiple depots to the affected areas that can be scattered across a region. This responsibility includes the quick acquisition of vehicles from the local market and the preparation of pickup and delivery schedules and vehicle routes. During crises, the supply of vehicle is often limited, their acquisition cost is steep, and acquired vehicles are restricted by rental periods. Moreover, the affected areas suffer from a dire need for aid materials and they must be reached within due time. Therefore, it is imperative that the decisions of acquiring, scheduling, and routing of vehicles are made optimally and quickly. In this paper, we consider a variant of a truckload open vehicle routing problem with time windows which exhibits vehicle routing operations characteristics in a humanitarian crisis. We present two integer linear programming models to formulate the problem. The first model is an arc-based mixed integer linear programming model. The second model is a path-based integer linear programming model; we design two fast path generation algorithms to formulate this model. The first model is solved exactly using the commercial solver, while we design a column generation algorithm to solve the second model. We compare the results obtained from the two models and show that the path-based model with column generation algorithm outperforms the arc-based model when solved exactly in terms of solution time without sacrificing the solution quality.
Article
View A Column Generation Algorithm for Vehicle Scheduling and Routing Problems