In diesem Beitrag wird ein neuartiger Ansatz zur Dienst- und Umlaufplanung im öffentlichen Personennahverkehr vorgestellt. Zum Einsatz kommt dabei der Arelion Optimization Core, ein evolutionäres Optimierungsverfahren, das sich dazu eignet, durch Abbildung von problemspezifischem Wissen verschiedenste komplexe Optimierungsprobleme mit guter Qualität und Laufzeit näherungsweise lösen zu können. Es werden dabei die Herausforderungen und die Notwendigkeit der integrierten Planung aufgezeigt und ein kurzer Überblick über bestehende Ansätze gegeben. Die Ergebnisse werden anhand eines konkreten Anwendungsfalls aus der Praxis untersucht.

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

1 Einleitung

Der Druck für Verkehrsunternehmen wird immer größer. Einerseits bedingt durch den größer werdenden Wettbewerbsdruck und damit einhergehend einer Steigerung des Kostendrucks und andererseits durch eine Vielzahl verschiedenster Rahmenbedingungen wie beispielsweise Sonderverkehre, Messen, Ersatzverkehre usw., die möglichst schnell berücksichtigt werden müssen, entsteht ein vermehrter Bedarf an Optimierung. Da diese Probleme bereits so umfangreich geworden sind und Lösungen in kurzer Zeit benötigt werden, ist nicht mehr daran zu denken, sie manuell zu lösen. Das heißt, der Bedarf an Optimierungssoftware, welche diese Probleme möglichst automatisiert und ohne Nacharbeit lösen sollen, wird immer größer.

Für Betriebsplanungssysteme lassen sich prinzipiell zwei Arten von Optimierungssystemen unterscheiden. Die Unterscheidung findet nach der Vorgehensweise bei der Lösungsgenerierung statt. Bei der sequentiellen oder auch klassischen, städtischen Betriebsplanung findet in einem abgeschlossenen Optimierungsschritt zuerst nur eine Planung der Umläufe statt. Das Resultat der Umlaufplanung dient als Basis für die Personaldienstplanung. Es findet dabei prinzipiell keine Rückkopplung zur Umlaufplanung statt, das heißt, die Umläufe gelten in der Dienstplanung als gegeben und unveränderlich. Für die sequentielle Planung gibt es verschiedenste etablierte Verfahren bzw. Algorithmen, die jeweils für Umlaufplanung oder Dienstplanung gut funktionieren. Es ist aber festzuhalten, dass die Lösung aus den beiden einzelnen Optimierungssystemen nicht unbedingt einem globalen Optimum entsprechen muss. Insbesondere da die Umläufe in der Dienstplanung als unveränderbar angesehen werden, besteht die Gefahr, in lokalen Optima für die Gesamtlösung hängen zu bleiben. Im schlimmsten Fall kann sich in der sequentiellen Planung sogar der Fall ergeben, dass auf Basis der Umlaufplanung kein gültiger Dienstplan erstellt werden kann. Um bei diesem Vergehen innerhalb der Umlaufbildung die zu vergütende Arbeitszeit der Fahrer abzubilden, werden die Fahrzeugeinsatzzeiten mit Kosten belegt. Dies widerspricht der Realität insofern, dass ein Fahrzeug als solches keine zeitabhängigen Kosten produziert, diese entstehen erst dadurch, dass ein zu bezahlender Fahrer dem Fahrzeug zugeordnet wird. In der Anwendung führt dieses Vergehen zu einer Mehrung von Leerkilometern. Verschärft wird dieses Problem noch dadurch, dass Wendezeiten, die ein Fahrer auf dem Fahrzeug verbringt, und als {unbezahlte) Pausenzeiten herangezogen werden könnten, bei diesem Verfahren minimiert werden, und somit zu kurz werden und nicht als Pausenzeit heran gezogen werden können.

Einen anderen Weg geht die integrierte (Dienst-Umlauf-)Planung. Hier wird die Aufgabenstellung in ihrer Gesamtheit erfasst, weil man ausgehend von den Rahmenbedingungen erkannt hat, dass es am sinnvollsten wäre, Umlauf- und Dienstplanung in einem einzelnen Schritt durchzuführen. Bei dieser Art der Planung werden die zu erbringenden Fahrzeugfahrten als Eingangsgröße herangezogen, die dann in der Planung zu Diensten zusammengesetzt werden. Es können auch Fahrten auf mehrere Dienste aufgeteilt werden. Damit werden Ablösen in Dienstfahrten dargestellt. Ziel der integrierten Planung ist sowohl den Fahrzeugbedarf in der Spitze, die Leerfahrten bzw. -kilometer als auch die Arbeitszeit zu minimieren. Dabei werden als wesentlicher Kostentreiber die Fahrpersonalkosten berücksichtigt. Die Umläufe werden jeweils parallel zu den Diensten gebildet. Die Umläufe unterliegen auch keinen großen Beschränkungen und sind damit erheblich leichter abzuleiten. Hauptschranke für die integrierte Planung bildet die Fahrzeugflotte. Es können niemals mehr Fahrzeuge zur gleichen Zeit verplant werden, als im Pool verfügbar sind. Natürlich ist die integrierte Planung wesentlich komplexer als die sequentielle Planung. Es müssen nun alle Rahmenbedingungen gleichzeitig beachtet werden. Beispiele dafür sind:

•    Gesetzliche und tarifliche Vorgaben in der Dienstplanung (Arbeitszeiten- und Pausenregelungen)

•    Vorgaben in der Umlaufplanung (Fahrzeugtypen, maximale Reichweiten etc.)

•    Unerwünschte Linienkombinationen

•    Verschiedene Diensttypen

•    Dienstteilungen

•    Maximale Anzahl der Dienste je Diensttyp

•    Verschiedene Depots mit verschiedenen Fahrzeugkapazitäten

•    Verschiedene Pauseneinrichtungen, die zwischendurch angefahren werden müssen

•    Ablösemöglichkeiten und Wege zu den Ablösepunkten (ggf. mit eigenem Ablöse­-Pkw)

Neben den Zielen aus der Umlaufplanung wie Reduktion der Leerkilometer und der Anzahl der Fahrzeuge kommen weitere Ziele wie Reduktion der Dienste und Dienstzeiten hinzu.

Eine exakte Lösung im Sinne eines mathematisch beweisbaren Optimums ist ab einer bestimmten Problemgröße in sinnvoller Zeit zum aktuellen Zeitpunkt nicht realisierbar. Die Arelion GmbH verwendet zur Lösung integrierter Planungsaufgaben einen neuartigen, innovativen Ansatz. Dazu verwendet sie eine Technologie, die in mehr als 25 Personenjahren Forschung an der Johannes Kepler Universität Linz in einer Kooperation mit der Siemens AG München / Corporate Technology entwickelt wurde. Aus dieser Forschungskooperation hat sich die Arelion GmbH entwickelt, die seit 2012 einerseits an der Weiterentwicklung der Technologie arbeitet und andererseits ihren Kunden innovative Optimierungslösungen anbietet. Die Technologie, der Arelion Optimization Core (AOC), wurde in den verschiedensten Branchen bereits erfolgreich angewendet. Der große Vorteil in Anwendung zeigt sich auch in der integrierten Planung.

2 Überblick über existierende Verfahren

Laut der Komplexitätstheorie ist das hier zu lösende Problem NP-schwer, da bis jetzt noch kein Algorithmus gefunden wurde, der dieses Problem in polynomieller Zeit lösen kann. Allerdings wurde auch (noch) nicht bewiesen, dass so ein Algorithmus nicht existiert.

Sowohl im Allgemeinen als auch zur Lösung von dem speziellen Problem der integrierten Dienst-Umlauf-Optimierung werden folgende Modellierungs- und Lösungstechniken eingesetzt:

2.1 Heuristiken und Metaheuristiken

Da das Problem der integrierten Dienst-Umlauf-Optimierung, wie viele andere praktisch relevante Optimierungsprobleme, sehr groß und daher nur sehr schwer zu lösen ist, ist man oft gezwungen, auf Verfahren zurückzugreifen, die bei vertretbaren Rechenaufwand eine möglichst gute, aber nicht zwingend optimale Lösung liefern. Solche Verfahren werden Heuristiken genannt. Während Heuristiken in der Regel auf ein spezielles Problem zugeschnitten sind und die Problemstruktur nutzen, sind Metaheuristiken allgemeine, übergeordnete Schemata zur Steuerung eines oder mehrerer abhängiger heuristischer Verfahren. Typische Metaheuristiken für Schedulingprobleme sind Simulated Annealing, genetische Algorithmen, neuronale Netze, Ameisenalgorithmen oder Tabu-Search.

2.2 Dynamische Programmierung

Bei der dynamischen Programmierung werden Probleme betrachtet, die in mehrere Teilprobleme oder Stufen zerlegt werden können. Hängt der Zustand einer Stufe von dem Zustand und der Entscheidung der vorhergehenden Stufe ab, spricht man von dynamischer Optimierung. Die Gesamtentscheidung wird dabei durch stufenweise, rekursive Einzelentscheidungen ersetzt. Auch hier wird nicht zwingend eine optimale Lösung erzielt.

2.3 Lineare Optimierung

Bei Modellen der linearen Optimierung oder linearen Programmierung (LP) bestehen die Zielfunktion und alle Restriktionen aus Linearkombinationen von Entscheidungsvariablen. Die Variablen selbst können dabei reelle Werte annehmen.

Zur Lösung von linearen Programme existiert eine Vielzahl schneller, effizienter Algorithmen, allerdings sind in dem speziellen Fall von Scheduling-Problemen meist ganzzahlige Lösungen gefordert.

2.4 Gemischt-ganzzahlige Optimierung

Da eine Teilbarkeit von Ressourcen nicht gegeben ist bzw. die Variablen unteilbare 0/1-Entscheidungen abbilden, dürfen alle bzw. einige der Variablen nur ganze Zahlen annehmen. In diesem Fall spricht man von ganzzahliger bzw. gemischt-ganzzahliger Optimierung. Im Gegensatz zur linearen Optimierung sind ganzzahlige und gemischt-ganzzahlige Modelle in der Regel sehr schwer zu lösen.

Gängige Verfahren zur Lösung von MIP-Problemen sind:

•    Branch-and-Bound-Verfahren

•    Set Partitioning & Set Covering Modelle mit zusätzlichen Nebenbedingungen

•    Column Generation Algorithmen

•    Lagrange Relaxation und Subgradienten-Optimierung

•    Ressource Constrained Shortest Path Algorithmen

Abgesehen von proprietären, heuristischen Ansätzen für die integrierte Dienst-Umlauf­Optimierung werden aktuell meist Verfahren der gemischt-ganzzahligen Optimierung verwendet. Allerdings läst der derzeitige Stand der Algorithmen und der Technik eine exakte Lösung von Problemstellungen realistischer Größenordnung noch nicht zu. So ist es bei realistischen Problemgrößen einerseits nicht möglich, bei einem Column Generation-Ansatz durch vollständige Enumeration alle Spalten zu erzeugen und andererseits garantiert die Theorie der linearen Programmierung nicht, dass ein solcher Algorithmus nach einer endlichen Anzahl von Schritten mit einer zulässigen und optimalen Lösung terminiert. Dann muss zur Bestimmung konsistenter Lösungen eine Heuristik eingesetzt werden.

Um dennoch solche Algorithmen einsetzen zu können, wird daher in der Regel die Problemgröße zunächst heuristisch verkleinert, d.h. es werden einige Entscheidungen im Vorfeld getroffen und die Problemgröße somit reduziert. Selbst wenn das verbleibende verkleinerte Problem anschließend optimal gelöst werden kann, ist durch die heuristische mit Vorverarbeitung nicht sichergestellt, dass für das ursprüngliche Probleme keine bessere Lösung existiert.

3 Planung mit dem Arelion Optimization Core

In diesem Abschnitt soll beschrieben werden, wie das konkrete Problem der integrierten Dienst- und Umlaufplanung mit dem Arelion Optimization Core gelöst werden kann.

3.1 Funktionsweise des Arelion Optimization Core

Der Arelion Optimization Core (AOC) beruht auf einem Optimierungsframework, das an der Johannes Kepler Universität Linz in einer Kooperation mit der Siemens AG entwickelt wurde und damals als .OptLets Framework" bezeichnet wurde (vgl. [131).

Der AOC bedient sich verschiedensten Ansätzen aus der Literatur. Von der Grundkonzeption ist das Verfahren ein evolutionäres Verfahren und kann als Metaheuristik angesehen werden. Wie in evolutionären Verfahren üblich, können zu jedem beliebigen Zeitpunkt Lösungen angeboten werden. Je mehr Zeit man dem Verfahren gibt, desto besser werden die Lösungen. Dies passiert, in dem schrittweise eine Lösung aus dem Pool genommen wird und in einem Optimierungsschritt versucht wird, diese Lösung zu verbessern. Hat sich prinzipiell die Lösung verbessert, so wird sie in den Pool aufgenommen. Mit dieser Methodik wird die Qualität des Lösungspools mit der Zeit immer besser. Ähnliche, bereits eingesetzte Verfahren vollführen die Optimierungsschritte ohne Problemwissen und eine Verbesserung findet rein zufällig statt. Diese Verfahren stehen im Ruf, unter Umständen sehr schnell zu sein, aber keine vernünftige Lösungsqualität zu erreichen.

Hier setzt der Arelion Optimization Core an. Der AOC geht davon aus, dass sich jede Optimierungsaufgabenstellung von anderen unterscheidet. Das heißt, eine globale Heuristik zur Optimierung beliebiger Probleme existiert nicht. Deshalb bietet der AOC das Konzept an, zielorientiert Lösungen weiterzuentwickeln. Dadurch kann beliebiges Wissen über eine konkrete Aufgabenstellung in sogenannten Solving Units (auch als virtuelle Experten bezeichnet) abgebildet werden. Konzeptionell kann man sich das so vorstellen, dass alle Problemexperten um einen Tisch sitzen. Jeder dieser Experten hat eine andere Sicht auf die Aufgabenstellung und bringt andere Ideen in die Lösungsgewinnung ein. Es wird in jedem Optimierungsschritt eine Lösung einem Experten zugeteilt, der mit der Lösung generell und isoliert von den Meinungen der anderen Experten machen kann, was er möchte. Hat eine Solving Unit eine Lösung verbessert, so steigt die Wahrscheinlichkeit, mit der der Experte später wiederum durch den AOC beauftragt wird. Das heißt, das System lernt aus dem Verhalten der Experten und das System wird immer besser, je länger das System läuft. Wobei „lang" in diesem Kontext eher als kurzer Zeitraum (von wenigen Sekunden bis zu Minuten) zu sehen ist. Das System generiert somit eine Lösung, die eine ausgewogene Mischung aus allen Beteiligten bildet. Der AOC selbst tariert die verschiedenen Ansätze und Aspekte gegeneinander aus. Dadurch dass die Solving Units isoliert voneinander arbeiten, können Optimierungslösungen auf Basis des AOC beliebig skalieren. Bild 1 zeigt die Architektur eines Optimierers, der auf dem AOC basiert.

Bild 1: Architektur des Arelion Optimization Core

Die Eingabedaten beschreiben die konkreten Parameter einer Problemstellung. Die Lösungen beschreiben, wie die Ergebnisdaten für die zu optimierende Probleminstanz aufgebaut sind. Sowohl die Struktur der Eingabedaten als auch die Struktur der Lösung sind problemspezifisch. Der Begriff Lösung ist dabei sehr weit gefasst. Lösungen im Sinne des AOC können sehr weit vom Optimum entfernt oder sogar unzulässig sein.

Die Solving Units sind die zentralen Komponenten eines spezifischen Optimierers. Die Aufgabe einer Solving Unit ist, aus einer bestehenden Lösung eine neue, veränderte Lösung zu erzeugen. Die Strategien, die dabei angewendet werden, sind problemspezifisch und können sehr unterschiedlich sein. Das kann eine Konstruktion einer vollständigen Lösung mittels eines heuristischen Verfahrens sein oder kleine Änderungen an einer bestehenden Lösung (wie z.B. das Vertauschen von zwei Orten bei einer Routenplanung).

Die Auswahl der Solving Units ist zufallsgesteuert, wobei die Solving Units jedoch unterschiedliche Auswahlwahrscheinlichkeiten haben, die sich aus einer periodischen Bewertung durch das Framework ergeben. Das heißt, es werden diejenigen Solving Units bevorzugt, welche häufiger zu Verbesserungen geführt haben. Dabei werden nicht nur direkte Verbesserungen durch einzelne Solving Units berücksichtigt, sondern auch Verbesserungen über mehrerer Schritte (mit zwischenzeitlich schlechteren Lösungen).

3.2 Einsatz des AOC zur Dienst- und Umlaufplanung

Nachfolgend wird beschrieben, wie das Datenmodell (Eingabedaten und Lösungsrepräsentation) und die Solving Units problemspezifisch für das Problem der Dienst­ und Umlaufplanung umgesetzt wurden.

3.2.1 Datenmodell

Das Datenmodell umfasst einerseits die zu optimierenden Daten (die Eingabedaten) und andererseits die entstehenden Dienst- und Umlaufpläne (Lösungen).

Die Eingabedaten enthalten u.a. folgende Datenstrukturen:

•    Liste von Linienfahrten mit Abfahrts- und Ankunftszeit, Start- und Endhaltestelle, erlaubten Fahrzeugtypen und Ablösemöglichkeiten

•    Liste von Depots und Pausenorten mit entsprechenden Fahrzeugkapazitäten

•    Liste von Fahrzeugtypen und Kapazitäten

•    Matrix mit Fahrzeiten und Entfernungen zwischen verschiedenen Orten (für Leerfahrten)

•    Matrix mit Transferzeiten für Fußwege zwischen Ablösepunkten

Eine Lösung besteht in erster Linie aus einer Liste von Diensten. Jeder Dienst enthält mehrere Umlaufstücke, die im Rahmen dieses Dienstes gefahren werden. Ein Umlaufstück besteht aus einer Liste von Fahrten, einem Anfangs- und Zielort (Depot oder Ablösepunkt). Jedes Umlaufstück enthält zudem einen Verweis auf das vorherige und nächste Stück im gleichen Umlauf. Daraus ergibt sich dann der Umlaufplan.

3.2.2 Solving Units

Eine Gruppe von Solving Units dient zur Findung von Startlösungen. Eine derartige Solving Uni! konstruiert mittels eines heuristischen Verfahrens eine vollständige neue Lösung, unabhängig von der zugewiesenen Ausgangslösung. Unterschiedliche Solving Units verwenden dabei unterschiedliche Parametrisierungen und Zufallsschwankungen, so dass eine Vielzahl von Startlösungen unterschiedlicher Qualität entsteht. Diese Lösungen sind allerdings in der Regel noch relativ weit von einer guten Lösung entfernt, oft sind sie auch unzulässig, weil Constraints wie z.B. Arbeits- oder Pausenzeiten verletzt werden. Sie bilden aber eine gute Ausgangsbasis für inkrementelle Verbesserungen durch die übrigen Solving Units. Jede diese Starter Solving Units erzeugt nur eine bestimmte maximale Anzahl von Lösungen, anschließend wird sie deaktiviert.

Die meisten Solving Units führen lokale Änderungen an einer bestehenden Lösung durch, die nur wenige Dienste oder Umläufe betreffen. Typische Operationen sind z.B.:

•    Vertauschen oder Verschieben von Umlaufstücken zwischen zwei Diensten

•    Vertauschen oder Verschieben von einzelnen Fahrten zwischen Umlaufstücken

•    Kombination von mehreren kurzen zu einem langen Dienst

•    Aufteilen eines langen auf mehrere kurze Dienste

•    Änderung von Depots, von denen Umläufe oder Dienste beginnen und enden

•    Kombination von mehreren Umlaufteilen zu einem Umlauf mittels Ablösen von Fahrern

Verschiedene Solving Units unterscheiden sich nicht nur in den Operationen, die sie durchführen, sondern auch in der Auswahlstrategie, auf welchen Diensten bzw. Umläufen sie diese Operationen durchführen. Die einfachste Strategie ist die rein zufällige Auswahl.

Darüber hinaus gibt es eine Reihe verschiedener mehr zielgerichteter Strategien. Eine solche Strategie besteht z.B. darin, gezielt unzulässige Dienste auszuwählen, die durch die Änderung repariert werden können, z.B. ein zu langer Dienst durch Verschieben der letzten Fahrt zu einem anderen Dienst. Andere Strategien zielen auf die Verbesserung eines bestimmten Aspektes ab, wie z.B. Reduktion von Leerfahrtzeiten oder Reduktion von Standzeiten. Manche Solving Units wählen gezielt Dienste oder Umläufe in Spitzenzeiten aus, weil dadurch eine höhere Chance besteht, durch eine Änderung z.B. einen Dienst oder Umlauf einzusparen.

3.2.3 Constraints und Zielfunktion

Die Definition des konkreten Umlauf-/Dienstplanungsproblems ist durch die Constraints und die Zielfunktion gegeben. Insbesondere die Constraints können sich für verschiedene Probleminstanzen, d.h. je nach betrieblichen Gegebenheiten, in einigen Aspekten unterscheiden. Die Flexibilität des Planungsverfahrens mit dem AOC erlaubt es, entsprechende Anpassungen projektspezifisch umzusetzen.

3.2.3.1 Constraints

Die Constraints dienen einerseits dazu festzustellen, ob eine vorliegende Lösung gültig oder ungültig im Sinne der Umlauf-/Dienstplanung im Allgemeinen und der betrieblichen Vorgaben im Speziellen sind. Andererseits geben die Constraints sowohl Ansatzpunkte zur Konstruktion von Startlösungen als auch zum Entwurf von entsprechenden Solving Units bzw. der darin implementierten Operationen.

Die Constraints können in zwei Teilmengen unterschieden werden. Die erste Teilmenge betrifft den Umlaufplan:

(U1)    Alle Lastfahrten müssen in genau einem Umlauf verplant sein.

(U2)    Jeder Umlauf muss mit einer Ausrückfahrt beginnen und mit einer Einrückfahrt enden.

(U3)    Es darf keine zeitliche Überlappung von Umlaufelementen existieren.

(U4)    Der Umlauf darf keine zeitlichen oder örtlichen Lücken aufweisen; diese müssen durch Umlauftätigkeiten (Stand, Leerfahrt} aufgefüllt werden. (Ausnahme: Stand an einem Parkpunkt.)

(U5)    Die Schnittmenge der möglichen Fahrzeugtypen der Lastfahrten eines Umlaufs gemäß Eingabedaten darf nicht leer sein.

(U6)    Die Kapazitäten der Flotte und jedes Depots pro Fahrzeugtyp müssen eingehalten werden.

Weitere Constraints, die von den betrieblichen Vorgaben abhängen, betreffen z.B. die maximal zulässige Standzeit an einem Haltepunkt, einzuhaltende Mindestwende- und Mindestbereitstellzeiten oder die Zulässigkeit der Rotation von Fahrzeugen zwischen Depots. Ein weiteres Beispiel ist die eingeschränkte Reichweite von Fahrzeugen bestimmter Typen (z. B. Gasbusse).

Die zweite Teilmenge der Constraints betrifft den Dienstplan:

(D1)    Alle Umlaufelemente müssen in genau einem Dienst verplant sein.

(D2)    Die Elemente eines Dienstes dürfen keine zeitliche Überlappung aufweisen.

(D3)    Der Dienst darf keine zeitlichen oder örtlichen Lücken aufweisen; diese müssen durch Diensttätigkeiten (Pause, Wartezeit, Wegezeit) aufgefüllt werden. (Ausnahme: Dienstunterbrechung an einem Depot bei geteilten Diensten.)

(D4)    Jeder Dienst muss den Arbeitszeitbestimmungen eines Diensttyps genügen.

(D5)    Jeder Dienst muss an dem Depot enden, an dem er begonnen hat.

Die Diensttypen und die Vorgaben bzgl. der Arbeitszeitbestimmungen sind dabei betriebsabhängig. Beispiele für Diensttypen sind Dienste mit Blockpausen oder geteilte Dienste. Die konkreten Ausprägungen der Diensttypen sind u. a. durch die minimale/maximale Dienstdauer, die minimale/maximale Arbeitszeit pro Dienst und pro Dienstteil und die Pausenregelung (Anzahl Pausen, minimale/maximale Pausendauer) gegeben. Zudem kann die zeitliche Lage der Dienste auf ein bestimmtes Zeitband eingeschränkt sein (z. B. Früh- oder Spätdienste).

Zusätzliche, betriebsabhängige Constraints ergeben sich aus der Notwendigkeit für Diensttätigkeiten, die ein Fahrer ohne Umlauf zu erledigen hat. Beispiele hierfür sind Vor­ bzw. Nachbereitungsarbeiten zum Dienstbeginn/-ende im Depot oder Wegezeiten zu Fuß oder mit einem Ablösefahrzeug, um Ablösen außerhalb des Depots zu realisieren.

3.2.3.2 Zielfunktion

Die Zielfunktion dient der Bewertung einer Lösung und damit auch zum Vergleich von Lösungen. Der mittels der Zielfunktion ermittelte Wert beschreibt die Kosten einer Lösung, die es zu minimieren gilt (wobei hier nicht ausschließlich die betrieblichen Kosten gemeint sind, sondern ein abstraktes Maß für die Qualität einer Lösung).

In die Zielfunktion fließen eine Reihe (gewichteter) Kennzahlen aus dem Umlauf- und dem Dienstplan einer Lösung ein. Dazu zählen:

•    Die Anzahl Umläufe und Dienste: Diese Kennzahlen dienen als Maß für den benötigten Fahrzeug- bzw. Personaleinsatz.

•    Der Umlauf- und der Dienstplanwirkungsgrad: Es wird die gesamte Umlauf- bzw. Dienstzeit ins Verhältnis zur gesamten Lastfahrtzeit gesetzt. Das Verhältnis von Dienst- zu Umlaufzeit ist für ein integriertes Planungsverfahren als Kennzahl zur Steuerung der Lösungsentwicklung ungeeignet.

•    Die Summe der Leerfahrtkilometer als Maß für die Kosten durch Laufleistung, die zusätzlich zur Durchführung der Lastfahrten entsteht.

•    Die bezahlte Arbeitszeit über alle Dienste: Diese schließt auch bezahlte Tätigkeiten außerhalb des Umlaufs mit ein.

Weitere Faktoren dienen als Bonus/Malus bei der Bewertung von Lösungen in Hinsicht auf betriebliche Aspekte wie z. B. der gewünschten Verteilung von Diensten auf Depots, der angestrebten durchschnittlichen Arbeitszeit pro Dienst oder der Verteilung der Dienste auf Diensttypen. Auch bei der Zielfunktion ist die Flexibilität des AOC-basierten Verfahrens von Vorteil, da ggf. problemspezifische Eigenschaften abgebildet werden können (z. B. eine abgestufte Bewertung des Fahrzeugeinsatzes).

4 Ergebnisse und Vergleich

In diesem Abschnitt werden die Ergebnisse des AOC-basierten Optimierers mit der vorherigen Lösung eines konkreten Verkehrsbetriebs verglichen.

Der zu optimierende Fahrplan weist folgende Kennzahlen auf:

•    1564 Linienfahrten

•    1O Depots und 2 Pausenorte

•    6 verschiedene Fahrzeugtypen

Eine reine Umlaufoptimierung mittels eines exakten Verfahrens ergibt ein Minimum von 138 Umläufen.

Die Dienstbildung wird in diesem konkreten Fall zusätzlich dadurch erschwert, dass es nur zwei Pausenorte in zentraler Lage gibt, an denen alle Umläufe immer wieder vorbeiführen müssen. Man kann daher davon ausgehen, dass sich die aus reiner Umlaufsicht optimale Anzahl von Umläufen nicht halten lässt.

Die vorherige Lösung des Kunden, berechnet mit einem proprietären MILP-basierten Verfahren, enthält 188 Dienste und 141 Umläufe bei einem Umlaufwirkungsgrad von 72,9%.
Die Lösung des AOC-basierten Optimierers enthält 185 Dienste und 140 Umläufe bei einem Umlaufwirkungsgrad von 71,5%. D.h. es konnten 1 Fahrzeug und 3 Dienste eingespart werden auf Kosten eines etwas niedrigeren Umlaufwirkungsgrads, der sich aus zusätzlichen Leerfahrten und Standzeiten ergibt.

Die ersten Lösungen, die von den Starter Solving Units gefunden werden, erfüllen nicht alle Constraints hinsichtlich der Arbeitszeiten und sind daher unzulässig. Erste zulässige Lösungen werden nach einer Laufzeit von ca. 5 Sekunden gefunden, diese Lösungen enthalten ca. 260 Dienste und 160 Umläufe, sind also noch weit von der finalen Lösung entfernt. Nachfolgende Tabelle zeigt den weiteren Lösungsverlauf über die Zeit (UWG = Umlaufwirkungsgrad).

Tabelle 1: Lösungsentwicklung

Im Vergleich dazu benötigte der zuvor beim Kunden eingesetzte Optimierer mehr als 24 Stunden zur Berechnung der Lösung. Zwischenlösungen sind dabei nicht verfügbar.
Ein wesentlicher Vorteil des AOC im Vergleich zu anderen evolutionären Verfahren liegt in der zielgerichteten Arbeitsweise, die sich zum einen durch die Abbildung des Problemwissens in den Solving Units und zum anderen durch die Bewertung und gezielte Auswahl der Solving Units ergibt.

Wie sehr sich insbesondere die Bewertung der Solving Units durch den AOC auf die Lösungsentwicklung auswirkt, wird ersichtlich, wenn man die Bewertung deaktiviert und die Auswahl rein zufällig durchführt.

Tabelle 2: Lösungsentwicklung ohne Bewertung der Solving Units

Die Optimierung ohne Bewertung der Solving Units durch den AOC zeigt einen deutlich langsameren Fortschritt bei der Lösungsentwicklung. Bei gleicher Rechenzeit ist die Qualität der Lösung wesentlich schlechter.

Die Ergebnisse zeigen, dass die integrierte Dienst- und Umlaufplanung mittels des Arelion Optimization Core mit anderen in der Praxis verwendeten Verfahren konkurrieren kann und sowohl hinsichtlich der Lösungsqualität als auch der Laufzeit bessere Ergebnisse liefern kann. Insbesondere hinsichtlich der Performance weist der Optimierer aber noch großes Verbesserungspotential und es wird erwartet, dass zukünftige Versionen deutlich weniger Rechenzeit benötigen werden.

5 Literatur

[1] B. Amberg, N. Kliewer, and M. Beck. Robuste Effizienz bei der Einsatzplanung für Bus und Fahrer. Der Nahverkehr, 1/2, 2012.

[2] Borndörfer, M. Grötschel, and U. Jäger. Planning problems in public transit. In M. Grötschel, K. Lucas, and V. Mehrmann, editors, Production Factor Mathematics, pages 95-122. acatech/Springer, Berlin Heidelberg, 2010. ZIB Report 09-13.

[3] R. Bomdörfer, M. Grötschel, A. Löbel, and S. Weider. Integrierte Umlauf- und Dienstplanung im öffentlichen Nahverkehr. In Neue Mathematische Verfahren in Industrie und Dienstleistungen, BMBF Mathematikprogramm 03GRM2B4, 2003.

[4] R. Borndörfer, M. Grötschel, and M. E. Pfetsch. A column-generation approach to line planning in public transport. Transportation Science, 41(1):123--132, 2007.

[5] R. Borndörfer, M. Grötschel, and M. E. Pfetsch. Models for line planning in public transport. In M. Hickman, P. Mirchandani, and S. Voß, editors, Computer-aided Systems in Public Transport, volume 600 of Lecture Notes in Economics and Mathematical Systems, pages 363-378. Springer Berlin Heidelberg, 2008.

[6] R. Borndörfer, A. Löbel, U. Strubbe, and M. Völker. Zielorientierte Dienstplanoptimierung. In Heureka '99: Optimierung in Verkehr und Transport, pages 171 -194, 1999.

[7] S. Bunte and N. Kliewer. An overview on vehicle scheduling models. Public Transport, 1(4):299-317, 2009.

[8] M.R. Bussieck, T. Winter, and U. Zimmermann. Discrete optimization in public rail transport. Mathematical Programming, 79:415-444, 1997.

[9] R. Freling, A. P.M Wagelmans, and J. M. Pinte Paixäo. An overview of models and techniques for integrating vehicle and crew scheduling. Technical Report 9801, Rotterdam Institute for Business Economic Studies, 1998.
[10] A. Gaffi and M. Nonato. An integrated approach to the extra-urban crew and vehicle scheduling problem. In N.H.M. Wilson, editor, Proceedings of the 7th Inter. Conference on Computer-Aided Scheduling of Public Transport, pages 103-128, 1999.

[11] C. Liebchen. Linien-, Fahrplan-, Umlauf- und Dienstplanoptimierung: Wie weit können diese bereits integriert werden? In M. Friedrich, editor, Heureka'08 - Optimierung in Transport und Verkehr, Tagungsbericht. FGSV Verlag, 2008.

[12] 1. Steinzen, V. Gintner, L. Suhl, and N. Kliewer. A time-space network approach for the integrated vehicle and crew scheduling problem with multiple depots. Transportation Science, 44(3), 2010.

[13] Breitschopf, C.; Blaschek, G.; Scheid!, T. Optlets: A Generic Framework for Solving Arbitrary Optimization Problems. 6th WSEAS lnt. Conference on Evolutionary Computing, Lissabon, 16.-18.6.2005.