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

In Proceedings of WEA 2005, Springer LNCS 3503

Periodic Railway Timetable Optimization, Approximation

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 as [PDF] [ps.gz]