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