Pia Ammann (TUM, AdONE): "Driver Routing and Scheduling in Long-Distance Bus Networks"
The liberalization of the European long-distance bus market caused a rapid growth in demand for intercity coach travel, resulting in a competition between numerous private coach companies. In this highly competitive environment a company only survives if it manages to keep operational cost at a minimum level via efficient operations. In this context, driver wages continue to be a major cost share. Accordingly, efficient scheduling and routing that allows to keep the number of drivers as low as possible remains a crucial planning task. Similar problems have already been addressed for airline crew scheduling, railway timetabling, truck driver scheduling, and urban bus services, but research on driver scheduling in long-distance bus networks is still scarce. While our problem resembles a truck driver scheduling problem, it bears several additional characteristics, e.g., drivers may be exchanged between buses en routes. Indeed, these exchanges may also take place at arbitrary intermediate stops such that our problem contains additional synchronization constraints. Against this background, we study the driver routing and scheduling problem for long-distance bus networks. We discuss a mathematical problem formulation based on a time-expanded multi-digraph and derive lower and upper bounds for the total number of drivers required. Moreover, we develop an exact algorithmic framework that allows to solve small- and medium-sized instances. We apply this framework to a real-world case study for one of Europe's leading coach companies and present first experimental results.
This is ongoing work with Rainer Kolisch and Maximilian Schiffer.
Date: Monday 25th of May 2020, starting at 2 p.m.
The seminar will take place online.