Column generation for vehicle routing problems with multiple synchronization constraints

Martin Fink, Guy Desaulniers, Markus Frey, Ferdinand Kiermaier, Rainer Kolisch, François Soumis

Research output: Contribution to journalArticlepeer-review

32 Scopus citations

Abstract

Synchronization of workers and vehicles plays a major role in many industries such as logistics, healthcare or airport ground handling. In this paper, we focus on operational ground handling planning and model it as an archetype of vehicle routing problems with multiple synchronization constraints, coined as “abstract vehicle routing problem with worker and vehicle synchronization” (AVRPWVS). The AVRPWVS deals with routing workers to ground handling jobs such as unloading baggage or refuelling an aircraft, while meeting each job's time window. Moreover, each job can be performed by a variable number of workers. As airports span vast distances and due to security regulations, workers use vehicles to travel between locations. Furthermore, each vehicle, moved by a driver, can carry several workers. We propose two mathematical multi-commodity flow formulations based on time-space networks to efficiently model five synchronization types including movement and load synchronization. Moreover, we develop a branch-and-price heuristic that employs both conventional variable branching and a novel variable fixing strategy. We demonstrate that the procedure achieves results close to the optimal solution in short time when compared to the two integer models.

Original languageEnglish
Pages (from-to)699-711
Number of pages13
JournalEuropean Journal of Operational Research
Volume272
Issue number2
DOIs
StatePublished - 16 Jan 2019

Keywords

  • Branch-and-price
  • Column generation
  • Multiple synchronization constraints
  • Variable fixing
  • Vehicle routing

Fingerprint

Dive into the research topics of 'Column generation for vehicle routing problems with multiple synchronization constraints'. Together they form a unique fingerprint.

Cite this