License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2023.7
URN: urn:nbn:de:0030-drops-187689
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18768/
Go to the corresponding OASIcs Volume Portal

Bortoletto, Enrico ; Lindner, Niels ; Masing, Berenike

Periodic Timetabling with Cyclic Order Constraints

pdf-format:
OASIcs-ATMOS-2023-7.pdf (0.7 MB)

Abstract

Periodic timetabling for highly utilized railway networks is a demanding challenge. We formulate an infrastructure-aware extension of the Periodic Event Scheduling Problem (PESP) by requiring that not only events, but also activities using the same infrastructure must be separated by a minimum headway time. This extended problem can be modeled as a mixed-integer program by adding constraints on the sum of periodic tensions along certain cycles, so that it shares some structural properties with standard PESP. We further refine this problem by fixing cyclic orders at each infrastructure element. Although the computational complexity remains unchanged, the mixed-integer programming model then becomes much smaller. Furthermore, we also discuss how to find a minimal subset of infrastructure elements whose cyclic order already prescribes the order for the remaining parts of the network, and how cyclic order information can be modeled in a mixed-integer programming context. In practice, we evaluate the impact of cyclic orders on a real-world instance on the S-Bahn Berlin network, which turns out to be computationally fruitful.

BibTeX - Entry

@InProceedings{bortoletto_et_al:OASIcs.ATMOS.2023.7,
  author =	{Bortoletto, Enrico and Lindner, Niels and Masing, Berenike},
  title =	{{Periodic Timetabling with Cyclic Order Constraints}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{7:1--7:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18768},
  URN =		{urn:nbn:de:0030-drops-187689},
  doi =		{10.4230/OASIcs.ATMOS.2023.7},
  annote =	{Keywords: Periodic Timetabling, Railway Timetabling, Periodic Event Scheduling Problem, Cyclic Orders, Mixed-Integer Programming}
}

Keywords: Periodic Timetabling, Railway Timetabling, Periodic Event Scheduling Problem, Cyclic Orders, Mixed-Integer Programming
Collection: 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)
Issue Date: 2023
Date of publication: 31.08.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI