Minimierung des Fahrzeugbedarfs gleich Minimierung der Fixkosten



VS-OPT


Steckbrief

Bei der Umlaufplanung werden aus einem Fahrplan Umläufe gebildet. Der Fahrplan enthält die Informationen über die Fahrgastfahrten, ihre Start- und Endzeiten und ihren Beginn und ihre Zielorte. Die Umläufe geben vor, welches Fahrzeug welche Fahrgastfahrt bedient.

Die Qualität der Umlaufplanung beeinflusst die operativen Kosten von Verkehrsunternehmen erheblich, da ein guter Umlaufplan die Anzahl der Fahrzeuge, die Länge der Leerfahrten und die Verspätungsanfälligkeit optimiert. Wie bieten mit VS-OPT einen Umlaufoptimierer, der seit 1997 im Einsatz ist und permanent weiterentwickelt wird. Er ist der erste Optimierer, der auch größte Umlaufplanungsprobleme beweisbar optimal lösen konnte.

Problemstellung


Die Umlaufplanung ist ein Teilschritt der operativen Planung der Verkehrsbetriebe. Sie setzt auf dem Fahrplan auf, der in der vorgelagerten Fahrplanerstellung festgelegt wird. Der Fahrplan definiert die sog. Fahrgastfahrten, die im Fahrplanaushang den Kunden bekanntgegeben werden. In der Umlaufplanung werden diese Fahrgastfahrten mit Umläufen geeigneter Fahrzeuge unterlegt. Zur Bildung von Umläufen werden die Fahrgastfahrten mit Hilfe verschiedener Typen von Betriebsfahrten wie Ein- und Aussetzfahrten, Leerfahrten oder durch schlichtes Warten am Haltepunkt (ein besonderer Fall einer echten Leerfahrt) verknüpft. Die Wahl- der Ein- und Aussetzfahrten entscheidet auch über die Zuordnung von Fahrzeugen zu Betriebshöfen.

Bei der Bildung von Umläufen sind drei Typen von Regeln zu beachten. Es gibt erstens verschiedene Typen von Fahrzeugen, die sich nicht alle gleichermaßen für jede Fahrt eignen. Gründe wie Kapazitäten, Qualitätsstandards, Durchfahrtshöhen etc. können den Einsatz eines oder mehrerer Typen für eine Fahrt notwendig machen bzw. ausschließen. Zweitens sind bei der Verknüpfung von Fahrgastfahrten Mindestwendezeiten, Linienwechsel, Fahrtartwechsel etc. zu beachten. Drittens gibt es Kapazitätsgrenzen in den Betriebshöfen für den Einsatz von Fahrzeugen der verschiedenen Typen.

Das Hauptziel der Umlaufplanung ist meist die Minimierung des Fahrzeugbedarfs und damit eine Minimierung von Fixkosten. Nachgeordnet optimiert man gern variable Kosten in Form des Kilometerbedarfs oder des Zeitbedarfs, Stabilitätskriterien wie die Anzahl an Linienwechseln oder auch Kriterien einer vorweggenommenen Dienstplanung wie das Vorhandensein von pausenfähigen Zeiten etc.

Abbildung 1-Netzplan und Graphenmodell der Fahrgast- und Leerfahrten eines Fahrplans. Die z-Achse ist die Zeitachse

Abbildung 2-Fahrgastfahrten (schwarz) und potentielle Leerfahrten (grau) eines regionalen Busverkehrsbetriebes

Abbildung 3– vereinfachtes Graphenmodell des Umalufplanungsproblems

Methodik

Die Umlaufplanung ist ein kombinatorisches Problem, dass sich sehr gut zur mathematischen Optimierung eignet. Es lässt sich direkt in ein graphentheoretisches „Mehrgüterflussproblem“ übersetzen, das mit Mitteln der ganzzahligen Optimierung bearbeitet wird.

Den Ausgangspunkt der Modellierung bilden die Fahrgastfahrten und die sog. „Depots“, Gruppen als gleichartig angesehener Fahrzeuge (gleicher Typ, gleicher Betriebshof, etc.). Zu jeder Fahrgastfahrt gehört eine Gruppe zulässiger Depots, die diese Fahrt durchführen können. Fahrgastfahrten und Depots werden durch sämtliche möglichen Betriebsfahrten miteinander verknüpft. Auf diese Weise ergibt sich ein Planungsgraph, dessen Kanten und Depotgruppen die Freiheitsgrade der Planung darstellen. Umläufe entsprechen dort depotgruppenreinen Pfaden, die Zielkriterien der Umlaufplanung werden durch eine geeignete Gewichtung der Bögen implementiert. Die Umlaufplanung stellt sich damit dar als die Frage der Bestimmung einer kostenminimalen Menge von depotgruppenreinen Pfaden, so dass jede Fahrgastfahrt genau einmal überdeckt wird, ein sog. Mehrgüterflussproblem der kombinatorischen Optimierung.

Mehrgüterflussprobleme sind eine im Prinzip gut untersuchte Problemklasse. Die Hauptschwierigkeit bei der Anwendung entsprechender Methoden in der Umlaufplanung liegt in der riesigen Größe der Planungsgraphen, in denen 100 Millionen und mehr mögliche Betriebsfahrten (= Freiheitsgrade!) vorkommen können. Unser Ansatz realisiert ein neuartiges Lagrangean Pricing, um diese Graphen ohne heuristische Vereinfachungen zielgerichtet zu durchsuchen. Dabei werden in einem mathematisch präzisierbaren Sinne aussichtsreiche Fahrtenverknüpfungen mit Hilfe einer Minimalkostenfluss-Relaxierung „generiert“. Die immer wieder aktualisierte Menge dieser Verknüpfungen bearbeiten wir mit LP- und Lagrange-Verfahren zur Bestimmung von unteren Schranken und als Basis für eine spezielle Heuristik zur Auflösung von Depotkonflikten zur Bestimmung von ganzzahligen Lösungen.

Die Umlaufplanung ist ein kombinatorisches Problem, dass sich sehr gut zur mathematischen Optimierung eignet. Es lässt sich direkt in ein graphentheoretisches „Mehrgüterflussproblem“ übersetzen, das mit Mitteln der ganzzahligen Optimierung bearbeitet wird.

Den Ausgangspunkt der Modellierung bilden die Fahrgastfahrten und die sog. „Depots“, Gruppen als gleichartig angesehener Fahrzeuge (gleicher Typ, gleicher Betriebshof, etc.). Zu jeder Fahrgastfahrt gehört eine Gruppe zulässiger Depots, die diese Fahrt durchführen können. Fahrgastfahrten und Depots werden durch sämtliche möglichen Betriebsfahrten miteinander verknüpft. Auf diese Weise ergibt sich ein Planungsgraph, dessen Kanten und Depotgruppen die Freiheitsgrade der Planung darstellen. Umläufe entsprechen dort depotgruppenreinen Pfaden, die Zielkriterien der Umlaufplanung werden durch eine geeignete Gewichtung der Bögen implemntiert. Die Umlaufplanung stellt sich damit dar als die Frage der Bestimmung einer kostenminimalen Menge von depotgruppenreinen Pfaden, so dass jede Fahrgastfahrt genau einmal überdeckt wird, ein sog. Mehrgüterflussproblem der kombinatorischen Optimierung.

Mehrgüterflussprobleme sind eine im Prinzip gut untersuchte Problemklasse. Die Hauptschwierigkeit bei der Anwendung entsprechender Methoden in der Umlaufplanung liegt in der riesigen Größe der Planungsgraphen, in denen 100 Millionen und mehr mögliche Betriebsfahrten (= Freiheitsgrade!) vorkommen können. Unser Ansatz realisiert ein neuartiges Lagrangean Pricing, um diese Graphen ohne heuristische Vereinfachungen zielgerichtet zu durchsuchen. Dabei werden in einem mathematisch präzisierbaren Sinne aussichtsreiche Fahrtenverknüpfungen mit Hilfe einer Minimalkostenfluss-Relaxierung „generiert“. Die immer wieder aktualisierte Menge dieser Verknüpfungen bearbeiten wir mit LP- und Lagrange-Verfahren zur Bestimmung von unteren Schranken und als Basis für eine spezielle Heuristik zur Auflösung von Depotkonflikten zur Bestimmung von ganzzahligen Lösungen.

Praxis


VS-OPT ist nicht nur im Einsatz bei einigen Nahverkehrsunternehmen, es ist auch integraler Bestandteil unseres integrierten Umlauf- und Dienstplanungsoptimierers IS-OPT.
Optimierungsstudien mit VS-OPT sind dokumentiert für Daten der Berliner Verkehrsbetriebe (BVG), der Hamburger Hochbahn AG (HHA) und der Verkehrsbetriebe Hamburg Holstein (VHH) (siehe Löbel1997). Die dortigen Bus-Umlaufplanungs-Szenarien haben bis zu 28.000 Fahrgastfahrten, 10 Betriebshöfen, 14 Fahrzeugtypen, 100 Millionen Leerfahrten Seitdem wurde VS-OPT permanent weiterentwickelt. Die Laufzeiten betragen inzwischen nur noch ein Bruchteil derer von 1997, außerdem haben wir z.B. eine Sensitivitätsanalyse für Fahrpläne auf Basis von VS-OPT entwickelt. Bei dieser kann man je Fahrt vorgeben, wie weit sie verschoben werden darf. Anschließend wird mit VS-OPT ein Umlaufplan berechnet, der mit minimalen Verschiebungen von Fahrten versucht die Anzahl der Fahrzeuge zu verringern. Dies hat in Studien tatsächlich zu einer Reduktion von Fahrzeugen mit nur wenigen Verschiebungen von Fahrten geführt.
VS-OPT ist integriert in das Planungssystem IVU.run der IVU Traffic Technologies AG und bei zahlreichen Verkehrsbetrieben auf der ganzen Welt installiert. Außerdem ist die Netzwerksimplex-Komponente MCF von VS-OPT Teil der SPEC CPU2000, SPEC CPU2006 und SPEC CPU2017 Benchmark Testsuiten der Chip-Industrie.