A column generation algorithm for vehicle scheduling and routing problems

Tasnim Ibn Faiz, Chrysafis Vogiatzis, Md Noor-E-Alam

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)222-236
Number of pages15
JournalComputers and Industrial Engineering
StatePublished - Apr 2019
Externally publishedYes


  • Column generation
  • Humanitarian logistics
  • Open vehicle routing problem
  • Path generation algorithm
  • Time windows
  • Truckload

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)


Dive into the research topics of 'A column generation algorithm for vehicle scheduling and routing problems'. Together they form a unique fingerprint.

Cite this