A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit

Please always quote using this URN: urn:nbn:de:0297-zib-7898
  • This article proposes a Lagrangean relaxation approach to solve integrated duty and vehicle scheduling problems arising in public transport. The approach is based on the proximal bundle method for the solution of concave decomposable functions, which is adapted for the approximate evaluation of the vehicle and duty scheduling components. The primal and dual information generated by the bundle method is used to guide a branch-and-bound type algorithm. Computational results for large-scale real-world integrated vehicle and duty scheduling problems with up to 1,500 timetabled trips are reported. Compared with the results of a classical sequential approach and with reference solutions, integrated scheduling offers remarkable potentials in savings and drivers' satisfaction.

Download full text files

Export metadata

  • Export Bibtex

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Ralf Borndörfer, Andreas Löbel, Steffen Weider
Document Type:ZIB-Report
Tag:bundle method; crew scheduling ; integrated scheduling ; public transit ; vehicle scheduling
MSC-Classification:90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B20 Traffic problems
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C10 Integer programming
Date of first Publication:2004/05/03
Series (Serial Number):ZIB-Report (04-14)
Published in:Appeared in: Computer-aided Systems in Public Transport (CASPT 2005), M. Hickman et al. (eds.) 2008, pp. 3-24

$Rev: 13581 $