Optimierung

ZIB  →  Diskrete Methoden  →  Optimierung  →  Projekte  →  Verkehr und Logistik  →  BMBF-IS: Integrated Vehicle and Duty Scheduling

BMBF-IS: Integrated Vehicle and Duty Scheduling

Integrierte Umlauf- und Dienstplanung im Öffentlichen Nahverkehr

Die gleichzeitige Planung von Fahrzeugen und Fahrpersonalen im Nahverkehr ist der Gegenstand der integrierten Planung. Diese Art der Planung ist vor allem im Regionalbusverkehr wichtig, denn dort sind durch fehlende Ablösemöglichkeiten Fahrer und Fahrzeug in der Fläche aneinander gebunden. Mit traditioneller aufeinanderfolgender Planung (erst Fahrzeuge, dann Personale oder umgekehrt) kann man diese besondere Problematik nicht gut bewältigen.

Das Ergebnis dieses Projektes ist ein Optimierungssystem zur integrierten Planung, das auf Set-Partitioning/Covering- und Mehrgüterflussmodellen basiert. Da es beim derzeitigen Stand der Technik nicht möglich ist, solche Probleme optimal zu lösen, zielen wir auf Lagrange-Verfahren zur näherungsweisen Lösung.

Bei der Entwicklung und der anschließenden praktischen Umsetzung dieser Verfahren arbeiten die Softwarehäuser IVU Traffic Technologies AG, Berlin, und Mentz Datenverarbeitung GmbH, München, mit. Als "Lead User" nimmt die Regengsburger Verkehrsverbund GmbH an dem Projekt teil.

Planungsgraph

Problem

Vehicle scheduling and duty scheduling are important steps in the operational planning process of a public transport company. Today, many companies are solving these problems sequentially, often with a vehicles-first duties-second approach. In scenarios with few relief opportunities, however, sequential scheduling can run into severe difficulties in scheduling mandatory breaks for the drivers. Many public transport companies safeguard against such problems by inserting artificial idle periods into their vehicle schedules which later serve as break opportunities. In addition, they look after vehicle schedules that regularly visit a relief point or a depot. While such a procedure may result in feasible schedules, its drawback is that the vehicle schedules often contain more idle periods than actually needed. Integrated vehicle and duty scheduling exploits this potential.

Method

Our approach to integrated vehicle and duty scheduling is based on an integrated model of the problem that combines a vehicle and a duty scheduling model by a coupling part that synchronizes the use of deadhead trips. The objective of the optimization can be an arbitrary mix of vehicle and duty costs.

The optimization algorithm decomposes the problem into its vehicle and duty scheduling part by relaxing the coupling constraints in a Lagrangean fashion. This results in a sequence of vehicle and a duty scheduling subproblems, which are solved using methods that we have developped in preceding projects on vehicle scheduling and duty scheduling. The Lagrange relaxation provides not only a lower bound for the costs of an optimal integrated schedule. Using a bundle approach to handle the relaxed coupling constraints, we can also produce an approximate primal LP solution. We use this information in a branch-and-bound-type heuristic in order to derive synchronized and cost efficient vehicle and duty schedules.

Results

We have tested our method on industrial large-scale scenarios provided by the Regensburger Verkehrsverbund GmbH (RVV). The RVV is an urban public transport company with a star-shaped network. There are only four relief points in the center of the network, all close to the railway station, which is itself close to the depot. Such a structure is typical for a situation which is ill-suited for sequential planning.

On weekdays, the RVV does 1,414 timetabled trips, consisting of 3,666 duty elements. The duty elements are connected by 233,842 potential connections, among them 57,646 potential deadhead trips. The duty scheduling rules include quotient as well as block breaks; in addition, constraints on average duty durations had to be taken into account. As far as we known, these RVV instances are the largest and most complex instances of integrated vehicle and duty scheduling problems that have been considered up to now.

In comparison to the reference solution provided by the RVV, our optimization tool IS-OPT could reduce the number of duties by 2-3%, the total working time by 5%, and the time spent by vehicles outside of the depot by 4%.

Our integrated vehicle and duty scheduling optimization module IS-OPT is integrated into the commercial planning system MICROBUS II of IVU Traffic Technologies AG and commercially marketed. Further development and support is done by the ZIB spin-off company Löbel, Borndörfer & Weider GbR.

Related Projects

Publications