Strategische Planung und Optimierung der Kapazität in Eisenbahnnetzen unter Nutzung von automatischer Taktfahrplanung

Textprobe:

Kapitel 5.2, Greedy-Strategien für die Konstruktion:

Im ersten Unterkapitel werden relativ einfache Strategien für die Konstruktion von Trassen auf überlagerten Zuglaufabschnitten erläutert. Diese Strategien ergeben sich intuitiv wenn man über eine Konstruktion bei überlagerten Zuglaufabschnitten nachdenkt, oder sind bewährte Heuristiken der manuellen Fahrplankonstruktion. Sie werden daher Greedy-Strategien genannt32 und in den Abschnitten 5.2.1 bis 5.2.4 beleuchtet.
5.2.1, Strategie "Auflösung der Überlagerungen":

Eine einfache Lösungsmöglichkeit besteht in der Auflösung der Überlagerungen durch Unterteilung der Zuglaufabschnitte an allen Verzweigungs- und Konfliktpunkten im Netz. Dadurch entstehen viele kurze Zuglaufabschnitte, die keine Überlagerungen mehr aufweisen. Abbildung 5.4 zeigt die Aufteilung der vier langen Zuglaufabschnitte in zehn kürzere Zuglaufabschnitte.
[.] Die Trennung der Zuglaufabschnitte an allen Verzweigungspunkten würde zwar die Überlagerungen auflösen, hätte jedoch zwei entscheidende Nachteile:
Fahrzeiten auf den kürzeren Zuglaufabschnitten passen nicht mehr zu gewünschten Lenkzeiten von 3,5 Stunden.
Keine ausreichende Pufferkapazität in vielen Teilungspunkten im Netz verfügbar.
Die Auflösung der Überlagerungen wird somit mit neuen Abhängigkeiten erkauft, die ebenfalls verhindern, dass die Zuglaufabschnitte unabhängig voneinander konstruiert werden können. Die Komplexität der überlagerten Zuglaufabschnitte und der konkurrierenden Relationen würde in das Belegungsverfahren übertragen werden, da dort für eine konfliktfreie Lösung beispielsweise die Knotenkapazitäten detailliert betrachtet werden müssen. Daher ist der Lösungsansatz der Unterteilung allein nicht zielführend und es müssen Trassen für die langen und überlagerten Zuglaufabschnitte konstruiert werden, die anschließend optimiert belegt werden. Jedoch wird die Idee der Unterteilung langer Zuglaufabschnitte in den Strategien "Engpassorientierung" und "Belegung und Flexibilität" aufgegriffen und mit weiteren Verfahren kombiniert.
5.2.2, Strategie "Seriell":

Eine weitere Lösungsmöglichkeit zur Konstruktion auf überlagerten Zuglaufabschnitten ist die sequentielle Abarbeitung der Zuglaufabschnitte. Zuerst wird eine Reihenfolge festgelegt, in der die Konstruktion erfolgen soll, beispielsweise nach absteigender Anzahl Trassen, die aus der Prognose gefordert werden. Anschließend wird für den ersten Zuglaufabschnitt in der Bearbeitungsreihenfolge die geforderte Trassenanzahl konstruiert (im Beispiel Tabelle 5.1 fünf Trassen zwischen H und M). Danach wird für die weiteren Zuglaufabschnitte in der Reihenfolge mit der verbleibenden Restkapazität auf den Strecken ebenfalls versucht die geforderte Anzahl Trassen zu erreichen.
[.] Falls für einen Zuglaufabschnitt aus Kapazitätsgründen nicht die geforderte Trassenanzahl konstruierbar ist, werden nur so viele Trassen konfliktfrei konstruiert wie möglich sind. Anschließend wird der nächste Zuglaufabschnitt in der Reihenfolge bearbeitet. Die Strategie "Seriell" garantiert (bei der absteigenden Sortierung nach geforderter Anzahl Trassen), dass auf Relationen mit hoher prognostizierter Nachfrage auch viele Systemtrassen angeboten werden können. Dies geht zulasten der Relationen, für die nur eine geringe Nachfrage besteht.
5.2.3, Strategie "Parallel":

Bei der Strategie "Parallel" wird im Gegensatz zur Strategie "Seriell" auf allen Zuglaufabschnitten gleichmäßiger konstruiert. Nach Festlegung einer Reihenfolge wird pro Zuglaufabschnitt immer genau eine Trasse konstruiert, bevor die Bearbeitung des nächsten Zuglaufabschnitts erfolgt (siehe Tabelle 5.2). Ein Zuglaufabschnitt wird nur so oft erneut in die Reihenfolge aufgenommen, bis die geforderte Trassenanzahl erfüllt ist. Dementsprechend werden die beiden Zuglaufabschnitte H->R und W->M genau einmal bearbeitet, da die Nachfrage nach einer Systemtrasse bereits nach der ersten Iteration erfüllt ist.
[.] Falls für einen Zuglaufabschnitt aus Kapazitätsgründen keine zusätzliche Trasse konstruiert werden kann, wird er nicht noch einmal in die Reihenfolge aufgenommen und der nächste Zuglaufabschnitt in der Reihenfolge bearbeitet. Die Strategie "Parallel" stellt sicher, dass auf allen Relationen (auch denjenigen mit geringer prognostizierter Nachfrage) mindestens eine Trasse angeboten werden kann. Dies geht zulasten der Relationen mit einer sehr hohen Nachfrage, die dadurch eventuell nicht mehr vollständig erfüllt werden können.
5.2.4, Strategie "Nachfrage":

In der Strategie "Nachfrage" wird wie in der Strategie "Parallel" pro Iteration immer nur eine Trasse je Zuglaufabschnitt konstruiert. Die Reihenfolge der Konstruktion ergibt sich hier jedoch direkt aus der Nachfrage. Ziel ist es, den minimalen Erfüllungsgrad aller Zuglaufabschnitte zu maximieren. Falls insgesamt für die vier Zuglaufabschnitte maximal nur 8 Systemtrassen konstruierbar wären, ist die minimale Erfüllung bei Fall 2 in Tabelle 5.3 höher (60% für H -> M) und daher besser als im Fall 1 mit 0% für die Zuglaufabschnitte W -> M und H -> R.
[.] Für denjenigen Zuglaufabschnitt, dessen relative Erfüllung der Nachfrage aktuell am geringsten ist, wird in der nächsten Iteration eine Trasse konstruiert. Bei Gleichstand wird der Zuglaufabschnitt ausgewählt, der einen höheren Zuwachs des Erfüllungsgrades hat33. Für das Beispiel mit den vier Zuglaufabschnitten würde sich die folgende Reihenfolge ergeben:

[.] Vor der ersten Iteration ist die Erfüllung auf allen Zuglaufabschnitten bei 0%. Die Relationen W -> M und H -> R hätten mit der Konstruktion einer Trassen jeweils einen Zuwachs auf 100% bei der Erfüllung. Daher wird zufällig der Abschnitt W -> M ausgewählt. In der zweiten Iteration wird nun die Relation H -> R ausgewählt, da der Zuwachs auf 100% größer ist als die Zuwächse der anderen beiden Zuglaufabschnitte. Die Erfüllung auf der Relation H -> B steigt auf 25% und für H -> M würde die Erfüllung auf 20% steigen. Dementsprechend wird zunächst der Zuglaufabschnitt H -> B und danach H -> M ausgewählt. In der fünften Iteration wird auf dem Zuglaufabschnitt H -> M erneut eine Trasse konstruiert, da die Nachfrage mit einer von fünf Trassen am geringsten erfüllt ist. Durch die zusätzliche Trasse steigt die Erfüllung von 20% auf 40% und in der nächsten Iteration wird auf der Relation H -> B mit einer aktuellen Erfüllung von 25% eine Trasse konstruiert.
Falls für einen Zuglaufabschnitt aus Kapazitätsgründen keine zusätzliche Trasse konstruiert werden kann, wird er nicht mehr bei dem Vergleich der Nachfrageerfüllung betrachtet und der nächste Zuglaufabschnitt mit noch nicht vollständig erfüllter Nachfrage bearbeitet. Die Strategie "Nachfrage" stellt sicher, dass die Relationen entsprechend ihrer Anforderung an Trassen möglichst gleichmäßig erfüllt werden. Relationen mit einer sehr geringen Nachfrage werden durch diese Strategie bevorteilt, da sie durch die hohen Zuwachsrate mit der ersten Trasse in einer sehr frühen Iteration ausgewählt werden.
5.2.5, Zusammenfassung der Greedy-Strategien:

Die Kernidee der Greedy-Strategien besteht darin, eine geeignete Reihenfolge für eine sequentielle Fahrplankonstruktion zu ermitteln und diese anschließend abzuarbeiten, bis die Anforderung erfüllt oder die Kapazität ausgeschöpft ist. In der manuellen Konstruktion werden die bisher beschriebenen Strategien "Seriell", "Parallel" und "Nachfrage" auch miteinander kombiniert oder bereits konstruierte Trassen noch einmal zurückgenommen um eventuell zwei Trassen auf anderen Zuglaufabschnitten zu ermöglichen. Dieses "Trial & Error"-Verfahren wird jedoch mit steigender Anzahl überlagerter Zuglaufabschnitte immer schwerer zu durchschauen und dadurch die Bearbeitung sehr zeitintensiv. Ein weiterer Nachteil ist, dass diese Heuristik keinen Anhaltspunkt liefert, ob sich ein weiteres Ausprobieren lohnt oder wie weit man von dem Optimum entfernt ist. Weiterhin ist die Bestimmung des Engpasses davon abhängig, auf welchen Relationen man die Nachfrage nicht vollständig erfüllt, da nur für diese Strecken die maßgebenden kapazitätsbeschränkenden Abschnitte bestimmt werden können.