Periodic Metro Scheduling

6th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems

Evangelos Bampas ; Georgia Kaouri ; Michael Lampis ; Aris Pagourtzis

Others  :  http://drops.dagstuhl.de/opus/volltexte/2006/684/pdf/06002.BampasEvangelos.Paper.684.pdf
PID  :  6974

来源: CEUR

【 摘 要 】

We introduce the Periodic Metro Scheduling (PMS) problem, which aims in generating a periodic timetable for a given set of routes and a given time period, in such a way that the minimum time distance between any two successive trains that pass from the same point of the network is maximized. This can be particularly useful in cases where trains use the same rail segment quite often, as happens in metropolitan rail networks.We present exact algorithms for PMS in chain and spider networks, and constant ratio approximation algorithms for ring networks and for a special class of tree networks. Some of our algorithms are based on a reduction to the Path Coloring problem, while others rely on techniques pecially designed for the new problem.