Periodic Metro Scheduling

Bampas, Evangelos; Kaouri, Georgia; Lampis, Michael; Pagourtzis, Aris

doi:10.4230/OASIcs.ATMOS.2006.684

Document

Periodic Metro Scheduling

Authors Evangelos Bampas, Georgia Kaouri, Michael Lampis, Aris Pagourtzis

Part of: Volume: 6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06) (ATMOS 2006)
Part of: Series: Open Access Series in Informatics (OASIcs)
Part of: Conference: Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2006-08-29

PDF

File

PDF

OASIcs.ATMOS.2006.684.pdf

Filesize: 273 kB
15 pages

Document Identifiers

DOI: 10.4230/OASIcs.ATMOS.2006.684
URN: urn:nbn:de:0030-drops-6841

Subject Classification

Keywords

Train scheduling
path coloring
delay-tolerant scheduling
periodic timetabling

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get BibTex

Evangelos Bampas, Georgia Kaouri, Michael Lampis, and Aris Pagourtzis. Periodic Metro Scheduling. In 6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06). Open Access Series in Informatics (OASIcs), Volume 5, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006) https://doi.org/10.4230/OASIcs.ATMOS.2006.684

Author Details

Evangelos Bampas

Georgia Kaouri

Michael Lampis

Aris Pagourtzis

Any Issues?

Feedback on the Current Page

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail