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.
Problem
Vehicle scheduling is a step in the operational planning process in public transport. Starting point is a timetable, which defines the so-called timetabled trips. The task of vehicle scheduling is to cover these trips with rotations of suitable vehicles. To build these rotations, the timetabled trips are linked by so-called deadhead trips, which come in several types, such as pull-out and pull-in trips from and to a depot, other unloaded trips, or just by waiting "trips" at a station. The choice of pull-out and pull-in trips decides, in particular, the assignment of vehicles to depots.
Vehicle scheduling is governed by three types of rules. First, there are different types of vehicles, and not every vehicle is suited for every trip: Capacity limits, quality requirements, or constraints such as limited headroom can force or forbid the use of a certain vehicle type for a trip. Second, minimum turning times, line change restrictions, and similar rules for connecting two timetabled trips have to be taken into account. Third, there are capacity restrictions for the availability of vehicles of various types at the depots.
The main goal of vehicle scheduling is fleet minimization, i.e., a minimization of fixed costs. Subordinate goals can be variable costs, stability criteria such as the number of line changes, or anticipated duty scheduling criteria such as the existence of time slots that can be used for breaks.
Method
Vehicle scheduling is a combinatorial problem that is well suited for mathematical optimization. It can be formulated as a multi-commodity flow problem and solved with integer programming techniques.
The starting point for a mathematical approach is a graph theoretic formulation of the problem in the form of a vehicle scheduling digraph. The nodes of this digraph are the timetabled trips and the depots. Timetabled trips and depots are connected by arcs that model the possible deadhead trips. Putting appropriate weights on these arcs allows to formulate all kinds of optimization objectives. In this graph, a vehicle rotation corresponds to a depot-consistent path. The vehicle scheduling problem translates into the question to find a set of depot-consistent paths that cover each timetabled trip once and only once. This problem is known as a multi-commodity flow problem of combinatorial optimization.
Multi-commodity flow problems are well studied. The main difficulty in applying the known results to vehicle scheduling problems arising in public transit is the enormous size of these instances. In fact, planning graphs involving tens of thousands of timetabled trips and 100 million and more deadhead trips (which are the degrees of freedom!) are not unusual. We have developped a novel Lagrangean pricing method in order to search these gigantic graphs (without resorting to heuristic simplifications). The principle is to identify, in a precise mathematical sense, promising deadhead trips by means of single-commodity flow relaxations. These deadheads, time and again updated, are analyzed with LP and Lagrange-Techniques to produce lower bounds as well as high quality solutions, which are derived using a special heuristic that resolves depot-conflicts in the relaxation.
In all practical instances that we have encountered, the lower and upper bounds on the fleet size coincide, i.e., practical vehicle scheduling problems of arbitrary size can be solved to proven fleet optimality. Also, the secondary optimization criteria are usually within 99% of the optimum.
Results
Our vehicle scheduling optimization tool VS-OPT is integrated into the commercial planning systems MICROBUS II of IVU Traffic Technologies AG and BERTA of the Berliner Verkehrsbetriebe (BVG) and commercially marketed. Further development and support is done by the ZIB spin-off company Löbel, Borndörfer & Weider GbR. The tool is in use in many public transport companies, among them Athens, Berlin, Bonn, Connex Germany, DB Regio, Genova, Milan, Munich, and Norgesbus.
The SWB Bonn report that the optimization of their production plan for 30/06/2001 with VS-OPT has resulted in savings of 5 out of 201 vehicles.
