Jakob, Ricardo, (ehem.) Maja

Es wird folgendes Szenario zugrunde gelegt: n Züge mit unterschiedlichen Parametern (V_avg, Priorität,…) müssen in optimaler Reihenfolge auf ein Richtungsgleis zwischen Bahnhof A und Bahnhof B verteilt werden, sodass möglichst wenig Verspätung / Anschlussverluste entstehen, insbesondere wenn Züge mit Verspätung eintreffen.

Computer (optional)

Datensätze zu: Geschwindigkeiten/Durchschnittsgeschwindigkeiten verschiedener Zugkategorien, Prioritäten, Fahrgastzahlen, Taktdichten, Blockstellen, Zugfolgezeiten.

Grundlagen zur diskreten Optimierung

Wir befassen uns mit einem logistischen Problem, das seinen Ursprung in der Eisenbahn hat: Nach einer Streckensperrung sollen die im Bahnhof gestauten Züge in optimaler Reihenfolge ausgesandt werden. Es wird nur ein Richtungsgleis ohne Ausweichstellen betrachtet.

Der einzige entscheidende Faktor ist die Verspätung der Reisenden bzw. Güter. Auf diese nehmen die geplante Ankunftszeit (wie straff ist der Fahrplan gestrickt), ggf. Umsteigezeiten und -zahlen (wie viele Personen möchten in welche Züge umsteigen), die Zuggeschwindigkeit, der minimale Zugfolgeabstand und die Länge der Strecke bis zur nächsten Ausweichmöglichkeit Einfluss.

All diese Eigenschaften sind im Programm frei wählbar

Der Grundaufbau ist so konzipiert, dass einzelne Programmteile reibungslos ausgetauscht werden können:

• Masterdatei, sie ruft die Unterprogramme auf. In ihr werden sämtliche Eigenschaften für Strecke usw. Eingetragen.
• Die Züge sind samt ihrer Eigenschaften wie Geschwindigkeit, Ort usw. Wörterbücher, die in einer Liste gespeichert sind, in einer Textdatei hinterlegt. Dies hat den Nutzen, dass eine eindeutige Reihenfolge festgelegt werden kann, ohne weitere Hilfsmittel zu verwenden.
• Ein Einleseprogramm liest nun diese Textdatei ein und stellt die daraus gelesene Zugliste dem Master zur Verfügung.
• Dieser ruft dann die vom Benutzer ausgewählten Algorithmen auf, stoppt die Zeit und wertet die Ergebnisse aus.
• Die Grundlage der Algorithmen bildet das Simulationsprogramm, welches in zwei Varianten existiert.

Wichtig für die Algorithmen ist folgendes Modell zur Vorstellung: Alle Möglichen Lösungen (=ausgewertete Zugreihenfolgen) befinden sich auf einer Ebene. Nun wird je nach „Score“ der Auswertung diese Lösungen angehoben, es entsteht eine Hügellandschaft. Ziel eines jeden Algorithmus ist es nun, das „tiefste Tal“, also den geringsten Verspätungswert zu erreichen, und zwar in möglichst wenigen Schritten.

Der Algorithmus probiert alle Möglichen Kombinationen nacheinander aus und merkt sich immer die jeweils beste. Diese Methode garantiert eine optimale Lösung, da es aber n! Kombinationen bei n Zügen gibt, steigt die Laufzeit sehr schnell in nicht mehr sinnvolle Dimensionen (Auszug aus Protokoll:)

1. 3 Züge: 0m00,073s
2. 6 Züge: 0m12,757s
3. 7 Züge: 2m04,064s
4. 8 Züge: 20m55,436s

Der Code ist sehr simpel:

import itertools
import simulation
import auswertungsprogramm
 
zug1={"vavg":20,"vist":20,"abfahrt":0,"besetzung":100,"ankunftplan":0,"ankunft":-1,"status":0,"nummer":595,"ort":2000}
zug2={"vavg":30,"vist":30,"abfahrt":2,"besetzung":50,"ankunftplan":0,"ankunft":-1,"status":0,"nummer":123,"ort":0}
zug3={"vavg":30,"vist":20,"abfahrt":4,"besetzung":20,"ankunftplan":0,"ankunft":-1,"status":0,"nummer":987,"ort":0}
 
zuege = [zug1, zug2, zug3]
 
 
def bruteforce(zugliste):
    #minimumzeit = auswertungsprogramm.auswertung(list(itertools.permutations(zugliste)[1]))
    for perm in itertools.permutations(zugliste): # Permutationen werden ermittelt
        temp = simulation.simuliere(list(perm)) # Permutationen werden gefahren
 
 
bruteforce(zuege)   

Dieser Algorithmus wählt zufällig zwei Züge aus der Liste, vertauscht beide und testet die neu gewonnene Reihenfolge auf eine Verringerung der Verspätung. Die Laufzeit hängt lediglich davon ab, wie oft man das Programm tauschen lässt. Die Tauschzahl wird beim Programmaufruf übergeben. Alternativ könnte man auch eine Methode implementieren, die das Tauschverfahren bei einer Verbesserung um x Prozent beendet. Quelltext

Ähnlich dem obigen Algorithmus, jedoch wird eine 3er-Serie gewählt, die beste Reihenfolge der 3 Züge berechnet und dann wieder einsortiert. Hiermit lassen sich Kombinationen erzielen, die mit dem 2er-Algorithmus nie erreicht werden könnten. Aus kuriosen Gründen funktioniert dieser Algorithmus jedoch nicht, näheres im Protokoll. Quelltext

Wir erinnern uns zurück an das Modell der Landschaft: Der Algorithmus arbeitet nun ähnlich dem 2er-Tauschalgorithmus, mit einer entscheidenden Änderung: Ähnlich des Abkühlens von Metallen oder Kristallisierung ist es dem Algorithmus möglich, auch Schritte „bergauf“ zu Springen um einem Möglichen lokalen Minimum zu entkommen. Die Sprungwahrscheinlichkeit ist abhängig von der „Temperatur“ des Systems, die abhängig von der Laufzeit ist. Die Geschwindigkeit und Form dieser Abkühlung ist nun imminent wichtig für den Erfolg des Annealing-Algorithmus. [Details Annealing, Abkühlen usw. einfügen] Quelltext

Klick: Protokoll td