Dannenberg, Hartmut

Nr. 23 - Dannenberg, Hartmut

"Ordered-Search-Algorithmen zur rechnergestützten Disposition von Eisenbahnbetriebsabläufen"; Dissertation 05.07.1985

In dieser Arbeit wird die Entwicklung und Implementation des Dispositionsmodells DISPO beschrieben. Zunächst werden die Probleme bei der Lösung von Konfliktsituationen im Eisenbahnbetrieb und die bisherigen Ansätze für eine teil- bzw. vollautomatische Disposition analysiert. Neben dem Ziel, einen mit guter Qualität ablaufenden Betrieb zu gewährleisten, sind auch wirtschaftliche Faktoren für Einsatz und Erfolg solcher Systeme von hoher Bedeutung.

Es wird gezeigt, daß die Lösung von Konflikten im Eisenbahnbetrieb auf das Auffinden eines Weges in einem Suchbaum zurückgeführt werden kann. Zur Lösung solcher Aufgaben bietet sich die Verwendung eines Ordered-Search-Algorithmus an. Er kann folgendermaßen charakterisiert werden:

• Jedem Knoten (Teillösung) des Suchbaums wird eine Bewertung zugeordnet, die die Kosten eines Lösungsweges über diesen Knoten bis zu einem Zielknoten angibt.
• Die Wegesuche wird stets bei einem Knoten mit bester Bewertung fortgesetzt.

Ein Ordered-Search-Algorithmus erzeugt nur Knoten, die auf einem Optimalweg zur Lösung liegen. Da die Bewertungsfunk-tion häufig nicht bekannt, bzw. ebenso aufwendig zu bestimmen ist wie der Lösungsweg selbst, müssen Schätzungen für die Bewertung verwendet werden, wobei die Wirksamkeit und Optimalität des Algorithmus mit dem Nachweis einfacher Voraussetzungen für die Schätzfunktionen sichergestellt werden kann.

Im Hauptteil der Arbeit wird das Dispositionsmodell DISPO beschrieben. Es ist in der Lage, den Betriebsablauf in Eisenbahnnetzen zu steuern. Folgende Parameter kennzeichnen das System:

• Darstellung beliebiger Gleis- und Signalanlagen durch einen gerichteten, bewerteten Graphen.
• Fahrsimulation von Zügen mit individueller Vorgabe von Fahrwegen und Halten im Dispositionsbereich.
• Berücksichtigung von verschiedenen Zuggattungen.
• Bewertung jeder Zugfahrt durch eine Funktion der Verspätung; Bewertung eines Fahrplans durch die Summe der einzelnen Zugbewertungen.
• Optimierung des Betriebsablaufs bei Behinderungen durch einen Ordered-Search-Algorithmus zur Minimierung der Fahrplanbewertung.
• Verwendung verschiedener Lösungsstrategien zur Beseiti-gung von Behinderungen.
• Ausgabe umfangreicher Betriebsprotokolle.

Das System wurde auf den Anlagen des Regionalen Rechenzentrums für Niedersachsen implementiert und getestet. Es ergänzt das am Institut für Verkehrswesen, Eisenbahnbau und -betrieb der Universität Hannover entwickelte Simulations-modell SIMU V.

Das Modell DISPO kann mit geringem Aufwand in die rechnergestützte Zugüberwachung der Deutschen Bundesbahn integriert werden. Hierbei sollte jedoch aus Kostengründen zunächst nur eine teilautomatische Disposition angestrebt werden. Eine Konzeption für eine derartige praktische Anwendung wird in der Arbeit vorgestellt.

Weitere Anwendungsmöglichkeiten des Modells bieten sich bei der Fahrplankonstruktion und der Verbesserung von Simulationsverfahren für Betriebsuntersuchungen an. Außerdem sollten Forschungsarbeiten zur Bestimmung der mit vereinfachten Dispositionsverfahren erreichbaren Betriebsqualität durchgeführt werden, so daß der Dispositionsaufwand für spezielle Anwendungen verringert werden kann.