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.
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 |