Integration der Revisionfahrten in der Wagenumlaufplanung

Raphael Richli, Semesterarbeit, Herbst 2008

Supervisor: Gabrio Caimi, Marco Laumanns

Keywords:
Umlaufplanung, Revisionen, Multicommodity Flow, MIP, Guthabenfunktion

Zusammenfassung

Um einen Fahrplan betreiben zu können, braucht eine Bahngesellschaft einen Wagenumlaufplan, der bestimmt, welche Zugkompositionen wann und wo verkehren. Dieser Umlaufplan wird noch immer zu einem grossen Teil manuell erstellt. Die Firma SMA und Partner AG hat eine Software entwickelt, die diese Arbeit vereinfacht. Dies geschieht unter anderem dadurch, dass eine Initiallösung für einen gegebenen Fahrplan automatisch erstellt werden kann, welche aber noch keine Revisionsfahrten für die Zugskompositionen beinhaltet.

Das Ziel dieser Arbeit besteht darin, Revisionsarbeiten von Zugskompositionen schon bei der Umlaufplanung zu berücksichtigen und in den Umlaufplan zu integrieren. Dafür wird ein Modellgraph entwickelt, wo jeder Knoten eine zeitliche und eine örtliche Komponente hat und jede Kante einer zulässigen Verbindung zwischen zwei Knoten entspricht. Ein (zyklischer) Fluss in diesem Graphen entspricht dann einen Umlauf für eine vorgegebene Anzahl von Kompositionen. Der Bedarf an Revision von jeder Komposition wird durch die Einführung eines Knotenpotentials abgebildet. Da jede Komposition einen unterschiedlichen Revisionsbedarf hat, muss jede einzelne Komposition separat modelliert werden, was in einem sogenannten Multicommodity Flow Modell beschrieben wird. Ziel ist es, einen Umlauf zu finden, welcher die Leerfahrten und/oder die Anzahl benötigter Revisionen minimiert. Dafür wird das Problem als gemischt-ganzzahliges lineares Programm beschrieben, welches mit einem kommerziellen Solver gelöst wird.

Resultate mit realen Instanzen mittlerer Grösse, die von SMA bereitgestellt wurden, zeigen, dass eine solche Integration der Revisionsarbeiten schon bei der Wagenumlaufplanung durchaus möglich ist. Im Vergleich zum Modell ohne Revisionen ist das Modell mit Revisonen allerdings deutlich grösser und nimmt mehr Zeit in Anspruch, um gelöst zu werden. Es bleibt die offene Frage, ob sich auch grosse Instanzen mit diesem Modell in vernünftige Zeit lösen lassen.