A column generation algorithm for vehicle scheduling and routing problems. (April 2019)

• Record Type: Journal Article
• Authors: Faiz, Tasnim Ibn; Vogiatzis, Chrysafis; Noor-E-Alam, Md.
• Is Part Of: Computers & industrial engineering. Volume 130(2019)
• Page Start: 222
• Page End: 236
• Publication Date: 2019-04
• Subjects: Humanitarian logistics -- Truckload -- Open vehicle routing problem -- Time windows -- Column generation -- Path generation algorithm; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2019.02.032
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: Two models for vehicle scheduling and routing problems are presented. A column generation based solution algorithm is designed. Efficient path generation algorithms are designed. The column generation based algorithm outperforms the exact method. Abstract: In this paper, we consider a variant of a truckload open vehicle routing problem with time windows, which is suitable for modeling vehicle routing operations during a humanitarian crisis. We present two integer linear programming models to formulate the problem. The first one is an arc-based mixed integer linear programming model that can be solved using a general purpose solver. For the second formulation, we first devise a task adjacency graph, that we use to develop a path-based integer linear program. We then propose a column generation framework to solve large-scale instances. Finally, we perform numerical experiments to compare the performance of the two models. Our computational results show that the path-based formulation solved using our proposed column generation framework outperforms the arc-based mixed integer linear program in solution time, without sacrificing solution quality.