Efficient and complete conflict graph generation schemes for railroad scheduling

Abstract

Railway networks already play a major role in today's transportation of passengers and goods. With the growing efforts to protect the environment and climate, its role is likely to become even more important in the near future. To handle this appropriately we need a way to schedule trains in a fast and efficient way. A recent publication for computer network scheduling made conflict graphs in their field viable, by building it up dynamically till a solution can be found. We to took this idea and implemented it for joint routing and railroad scheduling. We added a Potential Conflict mechanism to their algorithm to improve on its performance and compare different strategies to find the best way to extend the conflict graph for our domain. The evaluation shows that with those two adaptions we are able to scale the conflict graph solution from a single train station to the German railroad network.

Schienen Netzwerke spielen bereits heute eine große Rolle beim Transport von Personen und Gütern. Und mit den wachsenden Anstrengungen die Umwelt und das Klima zu schützen wird diese Rolle in naher Zukunft warscheinlich noch wichtiger. Um dem gerecht zu werden brauchen wir eine schnelle und effiziente Methode Fahrpläne zu erstellen. Eine neue Publikation im Bereich der Computer Netzwerke verwendet Conflict Graphs, indem diese dynamisch aufgebaut werden biseine Lösung enthalten ist. Wir haben diese Idee auf das Streckenführungs- und Ablaufkoordinierungsproblem für Züge übertragen. Um die Performance weiter zu verbessern haben wir außerdem den Algorithmus um den Potential Conflict Mechanisus erweitert. Wir haben darüber hinaus verschiedene Strategien erprobt,um den effizientesten Weg zu finden, den Graphen für dieses Problem aufzubauen. Unsere Evaluation zeigt, dass wir mit diesen beiden Anpassungen nicht mehr nur den Verkehr für einzelne Bahnhöfe, sondern für Länder der Größe Deutschlands planen können.