Planungs­horizonte erweitern mit Dienstreihen­folgeplanung



DR-OPT


Steckbrief

DR-OPT ist ein Optimierer zum Berechnen von Dienstreihenfolgen für Personale. Bei der Dienstreihenfolgeplanung werden vorhandene (Tages-)Dienste zu Dienstreihenfolgen kombiniert, die entweder zyklisch sind oder sich über einen Planungshorizont von mehreren Wochen erstrecken können…

DR-OPT kann für stationäre Personale genauso verwendet werden wie für Fahrpersonale oder andere Personale, deren Startort nicht unbedingt mit dem Endort eines Dienstes übereinstimmen muss. Wir haben außerdem prototypisch eine vollintegrierte Dienst- und Dienstreihenfolgeplanungsoptimierung implementiert (siehe BSSW2017). DR-OPT wurde für mehrere Studien verwendet und zeigte dabei, dass es möglich ist die Qualität der Dienstreihenfolgeplanung in Verkehrsbetrieben zu verbessern, ohne dass zusätzliche Kosten entstehen.

Beschreibung


Die Dienst- und Dienstreihenfolgeplanung sind die beiden Teilschritte des Planungsprozesses im öffentlichen Nahverkehr, die den Personaleinsatz bestimmen. In der Dienstreihenfolgeplanung werden aus Diensten mehrwöchentliche sogenannte Dienstreihenfolgen zusammengestellt, d.h. Abfolgen von Diensten und freien Tagen über einen bestimmten Zeitraum. Wie die Tagesdienste müssen auch die Dienstreihenfolgen einem umfangreichen Regelwerk genügen. In Deutschland sind die wichtigsten Bestimmungen die des Arbeitszeitgesetzes.

Ein weiterer wichtiger Punkt bei der Dienstreihenfolgeplanung ist der Ausgleich zwischen der Kostenminimierung (z.B. durch Vermeidung von Überstunden oder bezahlter Minderarbeit) und der Maximierung der Fahrerzufriedenheit , die sich in besonderem Maße an der Dienstreihenfolge fest macht. Idealerweise soll eine Dienstreihenfolge bestimmt werden, die die Fahrerzufriedenheit maximiert ohne wesentliche Zusatzkosten zu verursachen.

DR-OPT erzeugt einen Dienstreihenfolgeplan über einen bestimmten Planungshorizont (z.B. 4 oder 8 Wochen) in dem die Tagesdienste und eine vorher festgelegte Anzahl von Reservediensten abstrakten Personalen zugeordnet werden. Alternativ kann DR-OPT auch einen zyklischen Dienstreihenfolgenplan, ein sogenanntes Wochenschema, erzeugen. Ein Dienstreihenfolgeplan wird typischerweise tabellarisch dargestellt, in jeder Zeile werden die Dienste für ein Personal für den Planungszeitraum dargestellt, daher entspricht die Anzahl der Zeilen auch der Anzahl der Personale, die benötigt werden.

Die Personale sind abstrakt, da weder ihre Vergangenheit in Form von aufgelaufenen Arbeitszeitkontoständen, noch ihre Qualifikationen oder ihre Abwesenheitszeiten berücksichtigt werden. Den Zeilen eines Dienstreihenfolgeplans müssen im nächsten Planungsschritt, der Personaldisposition, konkreten Personalen zugeordnet werden.
DR-OPT basiert auf Set-Partitioning Modellen, die mit verschiedenen Primal-Heuristiken, u.a. mit der DEX-Heuristik, gelöst werden. Für Details siehe BRSSSW2015.

In DR-OPT haben wir bisher erfolgreich die Regeln und Ziele von Eisenbahnunternehmen, Regionalbusunternehmen, einer deutschen Bundesbehörde und von einem Service-Unternehmen eines Flughafens abgebildet. Z.B. können wir in DR-OPT Regeln über tägliche Ruhezeiten und wöchentliche Ruhezeiten, wie sie in der EU-Verordnung 561/2006 über Lenk- und Ruhezeiten und der “Deutschen Fahrpersonalverordnung” vom 22.1.2008 beschrieben sind, berücksichtigen. Im wesentlichen bedeutet das, dass zwischen zwei Fahrdiensten mindestens 11 Stunden Ruhezeit liegen müssen. Außerdem muss in jeder Woche mindestens einmal eine zusammenhängenden Ruhezeit von 48 Stunden enthalten sein. Diese darf auf 24 Stunden verkürzt werden, muss dann aber in einem bestimmten Zeitraum ausgeglichen werden. Diese Werte sind hier exemplarisch genannt, im Einzelfall können sie natürlich vom Planer flexible konfiguriert werden. Typische Regeln betreffen die Verteilung von freien Tagen, Reservediensten, Dienstanfangszeiten im Laufe einer Woche, durchschnitttlichen Arbeitszeiten und maximalen Arbeitszeiten.
Optimierungsziele von DR-OPT sind u.a. die Anzahl der Personale zu verringern, je Woche möglichst wenig von der vorgegebenen durchschnittlichen bezahlten Zeit abzuweichen oder die freien Wochenenden gleichmäßig zu verteilen.
In der Praxis treten unterschiedliche Varianten der Dienstreihenfolgeplanung auf, so kann z.B. in einem Zwischenschritt die Folge der freien Tage festgelegt werden, bevor Dienste den Zeilen zugeordnet werden. Es können auch Abfolgen von Dienstlagen (z.B. Früh- oder Spätdienste) festgelegt werden, bevor die Dienstreihenfolgen gebildet werden. In einer anderen Variante wird der Dienstreihenfolgeplan zyklisch gebildet, das heißt, dass jeder Fahrer sequentiell die Dienste aller Zeilen durchführt. Dadurch haben alle Fahrer, nachdem sie einmal den gesamten Plan durchlaufen haben, dieselben Dienste in derselben Reihenfolge durchlaufen, was als gerecht empfunden wird. Außerdem ist dies eine kompakte Darstellung der Dienstreihenfolge.

Dienstreihenfolge für Kontrolldienste


In einem aktuellen Projekt (siehe BSSS2016) haben wir DR-OPT mit einem System zum Bilden von Kontrolldiensten kombiniert. Dadurch wird es möglich gleichzeitig integriert Dienste für Kontrollteams zu bilden und diese in einer Dienstreihenfolge einzureihen. Mit den Kontrolldiensten müssen dabei nicht wie in DS-OPT festgelegte Tätigkeiten verplant werden, sondern aus einer Menge von zu kontrollierenden Ereignissen einige ausgesucht werden, die sich einerseits sinnvoll zu Diensten verplanen lassen, andererseits Anforderungen an die Kontrollquoten erfüllen. Zu kontrollierende Ereignisse können dabei z.B. Fahrgastfahrten sein auf denen Fahrscheine kontrolliert werden sollen. Es können aber auch bestimmte Fahrstrecken zu einem bestimmte Zeitpunkt sein, wenn an oder auf diesen Strecken etwas kontrolliert werden soll.
Die Kontrolldienste unterliegen hier ähnlich vielfältigen gesetzlichen und betrieblichen Einschränkungen wie die oben beschriebenen Tagesdienste. Zusätzlich gibt es zugelassene Kontrollbereiche für bestimmte Personale. Wir verwenden ein Multi-Commodity-Flow-Modell mit zusätzlichen Nebenbedingungen, um die Kontrolldienste und die Dienstreihenfolgeplanung zu integrieren. Das gesamte Spektrum der ganzzahligen Programmiermethoden von Spaltengenerierung, Schnittebenenverfahren, Branch-and-Bound bis hin zu unterschiedlichen Primalheuristiken wird genutzt.
In Zusammenarbeit mit dem Zuse Institute Berlin entwickeln und betreuen wir seit 2014 einen integrierten Kontrolldienst- und Dienstreihenfolge-Algorithmus, der seit 2014 im Bundesamt für Güterverkehr eingesetzt wird, um monatliche Dienstreihenfolgen für mehr als 200 Fahrzeuge und 400 Kontrolleure zu generieren. Die optimierten Kontrolldienste und Dienstreihenfolgen garantieren eine netzweite Kontrolle, und berücksichtigen dabei auch die zeitliche und räumliche Verteilung des zu kontrollierenden Verkehrs, um die begrenzte Anzahl von Kontrollkräften auf effiziente Weise einzusetzen.