Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Bampas, Evangelos; Kaouri, Georgia; Lampis, Michael; Pagourtzis, Aris http://www.dagstuhl.de/oasics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-6841
URL:

; ; ;

Periodic Metro Scheduling

pdf-format:


Abstract

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.

BibTeX - Entry

@InProceedings{bampas_et_al:OASIcs:2006:684,
  author =	{Evangelos Bampas and Georgia Kaouri and Michael Lampis and Aris Pagourtzis},
  title =	{{Periodic Metro Scheduling}},
  booktitle =	{6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06)},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-01-9},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{5},
  editor =	{Riko Jacob and Matthias M{\"u}ller-Hannemann},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/684},
  URN =		{urn:nbn:de:0030-drops-6841},
  doi =		{http://dx.doi.org/10.4230/OASIcs.ATMOS.2006.684},
  annote =	{Keywords: Train scheduling, path coloring, delay-tolerant scheduling, periodic timetabling}
}

Keywords: Train scheduling, path coloring, delay-tolerant scheduling, periodic timetabling
Seminar: 6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06)
Issue date: 2006
Date of publication: 2006


DROPS-Home | Fulltext Search | Imprint Published by LZI