Driver Routing and Scheduling with Synchronization Constraints

DOI10.1016/J.TRB.2023.05.009arXiv2207.06772WikidataQ122888098 ScholiaQ122888098MaRDI QIDQ6404960FDOQ6404960

Authors: Pia Ammann, Rainer Kolisch, Maximilian Schiffer 

Publication date: 14 July 2022

Abstract: This paper investigates a novel type of driver routing and scheduling problem motivated by a practical application in long-distance bus networks. A key difference from other crew scheduling problems is that drivers can be exchanged between buses en route. These exchanges may occur at arbitrary intermediate stops such that our problem requires additional synchronization constraints. We present a mathematical model for this problem that leverages a time-expanded multi-digraph and derive bounds for the total number of required drivers. Moreover, we develop a destructive-bound-enhanced matheuristic that converges to provably optimal solutions and apply it to a real-world case study for Flixbus, one of Europe's leading coach companies. We demonstrate that our matheuristic outperforms a standalone MIP implementation in terms of solution quality and computational time and improves current approaches used in practice by up to 56%. Our solution approach provides feasible solutions for all instances within seconds and solves instances with up to 390 locations and 70 requests optimally with an average computational time under 210 seconds. We further study the impact of driver exchanges on personnel costs and show that allowing for such exchanges leads to savings of up to 75%.

This page was built for publication: Driver Routing and Scheduling with Synchronization Constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6404960)