1 Search Results for "Spühler, Felix"

Document
DOI: 10.4230/OASIcs.ATMOS.2021.6
A Phase I Simplex Method for Finding Feasible Periodic Timetables

Authors: Marc Goerigk, Anita Schöbel, and Felix Spühler

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

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.
Cite as

Marc Goerigk, Anita Schöbel, and Felix Spühler. A Phase I Simplex Method for Finding Feasible Periodic Timetables. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@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-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.6},
  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}
}
  • Refine by Author
  • 1 Goerigk, Marc
  • 1 Schöbel, Anita
  • 1 Spühler, Felix

  • Refine by Classification
  • 1 Applied computing → Operations research
  • 1 Theory of computation → Network optimization

  • Refine by Keyword
  • 1 modulo simplex
  • 1 periodic event scheduling problem
  • 1 train timetable optimization

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact