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.

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