Groupe d’études et de recherche en analyse des décisions

G-2016-63

Column generation for vehicle routing problems with multiple synchronization constraints

, , , , et

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 the 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 refueling 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 and can choose each vehicle for transport. Furthermore, each vehicle can carry several workers as well as the driver. 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.

, 23 pages