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.2021.6
URN: urn:nbn:de:0030-drops-148753
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14875/
Go to the corresponding OASIcs Volume Portal

Goerigk, Marc ; Schöbel, Anita ; Spühler, Felix

A Phase I Simplex Method for Finding Feasible Periodic Timetables

pdf-format:
OASIcs-ATMOS-2021-6.pdf (0.8 MB)

Abstract

The periodic event scheduling problem (PESP) with various applications in timetabling or traffic light scheduling is known to be challenging to solve. In general, it is already NP-hard to find a feasible solution. However, depending on the structure of the underlying network and the values of lower and upper bounds on activities, this might also be an easy task.
In this paper we make use of this property and suggest phase I approaches (similar to the well-known phase I of the simplex algorithm) to find a feasible solution to PESP. Given an instance of PESP, we define an auxiliary instance for which a feasible solution can easily be constructed, and whose solution determines a feasible solution of the original instance or proves that the original instance is not feasible. We investigate different possibilities on how such an auxiliary instance can be defined theoretically and experimentally. Furthermore, in our experiments we compare different solution approaches for PESP and their behavior in the phase I approach. The results show that this approach can be especially helpful if the instance admits a feasible solution, while it is generally outperformed by classic mixed-integer programming formulations when the instance is infeasible.

BibTeX - Entry

@InProceedings{goerigk_et_al:OASIcs.ATMOS.2021.6,
  author =	{Goerigk, Marc and Sch\"{o}bel, Anita and Sp\"{u}hler, Felix},
  title =	{{A Phase I Simplex Method for Finding Feasible Periodic Timetables}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{6:1--6:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14875},
  URN =		{urn:nbn:de:0030-drops-148753},
  doi =		{10.4230/OASIcs.ATMOS.2021.6},
  annote =	{Keywords: train timetable optimization, periodic event scheduling problem, modulo simplex}
}

Keywords: train timetable optimization, periodic event scheduling problem, modulo simplex
Collection: 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)
Issue Date: 2021
Date of publication: 27.09.2021

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