Teil eines Fahplans

Ein Bildschirm des Systems

Die Forschungsabteilung der Siemens AG hat f? die Deutsche Bundesbahn den Prototypen eines Scheduling Systems geschrieben, der es erm?licht, t?lich neue, sich ?dernde Fahrpl?e f? einen grossen deutschen Hauptbahnhof zu erstellen.

Als Versuchsbahnhof wurde ein Hauptbahnhof mit 14 Gleisen und 6 Besucher- plattformen gew?lt, der eine durchschnittliche Leistung von 68 Z?en pro Stunde hat.

Das Computersystem reagiert auf Echtzeit-Scheduling-Probleme, die z.B. dadurch entstehen, dass Z?e Versp?ung haben oder es k?nen Wartungs- arbeiten an Gleisen oder Bahnsteigen die Schliessung dieser Bereiche f? bestimmte Stunden erfordern.

Es wird ein neuer Fahrplan mit berichtigten Ankunftszeiten generiert, wobei die Anderungen zum alten Fahrplan minimiert werden sollen, die sich durch die Verschiebungen ergeben. Der Prototyp arbeitet basierend auf der Menge der aktuellen Daten unter Echtzeitbedingungen und beschreibt das Eisenbahnnetz mit den geplanten Zeiten.

Interaktiv kann dem Benutzer ausserdem die M?lichlkeit gegeben werden, das System so abzu?dern, dass Anschl?se zu anderen Bahnh?en priorisiert werden, bzw. nicht geplante Z?e in das System eingepasst und mit Priorit?en versehen werden k?nen.

Das obige Bild zeigt einen Ausschnitt aus dem Fahrplan des Bahnhofs. Die Nummern der Bahngleise mit den dazugeh?igen Bahnsteige sind auf der X-Achse dargestellt. Zwei zus?zliche Gleise sind markiert (40 und 80), die es erlauben, dass Z?e den Bahnhof ohne Halt passieren. Die Zeit wurde an der Y-Achse dargestellt. Das Bild zeigt lediglich einen kleineren Ausschnitt des Fahrplanes, als er tats?hlich auf einem grossen Bildschirm zur Verf?ung steht.

Die Z?e k?nen auf jedem Gleis von einer der beiden Richtungen kommen, was durch die Zeichen "von rechts nach links" oder umgekehrt dargestellt ist; ausserdem hat jeder Zug einen bestimmten Code. Bekannte Versp?ungen von bestimmten Z?en sind hinter der Ankunftszeit der Z?e vermerkt.

In der Realit? sind drei Bahnhoftangestellte verantwortlich f? die Verteilung der ankommenden Z?e auf Gleise und Bahnsteige. Ihre Aufgabe ist es erstens, die Wege der Bahnbenutzer, die durch Umdisponierung entstehen, zu minimieren, zweitens die Priorit?en der Z?e festzulegen und drittens alle Sicherheitsrichtlinien bei Umdispositionen einzuhalten.

Das Computersystem stellt alle Aspekte des Bahnhofs dar und soll den Verant- wortlichen zur Unterst?zung Ihrer Arbeit dienen. Durch die Verwendung von Constraints, sucht das System nach einer besonders guten L?ung.

Viele vordefinierte Regeln und Sicherheitsbestimmungen definieren feste Constraints, wie z.B. die Zeit, die eine Kreuzung bzw. Weiche frei bleiben muss, um sicher zu gehen, dass der Zug Sie auch wirklich passiert hat. Diese festen Einschr?kungen darf das neue computergest?zte System nicht aufheben.

Andere, eher flexible Einschr?kungen spezifizieren z.B. die minimale Zeit, die ein Zug an einer Benutzerplattform anhalten soll, die jedoch k?zer ist, als die im Fahrplan festgelegte Zeit.

Wenn ein regionaler Zug Versp?ung hat, ?erf?rt er auch versp?et Weichen zu seinem vorgeplanten Bahnsteig; aus diesem Grund k?nen andere Z?e mit einer geringeren Priorit? gezwungen sein, vor dem Bahnhof diesen Zug abzuwarten, was wiederum zu Versp?ungen bei diesen Z?en f?ren kann. Sollte ein lokaler Zug eine grosse Versp?ung haben, kann dies dazu f?ren, dass der Anschluss an einen regionalen Zug nicht mehr geschafft werden kann. Der Fahrplan selbst gibt Anschlussverbindungen an, die von den Passagieren erreicht werden k?nen.

Das System erstellt den neuen Fahrplan basierend auf den Versp?ungen der Z?e und den Zus?zen des zust?digen Personals. Diese Zeit- und Kapazit?s- engp?se begrenzen den Fahrplan; das System muss diese durch Zeitersparnisse durch k?zere Stops der Z?e im Bahnhof, durch Anhalten anderer Z?e oder im schlechtesten Fall durch Umleitung der Passagiere auf einen anderen Bahnsteig kompensieren. Hierbei muss eine Umleitung auf die andere Seite des gleichen Bahnsteigs vor allen anderen M?lichkeiten priorisiert werden.

Teil eines berichtigten Fahplans

Ein Bildschirm des Systems

Sicherlich gibt es f? Probleme dieser Art nicht eine optimale L?ung; daher wurde ein interaktives System geschrieben, dass auch auf eher subjektive Optimierungsgr?de reagieren kann. Es zeigt die Zeiten an, die ein Zug an einem Bahnsteig h?t, damit aus- und eingestiegen werden kann. Wenn der Fahrplan korrigiert werden musste (siehe oben), werden die Umdispositionen rechts von der urspr?glichen Graphik dargestellt und entsprechend der Schwere ihrer Auswirkungen farbig gekennzeichnet.

Der f? den Fahrplan Zust?dige kann dann trotzdem bestimmen, das ein versp?eter Zug auf dem urspr?glich bestimmten Gleis einf?rt, weil z.B. auf dem entsprechenden Bahnsteig eine ganze Schulklasse oder ein ?tere Mann wartet und das System kann damit erneut gestartet werden. Dieser neue Start ben?igt weniger als 20 Sekunden auf einer kleinen UNIX Workstation oder einem PC, was ausreichend ist, um die Bed?fnisse eines grossen, oft frequentierten Bahnhofs unter Echtzeitdruck abzudecken.

Im Ganzen umfasst das System 15 000 lines of code, die in 2 Mann-Jahren entwicklet wurden. Ungef?r 1/3 dieses Codes sind Motif basierte Graphiken, die ebenfalls in Prolog geschrieben wurden. Das Constraint Technologie Paket von IF/Prolog wurde dazu benutzt, das Problem in einer lesbaren Form bequem und effektiv zu formulieren. IF/Prolog erlaubt den Entwicklern, ein Problem mit Hilfe von Regeln und Einschr?kungen zu beschreiben, anstatt gezwungen zu werden, sich auf das Design einer L?ungsprozedur zu konzentrieren, die nicht alle zuk?ftig n?igen Kriterien umfasst.

IF/Prolog vereinigt die unterschiedlichsten Datentypen und spezifiziert Regeln und Einschr?kungen in einer lesbaren und modifizierbaren Form. Die L?ung mit der Standard Constraint Technologie begrenzt das Problem auf eine handhabbaren Anzahl von Alternativen, die dann durch einen zust?digen Beamten ausgew?lt oder angepasst werden k?nen. Dies f?rt zu einer Entlastung des Personals von der m?samen Kleinarbeit hin zu anspruchsvolleren Entscheidungen, die das System nicht treffen kann oder soll.

Hardware

Software

IF/Prolog 5.0 mit: Constraint Technologie Paket OSF/Motif Programmier-Schnittstelle