Rolling Stock Assignment

Semesterarbeit in Theoretischer Informatik
Marco Nef; Prof. Dr. P. Widmayer, ETH Zürich
WS 2000/2001

Zusammenfassung

Das Rolling Stock Assignment ist die Problemstellung der Zuteilung von Rollmaterial auf die durch einen vorgegebenen Fahrplan definierten Fahrten eines Bahnsystems.

In dieser Semesterarbeit werden schrittweise Algorithmen für immer komplexere Instanzen dieses in NP enthaltenen Problems hergeleitet und implementiert. Zuerst wird für eine einfache Bahnlinie eine Lösung gesucht, welche die minimale Anzahl Wagen benötigt. Später werden eine Kostenfunktion und Zwischendepots zur Bahnlinie hinzugefügt. Die Lösung des Rolling Stock Assignment wird dabei auf die Suche nach dem kürzesten Weg in einem Graphen reduziert.

Bild: Fotoservice SBB

Demonstration der Algorithmen

Hinweis: Für die Algorithmen wird ein neues Browser-Fenster geöffnet.

Download

Semesterarbeit als PDF-Dokument   (477kB)

Um das Dokument öffnen zu können, wird der Adobe Reader benötigt, der unter folgender Adresse gratis heruntergeladen werden kann: www.adobe.com