 Multiple depot vehicle scheduling with controlled trip shiftingLucie Desfontaines and Guy Desaulniers Transportation Research Part B: Methodological, 2018, vol. 113, issue C, 34-53 Abstract: 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. Keywords: Vehicle scheduling; Trip shifting; Timetable quality control; 2-Phase matheuristic; Column generation (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:transb:v:113:y:2018:i:c:p:34-53 Ordering information: This journal article can be ordered from DOI: 10.1016/j.trb.2018.05.011 Access Statistics for this article Transportation Research Part B: Methodological is currently edited by Fred Mannering More articles in Transportation Research Part B: Methodological from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.