TU Berlin

FG Kombinatorische Optimierung und Graphenalgorithmen2005

COGA 5-Wheel

Inhalt

zur Navigation

Preprints 2005

A Cut-based Heuristic to Produce Almost Feasible Periodic Railway Timetables
Zitatschlüssel Report-006-2005
Autor Christian Liebchen
Jahr 2005
Nummer 006
Notiz In Proceedings of WEA 2005, Springer-Verlag LNCS 3503
Institution Technische Universität Berlin, Institut für Mathematik
Zusammenfassung We consider the problem of satisfying the maximum number of constraints of an instance of the Periodic Event Scheduling Problem (PESP). This is a key issue in periodic railway timetable construction, and has many other applications, e.g. for traffic light scheduling. We generalize two (in-) approximability results, which are known for MAXIMUM-k-COLORABLE-SUBGRAPH. Moreover, we present a deterministic combinatorial polynomial time algorithm. Its output violates only very few constraints for five real-world instances.
Link zur Publikation Download Bibtex Eintrag

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe