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…

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.

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.