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

BMBF-VS: Vehicle Scheduling

Umlaufplanung im öffentlichen Nahverkehr

Beschreibung

 

Im öffentlichen Nahverkehr, im Bahn- und im Luftverkehr müssen vorgegebene Fahrpläne mit Fahrzeugumläufen unterlegt werden. Dazu stehen Fahrzeuge verschiedener Typen zur Verfügung, die an mehreren Depots stationiert sind. Bei der Bildung von Umläufen sind Regeln für den Einsatz der Fahrzeugtypen und für die Verknüpfung von Fahrten zu beachten, insbesondere für die Bildung von Leerfahrten und die Zuordnung von Fahrzeugen zu Depots. Das primäre Planungsziel ist in der Regel die Minimierung des Fahrzeugbedarfs, sekundär betrachtet man auch Kriterien für variable Kosten oder betriebliche Kriterien wie die Anzahl an Linienwechseln.

Das Ergebnis dieses Projektes ist ein Unlauf-Optimierungstool VS-OPT, das Umlaufplanungsprobleme mit Methoden der ganzzahligen Optimierung löst. Im algorithmischen Kern ist eine neuartige Lagrangean-Pricing-Technik umgesetzt, die die beweisbar flottenoptimale Lösungen auch größter Instanzen erlaubt. VS-OPT ist in industrielle Planungssysteme integriert (MICROBUS II und BERTA) und bei vielen Verkehrsbetrieben im In- und Ausland im Einsatz. Die Teilkomponente MCF ist im Quellcode erhältlich und für akademische Zwecke frei verwendbar.

Erhebliche Einsparungen durch VS-OPT sind dokumentiert.

  Weitere Informationen finden sich in der ausführlichen Projektbeschreibung.

Ansprechpartner

  Andreas Löbel

Mitarbeiter

  Martin Grötschel
Andreas Löbel

Partner

 

Finanzierung

  Bundesministerium für Bildung und Forschung (BMBF) Fördernummer 03-GR7ZIB-7

Dauer

  10/1994 - 09/1997