  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 at arbitrary intermediate stops en route 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 reduces the number of required drivers by up to 56% compared to
approaches currently used in practice. 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 sec. We further study the impact of driver exchanges on the total driver
count and show that allowing for such exchanges leads to average savings of
42.69%.
