2026-07-22T17:55:21Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:684 2024-03-06T10:28:25Z ddc:004 open_access

Periodic Metro Scheduling Bampas, Evangelos Kaouri, Georgia Lampis, Michael Pagourtzis, Aris Train scheduling path coloring delay-tolerant scheduling periodic timetabling We introduce the { extsc{Periodic Metro Sched-ul-ing}} ({ extsc{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 ({ extsc{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 { extsc{Path Coloring}} problem, while others rely on techniques specially designed for the new problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Evangelos Bampas and Georgia Kaouri and Michael Lampis and Aris Pagourtzis 2006 Is Part Of OASIcs, Volume 5, 6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06) (2006) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2006.684 urn:nbn:de:0030-drops-6841 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2006.684 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode