-

 

 

 




Optimization Online





 

A Column Generation Algorithm for Vehicle Scheduling and Routing Problems

Tasnim Ibn Faiz( faiz.t***at***husky.neu.edu)
Chrysafis Vogiatzis and (cvogiatzis***at***ncat.edu)
Md. Noor-E-Alam(mnalam***at***neu.edu)

Abstract: 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.

Keywords: Humanitarian logistics, Truckload open vehicle routing problem with time windows, Column generation algorithm, Path generation algorithm.

Category 1: Applications -- OR and Management Sciences

Citation:

Download: [PDF]

Entry Submitted: 06/03/2018
Entry Accepted: 06/03/2018
Entry Last Modified: 06/03/2018

Modify/Update this entry


  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society