Multiple depot vehicle scheduling with controlled trip shifting

The multiple depot vehicle scheduling problem (MDVSP) has been widely studied in the context of public transit systems. Given a timetable of bus trips, it consists of finding a set of bus schedules that covers every trip exactly once while satisfying vehicle availability at each depot and minimizing the operating costs. This work considers a generalization of the MDVSP that allows slight modifications of the trip scheduled start times. By shifting some trips, one can indeed expect to cover all trips with fewer vehicles or less expensive deadheads (vehicle moves without passengers). However, reducing the operational costs in this way should not be too detrimental to the overall quality of the timetable and, therefore, the following criteria should be controlled: the number of shifted trips, the headways between the consecutive trips of a line, and the quality of some passenger connections. To solve this generalized problem, we develop a two-phase matheuristic: the first phase computes vehicle schedules with a column-generation heuristic; the second relies on a mixed integer program to find the best possible timetable considering the computed vehicle schedules. Penalties are introduced in the first phase to increase the chances of finding a better-quality timetable in the second phase. Computational tests on real-life datasets from a bus company show that the proposed matheuristic can solve the problem efficiently, yielding solutions with a significant reduction in the number of vehicles used compared to the solutions of the classical MDVSP and a limited alteration of the timetable.