A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit
| 04-14 | Ralf Borndörfer, Andreas Löbel, Steffen Weider
A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit | |
Abstract: 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.
Keywords: vehicle scheduling,
crew scheduling,
integrated scheduling,
public transit,
bundle method
MSC: 90B20, 90C10