Kurzfassung

Die Erstellung von Personaleinsatzplänen ist ein zentraler Planungsschritt in Verkehrsunternehmen und entscheidet maßgeblich über die Produktivität und die Mitarbeiterzufriedenheit. Häufig wird ein zyklisches Wochenschema erstellt, das dann in einem Kalenderzeitraum für mehrere Mitarbeiter ausgerollt wird. Die Erstellung ist eine anspruchsvolle und zeitintensive Aufgabe, denn es müssen viele verschiedene Randbedingungen berücksichtigt werden, wie z.B. das geltende Arbeitszeitgesetz, betriebliche Regelungen, Fairness und Produktivität. In diesem Artikel stellen wir ein Optimierungsverfahren basierend auf Simulated Annealing vor, mit dem Wochenschemata automatisch optimiert werden können. Das Verfahren ist in den Produkten der IVU Traffic Technologies AG für die Personaldisposition implementiert und bei vielen Verkehrsbetrieben erfolgreich im Einsatz.

Der Fachvortrag zur Veranstaltung ist im Volltext verfügbar. Das PDF enthält alle Bilder und Formeln.

1 Einleitung

Um profitabel zu wirtschaften, versuchen Verkehrsunternehmen heutzutage in allen Bereichen produktiv und effizient zu arbeiten. Im Kontext der Personaleinsatzplanung und -disposition erfordert das einerseits die Erstellung von Dienstplänen, die die Arbeitszeit des vorhandenen Personals optimal nutzen, aber auch die Tätigkeit der Erstellung selbst soll zeit- und kostensparend erfolgen. Der Fachkräftemangel hat zudem den Fokus auf Mitarbeiterzufriedenheit gelegt, der durch faire Dienstpläne und die Erfüllung von Wünschen Rechnung getragen wird. Diese Anforderungen sind bei größeren Verkehrsbetrieben heutzutage nur noch mit Hilfe von Softwarewerkzeugen zu erfüllen. Die IVU Traffic Technologies AG [1] bietet für die Dienstreihenfolgeplanung und Personaldisposition das Produkt IVU.crew als Teil der IVU.suite an.

In IVU.crew ist ein Einsatzplan definiert durch eine Auswahl von Diensten und eine feste Anzahl von Planzeilen, denen konkrete Mitarbeiter zugeordnet sind. Als Dienstreihenfolge wird die Zuteilung von aufeinanderfolgenden Diensten, freien Tagen und Bereitschaftszeiten zu einer Planzeile bzw. einem Mitarbeiter bezeichnet. Erfolgt diese Zuteilung für einen konkreten Zeitraum im Kalender, ist das Ergebnis ein Personaleinsatzplan.

Dienstreihenfolgen können auch unabhängig von einem konkreten Kalenderzeitraum in einem Schema festgelegt werden. In IVU.crew wird ein solches Schema als Wochenschema bezeichnet, da es für eine Regelwoche erstellt wird. Wenn ein Wochenschema in einem Einsatzplan für einen Kalenderzeitraum ausgerollt wird, dann werden in jeder Kalenderwoche die Zeilen des Schemas von verschiedenen Mitarbeitern geleistet, und jeder Mitarbeiter leistet die Abfolge aller Zeilen nacheinander über den Kalenderzeitraum hinweg. Eine genauere Beschreibung für das Ausrollen eines Wochenschemas findet sich in [2].

Die Verwendung von Wochenschemata hat in Verkehrsunternehmen eine lange Tradition und wird auch als rollierende Schichtplanung bezeichnet. Da alle Mitarbeiter eines Einsatzplanes dieselbe Dienstreihenfolge zeitversetzt zugeteilt bekommen, wird über einen längeren Zeitraum ein gewisser Grad an Fairness erreicht, z.B. in Bezug auf ungünstige Arbeitszeiten, unbeliebte Dienste, Wochenarbeitszeit und freie Wochenenden. Bei sehr großen Wochenschemata mit sehr vielen Zeilen stellt sich die Fairness allerdings erst nach einem sehr langen Kalenderzeitraum ein. Daher ist es wichtig, auch die Zeilen des Wochenschemas schon vergleichbar attraktiv zu gestalten [3]. Dadurch wird auch vermieden, dass sich in der Dienstreihenfolge eines Mitarbeiters sehr unattraktive Wochen mit sehr leicht zu bewältigenden abwechseln. Zu den Bedingungen für die zulässige Reihenfolge von Diensten, freien Tagen, u.a. kommen also noch weitere Randbedingungen hinzu, die ein Planer bei der manuellen Erstellung eines Wochenschemas beachten muss. Daher ist eine automatische algorithmische Optimierung eines Wochenschemas mit Hilfe eines Softwarewerkzeugs eine große Unterstützung.

Ausgerollte Wochenschemata führen zu regelmäßigen, vorhersehbaren Dienstplänen, sie sind aber zu unflexibel, um auch individuelle Abwesenheiten wie Urlaub oder Krankheit zu berücksichtigen. Daher versuchen einzelne Unternehmen, die Dienstpläne für längere Kalenderzeiträume direkt für die konkreten Mitarbeiter zu erstellen, was praktisch nur mit Hilfe von Optimierungsalgorithmen in angemessener Zeit möglich ist. Für diesen Zweck bietet das Modul IVU.crew die Automatische Personaldisposition an, die bereits seit über 10 Jahren bei vielen Verkehrsbetrieben in verschiedenen Ländern produktiv im Einsatz ist.

Auflagen, die sich aus dem Arbeitszeitgesetz des jeweiligen Landes ergeben, sowie betriebliche Vorgaben und Vereinbarungen mit der Belegschaft, sind in der Praxis häufig sehr komplex und individuell unterschiedlich für verschiedene Verkehrsunternehmen. In IVU.crew gibt es daher die Möglichkeit, mit einer ausdrucksstarken und flexiblen Regelsprache derartige Bedingungen zu formulieren und in das System einzugeben, die dann sowohl bei der manuellen Personaldisposition geprüft werden als auch von dem im Folgenden vorgestellten Optimierungsverfahren berücksichtigt werden.

Der Artikel gliedert sich wie folgt. Zunächst wird die Regelsprache für die Formulierung von Vorgaben und Bedingungen kurz vorgestellt, denn die Ausdruckskraft und Flexibilität der Regelsprache war ein Grund für den Einsatz der Metaheuristik Simulated Annealing anstatt eines mathematischen Optimierungsverfahrens oder eines Constraint Programming (CP) Solvers. Im Folgenden wird dann das implementierte Verfahren grundlegend beschrieben für den Fall der Optimierung azyklischer Personaleinsatzpläne. Im Anschluss wird dargestellt, wie dasselbe Verfahren erweitert wurde, um auch für die Optimierung zyklischer Wochenschemata eingesetzt werden zu können. Schließlich werden einige Beispiele für den erfolgreichen Einsatz der IVU.crew-Optimierungen in der Praxis beschrieben.

2 Dienstreihenfolgeregeln

Die Dienstreihenfolgen, die dem Fahrpersonal und anderen Mitarbeitern eines Verkehrsunternehmens zugeteilt werden, müssen vielfältige Anforderungen und Bedingungen erfüllen, insbesondere die Regelungen des nationalen Arbeitszeitgesetzes, Regelungen aus Tarifverträgen und innerbetriebliche Vereinbarungen. Da diese Bedingungen in verschiedenen Ländern und Verkehrsbetrieben unterschiedlich sind, ist es in IVU.crew möglich, dass diese von den Anwendern eingegeben werden können. So können die Programme zur Personaleinsatzplanung und Disposition flexibel auf verschiedene landes- und betriebsspezifische Regelungen angepasst werden. Die wesentlichen Bestandteile der Regelsprache sind

• Formeln für die Berechnung elementarer und abgeleiteter Eigenschaften der zugeteilten Tätigkeiten und der Mitarbeiter,
• Bedingungen für die zulässigen Wertebereiche der berechneten Werte und logische Verknüpfungen davon,
• sowie ein Zeitraumkonzept, das es ermöglicht, die Eigenschaften von zugeteilten Tätigkeiten an verschiedenen Tagen in Beziehung zu setzen.

Zudem gibt es noch die Möglichkeit der bedingten Formelauswertung mit sogenannten Wenn-Dann-Formeln, abhängig von dem Ergebnis einer Bedingung.

Eine Dienstreihenfolgeregel wird spezifiziert für einen bestimmten Zeitraumtyp wie z. B. 1 Tag, 3 Wochen, oder 2 Monate. Geprüft wird eine solche Regel dann auf allen konkreten Zeiträumen im Kalender, die zum Zeitraumtyp passen. Eine große Stärke der Regelsprache ist die Möglichkeit, den betrachteten Zeitraum bei der Prüfung von Teilformeln und Teilbedingungen zu verschieben, zu erweitern oder einzuschränken, wofür wiederum Bedingungen verwendet werden können.

Konkrete Beispiele aus der Praxis beschränken sich nicht auf einfache Dienstreihenfolgeprüfungen wie der Ruhezeit zwischen zwei aufeinanderfolgenden Diensten oder der Einhaltung der maximalen wöchentlichen Arbeitszeit. Insbesondere die exakte Abbildung von nationalen Arbeitszeitgesetzen und die Abbildung von Vorgaben aus aktuellen Tarifverträgen führten in der Vergangenheit schon zu sehr komplexen Regeln, deren hierarchische Baumstruktur aus Dutzenden von Teilformeln und Teilbedingungen bestehen, und in denen der betrachtete Zeitraum häufig verschoben und geändert wird. Konkrete Beispiele sind

• ETV §11 (2) Die freien Tage sind so zu verteilen, dass innerhalb eines Vierteljahres mindestens 13 freie Tage liegen, von denen drei auf einen Sonntag fallen müssen.
• BuRa-ZugTV 3 Abschnitt 2 (4): Nach einer Arbeitsphase, die länger als 120 Stunden dauert oder in der mehr als 40 Stunden Arbeitszeit in Schichten angerechnet wurde, muss ein Ruhetag mit einer Mindestlänge von 48 Stunden folgen.

Allgemein ist die Regelsprache durch die rekursive Beziehung zwischen Formeln, Bedingungen und Zeitraumverschiebungen und durch die große Anzahl verwendbarer arithmetischer Operatoren so ausdrucksstark, dass leicht nicht-lineare Bedingungen durch die Anwender eingegeben werden können. Eine automatische Übersetzung aller möglichen von Anwendern formulierbaren Dienstreihenfolgeregeln in ein System linearer Ungleichungen oder in Constraints einer proprietären Modellierungssprache erschien daher schon bald aussichtslos. Durch die Implementierung der Metaheuristik Simulated Annealing in der Programmiersprache C++ konnten aber letztendlich alle möglichen Dienstreihenfolgeregeln abgebildet werden.

3 Optimierungsziele

Zielorientierte Optimierungsverfahren erfordern die Definition einer Kostenfunktion, in der sich eines oder mehrere Optimierungsziele widerspiegeln [4].

Klassischerweise berechnet die Kostenfunktion einen einzelnen skalaren Wert für eine (mögliche) Lösung des Optimierungsproblems. Gibt es mehrere Optimierungsziele, bezüglich derer eine Lösung unterschiedlich bewertet werden kann, was zu verschiedenen Kostenwerten führt, dann werden diese Kostenwerte üblicherweise gewichtet addiert, um einen einzelnen Gesamtkostenwert zu erhalten. Die Bestimmung der Gewichtungsfaktoren gestaltet sich in der Praxis oft schwierig. Es müssen die Wertebereiche der verschiedenen Kennzahlen skaliert und die Kostenwerte dadurch normiert werden, und gleichzeitig möchte man durch die Gewichtungsfaktoren eine Priorisierung der Optimierungsziele festlegen. Während der Optimierung ist dann nicht mehr leicht nachvollziehbar, durch welche Optimierungsziele der Verlauf der Berechnung maßgeblich beeinflusst wird. In manchen Fällen ist auch nicht a priori klar, welches Optimierungsziel wichtiger ist. In diesem Fall berechnet man üblicherweise mehrere sich gegenseitig nicht dominierende Lösungen auf der Pareto-Front und überlässt es am Ende dem Anwender, daraus eine Lösung auszuwählen [5].

Wenn doch eine eindeutige Priorisierung a priori möglich ist, aber die Definition bzw. Anpassung der Gewichtungsfaktoren für jedes konkrete Optimierungsszenario nicht praktikabel ist, kann man auch mit einem Kostenvektor arbeiten. Die Kostenfunktion liefert dann nicht einen einzelnen skalaren Wert, sondern einen Vektor von Kennzahlen, und zwei Kostenvektoren werden lexikographisch verglichen, um zu entscheiden welcher kleiner bzw. größer ist. Dieser Ansatz wurde für das in diesem Artikel vorgestellte Verfahren gewählt und hat sich in der Praxis bewährt. Anwender können die Kostenfunktion definieren, indem sie Optimierungsziele auswählen und auf verschiedenen Ebenen von 0 bis N mit abnehmender Priorität einstellen. Zusätzlich können bei Bedarf auf einer Ebene mehrere Optimierungsziele eingeordnet und gewichtet aggregiert werden.

Das wichtigste Optimierungsziel bei der Dienstreihenfolgeoptimierung ist fast immer die Erfüllung einer Menge von ausgewählten Dienstreihenfolgeregeln. Die Regeln, die in einer Lösung des Optimierungsproblems auf keinen Fall verletzt werden sollen, müssen dann exklusiv auf Ebene 0 angeordnet werden. Neben dem Ziel „Regeln erfüllen“ gibt es eine Reihe weiterer Optimierungsziele, die in der Praxis benötigt werden, um nicht nur einen rechtlich zulässigen Dienstplan zu erhalten, sondern auch einen fairen und für die Mitarbeiterzufriedenheit „guten“ Plan, der gleichzeitig die vorhandenen Ressourcen optimal nutzt und die Produktivität maximiert. Die wichtigsten Optimierungsziele sind: möglichst alle Dienste zuteilen, die Arbeitszeitkonten ausgleichen, Ansprüche erfüllen, die Gleichverteilung z. B. unliebsamer Dienste oder freier Wochenenden über alle Mitarbeiter erreichen, sowie die Wünsche der Mitarbeiter möglichst erfüllen.

Das implementierte Verfahren versucht stets, die von der Kostenfunktion berechneten Kosten zu minimieren. Optimierungsziele, wie z. B. „möglichst viele Dienste zuteilen“, die man auch als Ziel der Maximierung einer Kennzahl ansehen könnte, werden übersetzt in inverse Ziele, deren Kosten minimiert werden sollen, wie z.B. „möglichst wenige Dienste offenlassen“.

4 Modellierung des Optimierungsproblems

Die Metaheuristik Simulated Annealing ist eine Form der Lokalen Suche [6], bei der immer wieder von einer möglichen Lösung zu einer benachbarten Lösung im Lösungsraum gegangen wird, um schließlich eine zulässige Lösung mit optimalen Kosten zu finden.

4.1 Matrixrepräsentation

Eine Lösung für das Problem der Optimierung von Personaleinsatzplänen ist die Festlegung der Zuteilung von Diensten, Frei-Zuteilungen, Bereitschaftszeiten u. a. zu den Planzeilen oder Mitarbeitern an allen Tagen im betrachteten Zeitraum. Diese Zuteilung wird im hier vorgestellten Verfahren als Matrix repräsentiert, in der die Zeilen die Planzeilen bzw. Mitarbeiter repräsentieren und die Spalten die Tage. Ein zugeteilter Dienst wird an dem Tag in der Matrix eingetragen, an dem er beginnt. Ein Dienst kann aber am Folgetag enden.

Die Einschränkung, dass in jeder Zelle der Matrix nur genau ein Eintrag gemacht werden kann und dadurch nur ein Dienst pro Tag zugeteilt werden kann, hat sich in der Praxis nicht als gravierend erwiesen, denn es gibt für Ausnahmefälle die Möglichkeit, dass zwei sehr kurze Dienste an einem Tag zu einem Paar kombiniert und stets zusammen zugeteilt werden. Zudem können in IVU.plan auch sogenannte geteilte Dienste gebildet werden, die eine zweigeteilte Schicht mit längerer Unterbrechung darstellen, aber als ein Dienst zugeteilt werden können.

4.2 Constraints

Harte Constraints, die von keiner (Zwischen-)Lösung verletzt werden dürfen, gibt es nur zwei, und sie sind durch die Datenstruktur und die möglichen Übergänge zu benachbarten Lösungen implizit gegeben. Ein Dienst kann nur an dem Tag in der Matrix eingetragen sein, an dem er grundsätzlich zuteilbar ist. Ein Dienst kann nicht am selben Tag mehreren Planzeilen bzw. Mitarbeitern gleichzeitig zugeteilt sein. Das gilt auch für andere zuteilbare Tätigkeiten.

Die Bedingung, dass sich zwei auf derselben Zeile zugeteilte Dienste nicht zeitlich überschneiden dürfen, weil eine Person nicht zwei Tätigkeiten gleichzeitig ausführen kann, ist schon kein hartes Constraint mehr. Diese muss von den Anwendern als Regel formuliert und in einem Optimierungsziel gefordert werden, um Überschneidungen zu vermeiden.

Dienstreihenfolgeregeln und andere Optimierungsziele werden im implementierten Verfahren in Constraints im Sinne von [6] übersetzt. Jedes Constraint berechnet Kosten, die entsprechend der Gewichtung der Optimierungsziele in der Kostenfunktion aggregiert und auf der entsprechenden Ebene des Kostenvektors eingetragen werden. Auch die bestmögliche Lösung kann für die Dienstreihenfolgeprüfung Kosten größer Null haben, wenn sich z.B. Dienstreihenfolgeregeln widersprechen. Das ist ein großer Vorteil des vorgestellten Verfahrens, denn es gibt de facto keine unlösbaren Instanzen des Optimierungsproblems in Bezug auf harte Constraints.

Das Ergebnis der Übersetzung von Optimierungszielen in Constraints sind Objekte in der verwendeten Programmiersprache  C++. Jedes Constraint-Objekt ist für die Überprüfung bzw. Bewertung der Lösung bezüglich (eines Teils) eines Optimierungsziels zuständig. Constraints werten abhängig von ihrer Aufgabe unterschiedliche Teilbereiche der Lösungsmatrix aus. Constraints für die Prüfung von Dienstreihenfolgeregeln werten Zuteilungen in einem begrenzten Zeitraum auf nur einer Zeile aus, während ein Constraint für die Arbeitszeitkontenoptimierung die gesamte Mitarbeiterzeile betrachten muss. Ein Constraint für die Gleichverteilung muss sogar alle Zeilen im gesamten Zeitraum betrachten.

5 Optimierungsverfahren und Parameter

In diesem Abschnitt werden konkrete Entwurfsentscheidungen bei der Implementierung der Metaheuristik Simulated Annealing sowie die gewählten Parameter für das Verfahren beschrieben. Grundlegende Aspekte wurden bereits auf dem Workshop on Innovative Scheduling and other Applications der CPAIOR 2011 vorgestellt [7].

5.1 Simulated Annealing

Simulated Annealing (SA) ist ein seit einigen Jahrzehnten etabliertes Optimierungsverfahren, das insbesondere auch für die Lösung großer Probleminstanzen diskreter, kombinatorischer Optimierungsprobleme mit nicht-linearen Constraints eingesetzt werden kann. Ursprünglich vorgestellt wurde der Ansatz in [8] für Optimierungsprobleme mit skalarer Kostenfunktion. Später wurde in [9] der Beweis erbracht, dass das Verfahren bei korrekter Wahl zentraler Parameter gegen das globale Optimum konvergiert, obwohl während der Suche im Lösungsraum zufällige Entscheidungen getroffen werden.

Die Metaheuristik ist eine Form der lokalen Suche und lässt sich vereinfacht wie folgt zusammenfassen: Ausgehend von einer Startlösung wird der Lösungsraum durchsucht, indem eine leicht abgewandelte Lösung durch eine inkrementelle Änderung erzeugt und bewertet wird. Die möglichen inkrementellen Änderungsoperationen definieren implizit die direkte Nachbarschaft einer Lösung. Die angewendete Änderungsoperation wird zufällig ausgewählt. Hat die benachbarte Lösung geringere oder gleiche Kosten im Vergleich zur bisherigen Lösung, so wird diese akzeptiert und ist der Ausgangspunkt für die nächste Iteration. Hat die benachbarte Lösung höhere Kosten, so wird diese mit einer gewissen Wahrscheinlichkeit trotzdem akzeptiert, um dadurch möglicherweise aus lokalen Optima zu entkommen. Die Wahrscheinlichkeit für die Akzeptanz einer schlechteren Lösung ist abhängig vom Kostendelta bzgl. der Ausgangslösung und von einem als „Temperatur“ bezeichneten Parameter. Formal notiert ist die Wahrscheinlichkeit für Kostenneu>Kostenalt:

Formel 1: Wahrscheinlichkeit der Akzeptanz einer schlechteren Lösung

Je größer die Kostendifferenz und damit die Verschlechterung, umso unwahrscheinlicher ist die Akzeptanz der geänderten Lösung. Umso höher die Temperatur, desto wahrscheinlicher ist sie. Die Idee des Verfahrens basiert auf dem Prozess des Ausglühens (Annealing) in der Stahlproduktion, in dem die Temperatur langsam gesenkt wird, um den energetisch optimalen Endzustand zu erreichen. Auch im Optimierungsverfahren sinkt die Temperatur langsam, so dass die Akzeptanz von schlechteren Lösungen immer unwahrscheinlicher wird. Der Beweis der Konvergenz in [9] fordert vor allem, dass die Temperatur langsam genug verringert wird.

Es gibt auch verschiedene Ansätze, Simulated Annealing für die Multikriterielle Optimierung einzusetzen, bei der nicht a priori festgelegt wird, welches Optimierungsziel wichtiger ist, sondern mehrere sich gegenseitig nicht dominierende Lösungen auf der sogenannten Pareto-Front berechnet werden. In diesen Fällen liefert die Kostenfunktion einen Kostenvektor, und es wird ein Maß für die Differenz zweier Kostenvektoren benötigt, um die in Formel 1 definierte Wahrscheinlichkeit berechnen zu können, z. B. die Distanz zur Pareto-Front [5].

5.2 Startlösung

Als Startlösung für die lokale Suche kann eine leere Einsatzplanmatrix verwendet werden, oder es kann eine rudimentäre Zuteilung mit einer Greedy Heuristik erzeugt werden. Ist eines der Optimierungsziele, Änderungen am bestehenden Plan möglichst zu minimieren, dann startet man üblicherweise mit den bestehenden Zuteilungen, damit die Heuristik den bisherigen Zuteilungsstand nicht erst rekonstruieren muss.

5.3 Änderungsoperationen und Nachbarschaft

Für den Übergang von einer Lösung zu einer benachbarten Lösung im Lösungsraum gibt es mehrere verschiedene Änderungsoperationen. Diese werden in der englischsprachigen Literatur auch Moves genannt, wie Züge in der Spieltheorie. Die im vorgestellten Verfahren implementierten Moves sind in Bild 1 anschaulich dargestellt.

Ein bislang nicht zugeteilter Dienst kann zugeteilt werden oder eine bestehende Zuteilung kann aufgelöst werden. Zuteilungen von Diensten u. a. am selben Tag können zwischen zwei oder mehr Zeilen getauscht werden. Eine bestehende Zuteilung kann direkt mit einem nicht zugeteilten Dienst getauscht werden. Als Änderungsoperation auf einer Zeile gibt es die Möglichkeit, die Art der Zuteilung an zwei oder mehreren Tagen zu vertauschen. Schließlich können die meisten Moves optional auf zwei aufeinanderfolgende Tage erweitert werden, was nicht deterministisch, sondern mit einer konfigurierbaren Wahrscheinlichkeit erfolgt. Diese Option hat sich vor allem im Cargo-Umfeld als hilfreich erweisen, weil viele Dienste sich über zwei Tage erstrecken.

Bild 1: Mögliche Änderungsoperationen (Moves)

Die Auswahl eines Moves erfolgt zufällig basierend auf mehreren voneinander abhängigen Zufallsentscheidungen. Dafür wird ein Mersenne-Twister als Pseudozufallszahlengenerator verwendet. Der Startwert, der sogenannte Seed, ist fest vorgegeben, so dass ein Optimierungslauf trotz Zufallsentscheidungen exakt reproduziert werden kann, was für die Fehleranalyse im Customer Service unerlässlich ist.

5.4 Akzeptanzkriterium

Die Kostenvektoren zweier benachbarter Lösungen werden lexikographisch verglichen. Das ist möglich, weil a priori festgelegt ist, welche Kostenfunktionskomponenten/Optimierungsziele wichtiger sind als andere. Somit kann leicht entschieden werden, ob die Kosten einer neuen Lösung, die sich aus der Anwendung eines Move ergibt, besser oder schlechter ist als die aktuelle. Für die Akzeptanz einer schlechteren Lösung entsprechend der Formel 1 müsste dann aber die Energiedifferenz zweier Lösungen, d. h. ihrer Kostenvektoren bestimmt werden können. Dieses Problem wurde im vorgestellten Verfahren mit einem pragmatischen Ansatz umgangen: Auf der ersten Ebene, auf der die Kosten der neuen Lösung größer sind (bei gleichen Kosten auf allen höheren Ebenen), wird das Akzeptanzkriterium aus Formel 1 auf die skalaren Kosten auf dieser Ebene angewendet und entscheidet über die Akzeptanz der neuen Lösung. Das Problem der unterschiedlichen Wertebereiche auf den Ebenen der Kostenfunktion wird durch eine Normierung der Kostendifferenzen bzgl. Ebene 0 adressiert.

Für diesen Ansatz haben wir in der Literatur bislang keine Entsprechungen gefunden. Leider können wir bisher keinen formalen Beweis angeben, der die Konvergenz des Verfahrens zum globalen Optimum sicherstellt. Wir können allerdings auf viele Jahre des erfolgreichen Einsatzes im produktiven Betrieb verweisen.

5.5 Priorisierung

Die Metaheuristik Simulated Annealing sieht vor, dass in jeder Iteration zufällig eine Lösung aus der direkten Nachbarschaft der aktuellen Lösung gewählt wird. Dabei wird implizit davon ausgegangen, dass alle Moves zu benachbarten Lösungen gleich wahrscheinlich sind. Diese gleichverteilt randomisierte Art der lokalen Suche hat sich aber in der Praxis als zu wenig zielgerichtet herausgestellt. Daher sind im vorgestellten Verfahren mehrere Mechanismen zur Priorisierung von Moves implementiert. Die Auswahl erfolgt immer noch zufällig, aber nicht gleichverteilt.

Bei der Auswahl eines Moves müssen insbesondere die Zellen der Matrix ausgewählt werden, die geändert werden sollen. Die Intuition hinter der Priorisierung ist, das mit höherer Wahrscheinlichkeit solche Zellen gewählt werden, die am meisten zu Kosten beitragen.

Constraints für Dienstreihenfolgeregeln beziehen sich auf einen oder mehrere Tage. Ist die Regel nicht erfüllt, dann trägt das Constraint für alle Tage jeweils denselben konstanten Wert zu den aggregierten Kosten bei: Kosten von 1 ggf. multipliziert mit dem Gewichtungsfaktor des Optimierungsziels. Constraints, die eine ganze Zeile oder die ganze Matrix betreffen, liefern sofern möglich nicht nur einen Kostenwert, sondern sie liefern zusätzlich ein sogenanntes Kostenprofil, das für jede Zelle des betrachteten Zeitraums angibt, wieviel Kosten die jeweilige Zelle zum Gesamtkostenwert beiträgt. So können auch „globale“ Constraints, die einen größeren Bereich der Matrix abdecken, einen differenzierten Beitrag zur Priorisierung der Zellen der Matrix liefern.

Es gibt einen Parameter für die Wahrscheinlichkeit, ob bei der Auswahl eines Moves überhaupt die Prioritäten berücksichtigt werden sollen, oder ob ausnahmsweise eine völlig gleichverteilte Zufallsentscheidung getroffen werden soll. Denn obwohl die Priorisierung das Verfahren zielgerichteter Verbesserungen an den Zwischenlösungen vornehmen lässt, würde es dem eigentlichen Ansatz der Metaheuristik Simulated Annealing widersprechen, wenn immer priorisiert mit Bias gewählt würde. Insbesondere würden Zellen mit Kosten von Null dann de facto gar nicht mehr geändert. Daher ist der gelegentliche bzw. mit der priorisierten Auswahl abwechselnde sogenannte „fair choice“ ein effektiver Kompromiss, der sich in der Praxis bewährt hat.

5.6 Kühlschema

Für die erfolgreiche Suche nach dem globalen Optimum bzw. möglichst guten lokalen Optima mit Simulated Annealing ist die initiale Temperatur entscheidend sowie ihre schrittweise Verringerung im Laufe des Verfahrens. Vereinfacht ausgedrückt bleibt das Verfahren sehr früh in lokalen Optima „gefangen“ und entkommt diesen nicht mehr, wenn die Temperatur zu schnell verringert wird. Startet das Verfahren mit einer hohen Temperatur und wird diese lange kaum verringert, dann wird die Suche im Lösungsraum de facto zufällig und chaotisch, weil schlechtere Lösungen fast genauso häufig akzeptiert werden wie bessere.

Im hier vorgestellten Verfahren wird die Temperatur in regelmäßigen Abständen abhängig von der Anzahl der Iterationen reduziert. Eine Iteration ist die Bewertung einer benachbarten Lösung, die akzeptiert oder verworfen werden kann. Mehrere Iterationen werden in sogenannten Runden zusammengefasst. Nach jeder Runde erfolgt die Entscheidung, ob und wie sehr die Temperatur reduziert werden soll. Die Anzahl der Iterationen pro Runde ist abhängig von der Problemgröße: Ein konfigurierbarer konstanter Faktor wird multipliziert mit der Größe der zu optimierenden Matrix. Das ist notwendig, weil z.B. für die Optimierung des Jahresplans einer dreistelligen Anzahl Mitarbeiter viel mehr Änderungsoperationen erforderlich sind, um zu einer signifikanten Verbesserung der Lösung zu kommen, als bei der Optimierung eines kleinen Wochenschemas mit nur 10 Zeilen.

Die Verringerung der Temperatur kann in der implementierten Optimierung auf zwei Arten erfolgen: geometrisch oder linear, wobei sich das lineare Kühlschema in der Praxis als zu unflexibel erwiesen hat. Beim geometrischen Kühlschema wird die aktuelle Temperatur am Ende einer Runde mit einem konstanten Faktor < 1 multipliziert. Es können unterschiedliche Faktoren konfiguriert werden für Runden mit und ohne Verbesserung der Zwischenlösung. Nach einer Runde ohne Verbesserung (sogenannte futile round) wird die Temperatur üblicherweise stärker reduziert, weil sich die Suche bereits in einem lokalen Optimum befindet.

Das geometrische Kühlschema ermöglicht es, darauf zu reagieren, wenn sich die Suche in einem lokalen Optimum verfängt. Dann kann die Temperatur auch vorübergehend wieder erhöht werden, um mehr schlechtere Lösungen zu akzeptieren. Dieses so genannte Reheating erfolgt automatisch – sofern die Option gewählt ist – nach einer konfigurierten Anzahl aufeinanderfolgender Runden, die nicht zu einer Verbesserung geführt haben und eine zu geringe Akzeptanzrate für geänderte Zwischenlösungen hatten. Nach einer konfigurierbaren festen Anzahl an Reheating-Phasen wird dann schließlich die Suche abgebrochen.

Die Standardwerte für die Reduktion der Temperatur führen vermutlich in den meisten Fällen zu einer zu schnellen Abkühlung, um eine Konvergenz gegen das globale Optimum zu gewährleisten, so dass das implementierte Verfahren auch als Simulated Quenching (SQ) [10] bezeichnet werden könnte. Eine ausreichend langsame Abkühlung würde zu unpraktikabel langen Laufzeiten führen. Die Qualität der gefundenen Lösungen war aber bislang immer zufriedenstellend.

Für die in diesem und den vorherigen Abschnitten erwähnten Konfigurationsparametern gibt es Standardwerte, die bei der initialen Produktentwicklung durch empirische Studien mit schwierigen Optimierungsszenarien ermittelt wurden. Diese Werte mussten in der Praxis kaum angepasst werden, als das Verfahren nach und nach bei den Kunden der IVU Traffic Technologies AG in vielen verschiedenen Kontexten eingesetzt wurde.

5.7 Random Sampling

Das Verfahren kann so konfiguriert werden, dass nach längerer ausbleibender Verbesserung, mit oder ohne Reheating-Phasen, ein vollständiger Restart der Optimierung mit einer anderen Startlösung erfolgt, so wird die Optimierung de facto mehrmals nacheinander ausgeführt. Die unterschiedliche Startlösung und in der Folge andere Zufallsentscheidungen führen dazu, dass ein anderer Teil des Lösungsraums durchsucht wird. Auf diese Weise kann eine noch bessere Lösung gefunden werden. Man kann dieses Verfahren als Random Sampling des Lösungsraums bezeichnen, da an zufällig gewählten Orten mit der Suche begonnen wird.

Auf heutigen Multicore-Prozessoren müssen die verschiedenen Optimierungsläufe nicht mehr nacheinander ausgeführt werden, sondern können parallel erfolgen. Das hat auch den Vorteil, dass die nächste Optimierung nicht erst dann starten kann, wenn die vorherige einen Zustand erreicht hat, in dem schon seit einigen Runden keine Verbesserung mehr erfolgte. Stattdessen können alle parallel laufenden Optimierungen von den Anwendern beobachtet werden und eine bereits genügend gute Zwischenlösung akzeptiert werden. Denn das implementierte Verfahren ist ein Anytime-Algorithmus, der jederzeit unterbrochen werden kann und der dann die bis dahin global beste Lösung ausgibt. Werden mehrere Optimierungen für ein Problem ausgeführt, wird vom System die beste Lösung aller Optimierungen dem Anwender präsentiert.

6 Erweiterung auf zyklische Wochenschemata

Bei der Erstellung von Wochenschemata müssen wie bei der Erstellung von Personaleinsatzplänen die Dienstreihenfolgeregeln geprüft werden. Auch wenn ein Wochenschema nur eine Woche lang ist, kann es doch mehrere Dutzend Zeilen enthalten, und die Zyklizität des Schemas erschwert das Problem, eine zulässige Dienstreihenfolge zu erstellen, zusätzlich. Auch für ein Optimierungsverfahren stellt der Zyklus eine besondere Herausforderung dar, weshalb auch in verwandten Arbeiten für die zyklische Dienstreihenfolgeoptimierung Heuristiken statt exakter mathematischer Methoden verwendet werden [2]. Daher wurde das in den vorangegangenen Abschnitten beschriebene heuristische Verfahren für die Optimierung azyklischer Personaleinsatzpläne auf den Fall zyklischer Wochenschemata erweitert.

Ein zyklisches Wochenschema enthält keine Zuteilungen vor und nach der einen Woche. Gleichzeitig sollen aber die Zeilen des Schemas aneinandergereiht eine zulässige Dienstreihenfolge ergeben, da das Schema auf diese Weise in einem Dienstplan ausgerollt wird. Die Idee hinter der Erweiterung des Verfahrens auf zyklische Wochenschemata war daher, das Ausrollen während der Optimierung virtuell auszuführen, und die Zuteilungen an den Tagen vor und nach der Woche des Schemas bei jeder Änderung im Schema direkt zu aktualisieren. So konnten viele Datenstrukturen und Algorithmen für die Implementierung der Constraints unverändert übernommen werden. Technisch gesehen werden Anfragen der Constraints bezüglich der Zuteilungen außerhalb des Schemas auf die entsprechenden Zellen innerhalb des Schemas umgeleitet.

Ein Constraint für eine Dienstreihenfolgeregel, welche einen Zeitraum von mehreren Tagen prüft, von denen einige bereits außerhalb der Woche des Schemas liegen, wertet dann an diesen Tagen die entsprechenden Zuteilungen innerhalb der Woche auf einer der folgenden Zeilen des Schemas aus. Das ist in Bild 2 anschaulich dargestellt.

Bild 2: Constraints in virtuell ausgerolltem Wochenschema

Die ausgegrauten Tage sind nicht Teil des Wochenschemas, sondern dessen virtuelle Fortsetzung. Es sind beispielhaft Dienste für Frühschicht (FS), Spätschicht (SS) und Nachtschicht (NS) im Schema zugeteilt. Die schmalen Balken, die sich über 5 Tage erstrecken, illustrieren exemplarisch Constraints für Dienstreihenfolgeregeln, die an diesen Tagen geprüft werden. Das Constraint, das die fünf Tage bis zu Tag 3 nach der Woche des Schemas bewertet, erhält die Information über die Zuteilung der Frühschicht (FS) aus der nächsten Zeile des Schemas.

Eine Move, der eine Zuteilung innerhalb des Schemas ändert, ändert implizit auch die virtuelle Zuteilung auf einer oder mehrerer anderer Zeilen außerhalb der Woche des Schemas. Wenn im Beispiel die Frühschicht an Tag 3 zugeteilt wird, ändert sich auch die virtuelle Zuteilung in der vorherigen Zeile. Von einem Move, der eine Zuteilung auf einer Zeile ändert, können also nicht nur Constraints auf derselben Zeile betroffen sein, sondern es müssen ggf. auch Constraints auf anderen Zeilen aktualisiert werden. Umgekehrt müssen die Kosten eines Constraints auch bei den aggregierten Kosten für die Priorisierung der Zellen auf anderen Zeilen berücksichtigt werden. Im Beispiel kämen in Zeile 4 an den Tagen 1-3 Kosten für die Priorisierung der Zellen hinzu, wenn o.g. Constraint nicht erfüllt ist.

Die in der Abbildung angedeuteten Constraints in Zeile 4 werden im Fall der Optimierung eines zyklischen Schemas im Gegensatz zum azyklischen Fall nicht instanziiert, denn diese sind äquivalent und redundant zu den entsprechenden Constraints in Zeile 3. Zeilenweise Constraints werden stets nur für die Zeiträume instanziiert, die in der Woche des Wochenschemas beginnen. Das Verfahren würde zwar auch mit redundanten Constraints korrekt funktionieren, aber die mehrfache Berechnung derselben fachlichen Bedingungen verlängert nur unnötig die Rechenzeit und wurde daher vermieden.

Bei der Optimierung von Personaleinsatzplänen können mehrere Einsatzpläne gleichzeitig zusammen für denselben Zeitraum optimiert werden, so dass ggf. auch die Dienste eines Einsatzplans den Mitarbeitern eines anderen Einsatzplans zugeteilt werden können. Auch für die Optimierung von Wochenschemata kam diese Anforderung bald hinzu. Daher wurde das Verfahren so erweitert, dass auch mehrere Wochenschemata zusammen mit gemeinsamer Dienstmasse optimiert werden können, wobei die Optimierung entscheidet, welche Dienste in welchen Wochenschemata zugeteilt werden. In diesem Fall enthält die Matrix des Optimierungsproblems dann mehrere Zyklen und die virtuelle Ausrollung erfolgt für jedes Schema separat. Auch diese Erweiterung konnte einfach umgesetzt werden, und wurde bereits erfolgreich eingesetzt.

7 Einsatz in der Praxis

Die Optimierung von Personaleinsatzplänen ist bereits seit vielen Jahren unter dem Namen Automatische Personaldisposition (APD) Teil des Produkts IVU.crew und wird von vielen Kunden der IVU produktiv genutzt. Unter den langjährigen Verwendern der APD sind sowohl Stadtverkehrsbetriebe als auch regionale und überregionale Bahnbetriebe.

Es werden mittlere bis große Einsatzpläne mit einer dreistelligen Anzahl Planzeilen optimiert für Zeiträume von 2 Wochen bis zu 3 Monaten. Die verwendeten Optimierungsziele variieren abhängig von den betriebsspezifischen Anforderungen stark. Die Berücksichtigung der Wünsche der Mitarbeiter für freie Tage oder bestimmte Schichtlagen wird mehr und mehr nachgefragt und setzt sich in der Branche durch.

Bei einem regionalen Bahnunternehmen konnte mit der APD auch die Optimierung ganzer Jahrespläne erfolgreich durchgeführt werden, ohne dass technische Parameter angepasst werden mussten. Das Verfahren skalierte gut auch für diesen langen Zeitraum. Jahrespläne in vielen verschiedenen Varianten müssen auch für die Ermittlung des Personalkostenindex SPNV berechnet werden. Die IVU ist mit ihren Optimierungslösungen an dem Projekt zur Berechnung des Index beteiligt [11].

Die Wochenschemaoptimierung ist ein vergleichsweise neues Teilprodukt, das aber auch bereits produktiv im Einsatz ist. Betriebe, die hauptsächlich mit Wochenschemata arbeiten, und nur wenige Abweichungen vom regelmäßigen Turnus erlauben, profitieren stark von der Zeitersparnis bei der Erstellung der Wochenschemata bei gleichzeitig erhöhter Produktivität und Mitarbeiterzufriedenheit. Aber auch Betriebe, die die APD in der mittel- und kurzfristigen Disposition einsetzen und Wochenschemata nur mit groben Schichtlagen langfristig ausrollen, nutzen zusätzlich die Wochenschemaoptimierung, um diese Schichtpläne zu optimieren.

In [12] werden einige mögliche Ursachen für das Scheitern von Optimierungsprojekten im Bahnumfeld beschrieben. Die IVU.crew Optimierungen konnten wiederholt erfolgreich bei Kunden der IVU eingeführt werden, weil viele dieser Ursachen nicht gegeben waren. Durch den engen Kundenkontakt konnte das Verfahren bezüglich realistischer Szenarien evaluiert werden. Die Qualität der berechneten Lösungen ist regelmäßig so gut, dass die Ergebnisse ohne manuelle Nachbearbeitung verwendet werden können. Die Bedienung der Programme ist nicht zu komplex, da lediglich die Kostenfunktion definiert werden muss, aber kaum jemals technische Parameter angepasst werden müssen. Die Laufzeit der Berechnung ist kurz genug, so dass die Ergebnisse rechtzeitig vorliegen. Und schließlich sind alle Szenarien lösbar, da de facto keine harten Constraints definiert werden.

8 Fazit

Für die Optimierung von azyklischen Personaleinsatzplänen und zyklischen Wochenschemata wird in IVU.crew die Metaheuristik Simulated Annealing verwendet. Die konkrete Implementierung der Heuristik hat sich als effektiv und robust erwiesen und ist seit vielen Jahren erfolgreich im produktiven Einsatz bei Kunden der IVU Traffic Technologies AG.

Für einige Details der Implementierung wurden pragmatische Lösungen gewählt, für die es in der Literatur keine uns bekannten theoretischen Erkenntnisse gibt. Das sind insbesondere der lexikographische Vergleich der Kostenvektoren mit normierten Kostendeltas und die nicht gleichverteilten Zufallsentscheidungen mit einem Bias, der abhängig von den aggregierten Kosten der Constraints ist.

Viele technische Parameter des Verfahrens sind konfigurierbar, mussten aber in der Praxis fast nie an konkrete Optimierungsszenarien der Kunden angepasst werden, um zu zufriedenstellenden Ergebnissen zu gelangen. Das implementierte Verfahren skaliert auch mit den unveränderten Standardparametern gut für unterschiedliche Problemgrößen. Da die Constraints in der Programmiersprache C++ implementiert sind, ist das Verfahren leicht um neue Optimierungsziele erweiterbar, insbesondere auch um solche, die in globale und nichtlineare Constraints übersetzt werden müssen. Mit den derzeit implementierten Optimierungszielen werden allerdings bereits die für die Praxis wichtigsten Anforderungen abgedeckt, so dass Verkehrsbetriebe die IVU.crew Optimierungen regelmäßig nutzen können, um ihre Einsatzpläne und Wochenschemata zu optimieren.

9 Literatur

1. IVU Traffic Technologies AG, ivu.de
2. T. Breugem, T. Schlechte, C. Schulz, R. Borndörfer (2023). A three-phase heuristic for the Fairness-Oriented Crew Rostering Problem. Computers & Operations Research 154.
3. R. Borndörfer, M. Reuther, T. Schlechte, C. Schulz, E. Swarat, S. Weider (2015). Duty Rostering in Public Transport - Facing Preferences, Fairness, and Fatigue. ZIB-Report 15-44
4. R. Borndörfer, A. Löbel, U. Strubbe, M. Völker (1998). Zielorientierte Dienstplanoptimierung. HEUREKA '99: Optimierung in Verkehr und Transport, S. 171-194
5. Kevin I. Smith, Richard M. Everson, Jonathan E. Fieldsend (2004). Dominance Measures for Multi-Objective Simulated Annealing. Proceedings of the 2004 Congress on Evolutionary Computation, S. 23-30
6. Hentenryck and Michel (2005). Constraint-Based Local MIT Press, Cambridge.
7. M. Marte, V. Mayer-Eichberger (2011). Constraint-based crew rostering for public transport. Proceedings of the International Workshop on Innovative Scheduling and other Applications using CP-AI-OR (ISA 2011), S. 3-7
8. S. Kirkpatrick, C.D. Gelatt Jr.,M.P. Vecchi (1983). Optimization by Simulated Annealing. Science 220(4598), S. 671-680.
9. S. Geman, D. Geman (1984). Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. IEEE Transactions on Pattern Analysis and Machine Intelligence 6, S. 721-741.
10. Ingber (1993). Simulated annealing: Practice versus Mathematical and Computer Modelling 18(11), S. 29-57.
11. F. Zerban, W. Tusche, Dr. K. Redies, et al. Personalkostenindex für SPNV gestartet. Der Nahverkehr 11/2022
12. C. Liebchen, H. Schülldorf (2019). A Collection of Aspects Why Optimization Projects for Railway Companies Could Risk Not to Succeed – A Multi-Perspective Approach. 8th International Conference on Railways Operations Modelling and Analysis, S. 752-765.