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
Additional Services
| 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 |
