Optimierungs­prozesse die neue Maßstäbe setzen!



DS-OPT


Steckbrief

DS-OPT ist ein Optimierer für Dienstplanungsprobleme wie sie typischerweise im öffentlichen Verkehr bei der Planung von Fahrern und Begleitpersonal auftreten. DS-OPT ist seit 20 Jahren bei einer Vielzahl von Eisenbahn- und Busverkehrsbetrieben weltweit im Einsatz.

Bei der Dienstplanung geht es darum Tätigkeiten zu Tagesdiensten zusammenzufassen, die von einzelnen Mitarbeitern durchgeführt werden können. Diese Tagesdienste sind vielfältigen und komplizierten Regeln aus Gesetzen, Verordnungen, Tarifen und betrieblichen Vereinbarungen unterworfen. DS-OPT wurde bereits benutzt um Dienste für Busfahrer, Triebfahrzeugführer, Zugbegleiter und Schiffspersonal zu planen. Wir haben auch erfolgreiche Konzeptstudien durchgeführt um die Tauglichkeit von DS-OPT zur Planung von Fluglotsen, Flugabfertigern und Flugzeugbesatzungen nachzuweisen.
Das grundlegende Modell von DS-OPT ist ein Set-Covering/Partitioning-Modell, welches mit Column-Generation und Branch-And-Bound-Heuristiken gelöst wird. Unsere Methodik ist in Zusammenarbeit mit dem Zuse-Institut Berlin entwickelt worden und in einer Reihe von wissenschaftlichen Publikationen beschrieben. Die Stärke von DS-OPT ist jedoch die breite Palette von Anforderungen, die es abdeckt. Es wird von einer großen Zahl von unterschiedlichen Unternehmen benutzt, deren Anforderungen fast komplett in unser Standardprodukt eingegangen sind. Dabei kommen die Wünsche und Anforderungen eines Unternehmens allen zu gute, da es unser Ziel ist alle Anforderungen in DS-OPT zu integrieren und ihnen so einen breit einsetzbaren Optimierer anbieten zu können. Auf diese Weise haben wir einen einheitlichen Optimierungskern sowohl für kleine Busunternehmen mit 20 Busse bis hin zu großen städtischen Unternehmen wie die BVG, der gleichzeitig auch für Bahnunternehmen wie Deutsche Bahn und Trenitalia verwendbar ist.
DS-OPT ermöglicht nicht nur automatische Diensterstellung, oft sind auch signifikante Kosteneinsparungen damit realisiert worden. Die Stadtwerke Bonn z.B. haben 4,3% ihre Busdienste und 2,5% ihrer Straßenbahndienste einsparen können. Die Verkehrsbetriebe Ennepetal-Ruhr sogar 9,1% ihrer Bus-Dienste. Dabei werden aber auch die Belange der Fahrer berücksichtigt und z.B. die Anzahl der geteilten Dienste oder von songenannten Stressdiensten gering gehalten.
Ursprünglich entwickelt wurde DS-OPT in einem vom BMBF geförderten Forschungsvorhaben am Konrad-Zuse-Zentrum für Informationstechnik Berlin, die Weiterentwicklung wurde im Jahre 2000 von der Dres. Löbel, Borndörfer & Weider GbR übernommen und in 2017 an die LBW Optimization GmbH übergeben. Der Vertrieb erfolgt seit dem Jahre 2000 ausschließlich über die IVU Traffic Technologies AG in ihrem Planungssystem IVU.plan und seinem Bahnableger IVU.rail.

Problem­beschreibung


Die Dienstplanung im öffentlichen Verkehr ist eine Aufgabe der operativen Planung, die von den Verkehrsbetrieben im Allgemeinen in mehreren aufeinanderfolgenden Schritten durchgeführt wird: Auf die Netzplanung folgen nacheinander die Linien-, Fahr-, Fahrzeugumlauf-, Dienst-, Dienstreihenfolge- und schließlich die Personaleinsatzplanung.
Bei der Dienstplanung geht es darum, aus einer Menge von elementaren Arbeitseinheiten, den sogenannten Dienstelementen, (zunächst) anonyme Tagesdienste für einzelne Fahrer zu bilden, die zusammen einen Dienstplan bilden. Zu beachten sind gesetzliche, tarifliche und betriebliche Regeln für Zulässigkeit, monetäre und arbeitszeitliche Bewertung einzelner Dienste und des Plans als Ganzes, sowie die Synchronisation mit den vor- und nachgelagerten Schritten der Umlauf- und der Dienstreihenfolgeplanung. Der Planungshorizont ist typischerweise ein Betriebstag, das Hauptziel ist die Minimierung der Kosten, Nebenziele sind die Zufriedenheit der Fahrer und betriebliche Stabilität. Wir skizzieren im Folgenden grob das Problem der Dienstplanung im ÖPNV. Für eine detailliertere Darstellung verweisen wir auf BLSV1999 und die dort genannten Referenzen. Die Dienstplanung gliedert sich in vier Ebenen.

Vier Ebenen der Dienstplanung


Die unterste Ebene ist die der Dienstbestandteile, die einzelne Tätigkeiten des Fahrpersonals repräsentieren. Man unterscheidet Dienstelemente, Übergänge und Ergänzungselemente. Die Dienstelemente entsprechen z.B. Bus- oder U/S-Bahn-Fahrten und ergeben sich aus dem „Schneiden“ von Fahrzeugumläufen an Ablösepunkten, an denen ein Fahrerwechsel möglich ist. Zwei Dienstelemente werden durch einen Übergang miteinander verknüpft, wenn es (lokal) möglich ist, die Elemente in einem Dienst hintereinander durchzuführen.

Die Übergänge enthalten alle Informationen, die notwendig sind um die Pausen festzulegen, dazu gehören Wegezeiten, Pausenzeiten, Lage von Pausenorten, etc. und sind die wichtigsten Freiheitsgrade der Dienstplanung.
Anzahl und Ausgestaltung der Übergänge hängen stark vom Regelwerk ab. Ergänzungselemente sind ein dritter Typ von Dienstbestandteilen, der zur Modellierung von Vorbereitungs- und Abschlußarbeiten dient. Solche Arbeiten fallen am Beginn oder Ende von Diensten, Dienstteilen oder Dienststücken, also an bestimmten Stellen eines Dienstes, an.

Die zweite Ebene bilden die Dienste. Jeder Dienst muss den Regeln einer Dienstart entsprechen, in der mögliche Arbeitszeiten, Lenkzeiten, Pausenmodelle, Zuschläge und andere Parameter von Diensten festgelegt sind. Beispiele für typische Dienstarten sind „zusammenhängende Dienste“, „geteilte Dienste“, „Frühdienste“ oder „Kurzdienste“.
Auf der dritten Ebene des Dienstplans gibt es ebenfalls Regelungen, die vor allem den Dienstmix betreffen, d.h. das Verhältnis der verschiedenen Dienstarten zueinander.

Auf dieser Ebene kann z.B. festegelegt werden, dass es nur eine bestimmte Anzahl geteilter Dienste geben darf, oder dass des einen bestimmten Prozentsatz Frühdienste geben soll.

Die vierte Ebene betrifft die Integration der Dienstplanung in die Gesamtplanung. Hier ergeben sich Fragen der Abgrenzung der Planungsperiode, der Abstimmung mit den vor- und nachgelagerten Planungsschritten, der „Stabilität“ der Planung über die Woche und der Anpassung der Planung für Sonderfahrpläne, wg. z.B. Baustellen oder Großereignissen.

Abbildung 1 – Dienstplanunggraph mit Lösung.

Mathematische Methodik

Die mathematische Methodik der Dienstplanung spiegelt die vier Ebenen genau wider. Die Grundlage und erste Ebene bildet ein graphentheoretisches Modell des Dienstplanungsproblems.


In diesem Dienstplanungsgraphen bilden die Dienst- und Ergänzungselemente die Knoten, während die Kanten die möglichen Übergänge darstellen. Knoten und Kanten tragen die für die Dienstplanung relevanten Attribute wie Lenkzeit, Pausenzeit, Heimatbereich, Streßfaktor und viele andere mehr.
Die Dienste entsprechen auf der zweiten Ebene Pfaden im Dienstplanungsgraphen. Umgekehrt ist allerdings nicht jeder Pfad ein Dienst. Nur Pfade, die alle Regeln einer Dienstart einhalten, definieren zulässige Dienste.
Die Dienstplanung ist in dieser Terminologie ein Problem des Überdeckens von Knoten (der Dienstelement-Knoten) durch Pfade bestimmter Arten. Zu jedem Pfad gehört eine Bewertung, und gesucht ist eine Pfadüberdeckung mit minimalen Kosten. Zu beachten sind auf der Ebene des Dienstplanes dabei noch Anforderungen an den Mix von Pfaden verschiedener Typen.
Die Integration der Dienstplanung in die Gesamtplanung strebt man auf der vierten Ebene durch die Konstruktion geeigneter Dienstplanungsgraphen und Dienstarten sowie durch die Wahl geeigneter Zielfunktionen an.
Dieses graphentheoretische Modell bildet die Basis für die Algorithmen unseres Optimierungssytems. Die Lösung von Problemen der Pfadüberdeckung gehört zu den am besten untersuchten Fragen in der kombinatorischen Optimierung. Wir setzen auf Column-Generation Methoden, die auf Set-Partitioning und Set-Covering Modellen basieren. Mit solchen Verfahren werden große Erfolge bei allen Arten von Dienstplanungsproblemen erzielt: siehe z.B. BSSW2006, RLW2004 und W2007.

Praxis und Ausblick


DS-OPT ist erfolgreich bei vielen nationalen und internationalen Bus- und Bahnunternehmen im Einsatz. Zu Bahnunternehmen, die DS-OPT benutzen gehören z.B. BLS (Pressemitteilung) und Trenitalia (Pressemitteilung). Auch viele Nahverkehrsunternehmen wie die BVG und einige der deutschen S-Bahnen benutzen DS-OPT. Daneben gehören viele der kleineren und mittleren Nahverkehrsbetriebe in Deutschland zu unseren Kunden. DS-OPT wird ständig weiterentwickelt.
Einerseits fließen neue Anforderungen in das Produkt, andererseits arbeiten wir permanent an der Performance des Algorithmus. U.a. haben wir ein neuartiges Konzept zur Erstellung von Dienstplänen entwickelt, die ähnlich zu vorhanden Dienstplänen sind um Gleichförmigkeitsanforderungen erfüllen zu können (siehe BLLSW2012). Auch für Forschungszwecke, wie z.B. Integration von Dienst- und Dienstreihenfolgeoptimierung benutzen wir DS-OPT (siehe BDLSW2014).