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.

• Berliner Verkehrsbetriebe (BVG)
• IVU Traffic Technologies AG
• HanseCom GmbH
• Löbel, Borndörfer & Weider GbR