Automatisiertes Dispatching

 

Dispatching gibt es im Luftverkehr und im Zugverkehr.  Im Luftverkehr führen die Fluglotsen das Dispatching durch, indem sie jedem Piloten in einem Kontrollbereich vorgeben, wann und auf welcher Flugstraße sein Flugzeug fliegen soll, so dass Flugzeuge sich gegenseitig nicht gefährden.

Auch im Zugverkehr gibt es die Train-Dispatcher, das Äquivalent zu den Fluglotsen, die verantwortlich sind für einen gewissen Bereich und dort jedem Zugführer mitteilen, wann und auf welcher Fahrstraße der Zug fahren soll, so dass Sicherheitsabstände und viele weitere Bedingungen eingehalten werden.

 

Wir haben über die letzten Jahre viel Fachwissen erworben  und Algorithmen entworfen, die Fluglotsen und Train-Dispatcher unterstützen, indem sie konfliktfreie Dispatching-Lösungen unter Berücksichtigung zahlreicher sehr unterschiedlicher Nebenbedingungen erstellen. Wenn Sie Interesse an diesem Thema und einer Zusammenarbeit haben, kontaktieren Sie uns bitte.  Im Folgenden stellen wir diese Algorithmen und ihre Lösungen zu verschiedenen Dispatching-Aufgaben vor.

 

 1) Einführungsbeispiel

Dieses Video zeigt die grundsätzliche Problemstellung im Dispatching. Der Input für den Dispatch-Algorithmus besteht aus:

  1. Dem Netzwerk. D.h. einem Graphen mit Knoten und Verbindungen.
  2. Die Position jedes Zuges zur Startzeit.
  3. Das Ziel jeden Zuges. Im Video möchte jeder Zug zu dem Knoten fahren, der die Flagge mit der gleichen Farbe wie der Zug hat.
  4. Die maximale Geschwindigkeit, die jeder Zug fahren kann.

Die Bedingungen, die eingehalten werden müssen, sind:

  1. Zu jedem Zeitpunkt darf maximal ein Zug auf einer Verbindungsstrecke fahren.
  2. Zu keinem Zeitpunkt dürfen zwei Züge sich auf denselben Knoten zu bewegen.

Das Ziel des Algorithmus ist es für jeden Zug eine Route mit zeitlichem Routenfahrplan zu erstellen, so dass obige Bedingungen erfüllt sind und jeder Zug möglichst schnell zu seinem Ziel kommt.

Das Anfangsbild im Video zeigt vieles, was den Input in den Algorithmus darstellt: Das Netzwerk, die Startpositionen der Züge, die Zielknoten der Züge.

Das Video im späteren Verlauf zeigt dann die errechnete Dispatch-Lösung des Algorithmus: nämlich wie die Züge im zeitlichen Verlauf fahren.

 

Schon alleine durch dieses Einführungsbeispiel-Video ist klar, dass ein Mensch auf eine solch gute Lösung nicht kommen würde. Die Aufgabenstellung ist für den Menschen einfach zu komplex. Vor allem die Vorstellung, wie die Züge im zeitlichen Verlauf fahren, ist für einen Menschen extrem schwierig. Der Algorithmus in Form einer Software kann das.

 

Der Algorithmus ist in der Lage viele weitere für das Train-Dispatching relevante Bedingungen zu berücksichtigen. Wie z.B. Overlap-conditions, Geschwindigkeitsdifferenz-Bedingungen, Kapazitätsbeschränkungen auf Gruppen von Fahrstraßen,  Blockierbedingungen resultierend durch Züge mit übergroßer Fracht, ..... 

 

Der Algorithmus basiert auf einer guten Modellierung als 0-1 linear integer programming Problem und die Lösung dieses Problems mit Hilfe von Heuristiken und Integer-Programming-Solvern.

 

2) Ein Tunnel-Beispiel

Im nächsten Beispiel geht es um das Zugnetzwerk im Bereich des Eurotunnel in einer  vierstündigen Periode. Gewöhnlich gibt es Einbahnstraßenverkehr im Tunnel. Um es interessanter zu machen, nehmen wir an, dass zwei Teilstrecken im Tunnel blockiert sind. Alle Züge in beide Richtungen müssen so geplant werden, dass sie durch den Flaschenhals im Tunnel gelangen, ohne den Verkehr in Gegenrichtung allzu sehr zu beeinträchtigen. Die Abfahrtszeiten der Züge sind aus einem realen Fahrplan vor ein paar Jahren entnommen. Shuttle-, Fracht- und Intercity-Züge werden durch unterschiedliche Farben visualisiert. Das Streckennetz ist geometrisch verzerrt dargestellt: In der Realität ist der Tunnelbereich (circa 40km) viel länger im Vergleich zu den Bahnhofsbereichen (jeweils circa 1 bis 2 km) auf der englischen und französischen Seite.

Die Bedingungen sind sehr änlich zu denen im Einführungsbeispiel, aber zusätzlich kommen noch Sicherheitsabstands-Bedingungen sowie Geschwindigkeitsdifferenz-Bedingungen hinzu.

 

3) Ein Rangier-Beispiel

Das nächste Video zeigt die Lösung des Dispatch-Algorithmus angewendet auf ein Rangier-Problem: Züge sind hier Lokomotiven, die jederzeit ihre Fahrtrichtung ändern können. Die roten Lokomotiven wollen zur roten Flagge, die blauen Lokomotiven zur blauen Flagge. Die Startpositionen der Züge sind so, dass sich rote und blaue Lokomotiven jeweils den Weg versperren. Zu jedem Zeitpunkt darf maximal eine Lokomotive sich auf einem Streckenabschnitt befinden.

Der Algorithmus findet eine geniale Lösung, bei welcher nur zwei Lokomotiven den langen oberen Weg nehmen.

4) Ein Schachbrett-Beispiel

In diesem Beispiel ist das Netzwerk ein künstliches schachbrettförmiges Zugnetzwerk mit 80 Zügen, die auf engem Raum sich bewegen müssen. Jeder Zug hat eine vorgegebene Startposition und ein vorgegebenes Ziel. Diese Informationen sind Teil des Inputs zum Algorithmus. Außerdem werden folgende Bedingungen modelliert und mitberücksichtigt:

  1. Auf jeder Teilstrecke darf maximal ein Zug zu jedem Zeitpunkt sein.
  2. Auf Diagonalen, die sich kreuzen, darf zu jedem Zeitpunkt maximal ein Zug sich befinden.
  3. Zu keinem Zeitpunkt dürfen sich zwei Züge auf den gleichen Knoten zu bewegen.
  4. An Abzweigungen dürfen Züge nur solche nehmen, so dass sich die Zugbewegungsrichtung um weniger als 90 Grad verändert.

Das Ziel des Algorithmus ist es, die Summe der Verzögerungen aller Züge zu minimieren.

 

Dies ist ein künstlich sehr schwierig gemachtes Dispatch-Problem. Denn viele Züge müssen sich auf engem Raum bewegen. Je dichter der Verkehr desto schwieriger ist das Problem. Dies ist ein sehr schwieriges kombinatorisches Problem. Das Problem wird gelöst, indem das Netzwerk in Teilnetzwerke aufgeteilt wird. Diese Unterteilung zu bewerkstelligen, ist jedoch algorithmisch sehr schwierig, denn auch an den Grenzen der Teilnetzwerke müssen die obigen Bedingungen sicher gestellt werden. Jedoch kann man verschiedene Teilnetzwerke zum Teil parallel bearbeiten.

Der Algorithmus ist jedoch in der Lage, viel größere Probleme zu lösen. Hier nun ein gleichartiges Beispiel mit 1000 Zügen.

5) Fluglotsen-Beispiel

Dieses Video zeigt ein Fluglotsenbeispiel eines Luftraumes, in welchem die Fahrstraßen ebenfalls schachbrettartig angelegt sind. Es ist ein künstliches Beispiel. Jedes Flugzeug hat eine vorgegebene Zeit und Stelle, an welcher es den Luftraum betritt, sowie ein vorgegebenes Ziel, an welchem das Flugzeug den Luftraum verlassen möchte. Die Flugzeuge durchfliegen also den Luftraum.

 

Es gibt drei mögliche Flugebenen übereinander: die rote Flugebene ist die unterste, darüber ist die grüne, und die oberste Flugebene ist blau. Ein Flugzeug nimmt immer die Farbe der Flugebene an, auf welcher es sich gerade befindet. Wenn ein Flugzeug die Flugebene gerade wechselt, so nimmt der hintere Teil des Flugzeuges die Farbe an der Ebene, woher es kommt, und der vordere Teil die Farbe an der Ebene, zu welcher es fliegt. Das Netzwerk ist also ein dreidimensionales schachbrettartiges mit drei Ebenen. Die Bedingungen, welche der Algorithmus berücksichtigt, sind:

  1. Innerhalb eines Würfels im Netzwerk darf zu jedem Zeitpunkt maximal ein Flugzeug sich befinden. Jedoch auf sich gegenüberliegenden Seiten eines Würfels dürfen sich zwei Flugzeuge bewegen, jedes auf einer der Seiten.
  2. Zu keinem Zeitpunkt dürfen zwei Flugzeuge sich auf denselben Knoten zu bewegen.
  3. Flugzeuge dürfen keine scharfen Kurven fliegen.  D.h. in ebener Richtung, wie im Video dargestellt, ist maximal eine 45 Grad Kurve erlaubt. Flugrichtungen vertikal nach oben oder unten sind natürlich auch nicht erlaubt.

Diese Bedingungen implizieren, dass wenn sich zwei Flugzeuge im Video kreuzen, so müssen sie auf unterschiedlichen Ebenen fliegen, also im Video verschiedenfarbig dargestellt sein.