ZIB-Logo
KONRAD-ZUSE-ZENTRUM
FÜR INFORMATIONSTECHNIK
BERLIN

BMBF-VS: Vehicle Scheduling

Vehicle Scheduling in Public Transit

Description

 

In public transport, in rail and air traffic vehicle rotations must be constructed on the basis of a given timetable. Usually, the vehicles are of several types or sizes and they are stationed at a number of depots. Furthermore, there are rules for the construction of rotations for these vehicles, must notably for the feasibility of deadhead trips and the assignment of vehicles to depots. The main goal in vehicle scheduling is to minimize the fleet size, secondary goals are to minimize variable costs or operational criteria such as the number of line hops.

The result of the project is an optimization tool VS-OPT that solves vehicle scheduling problems using integer programming techniques. The algorithmic core implements a novel Lagrangean pricing technique that allows to solve even largest instances to proven fleet optimality. VS-OPT is available in industrial scheduling systems (MICROBUS II and BERTA) and in use in many public transport companies throughout the world. A part of VS-OPT, the min-cost flow solver MCF can be downloaded; it can be freely used for academic purposes.

Signifcant cost reductions by VS-OPT are documented.

  Further information is available in the detailed project description.

Contact

  Andreas Löbel

Members

  Martin Grötschel
Andreas Löbel

Partners

 

Funding

  German Federal Ministery for Education and Research (BMBF) Grant 03-GR7ZIB-7

Duration

  10/1994 - 09/1997