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.

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


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.


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).