• search hit 9 of 10
Back to Result List

A Cut-based Heuristic to Produce Almost Feasible Periodic Railway Timetables

Please always quote using this URN:urn:nbn:de:0296-matheon-2297
  • 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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Christian Liebchen
URN:urn:nbn:de:0296-matheon-2297
Referee:Rolf H. Möhring
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2005/07/03
Release Date:2005/02/28
Institute:Technische Universität Berlin
Preprint Number:222
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.