A Phase I Simplex Method for Finding Feasible Periodic Timetables

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



PDF
Thumbnail PDF

File

OASIcs.ATMOS.2021.6.pdf
  • Filesize: 0.84 MB
  • 13 pages

Document Identifiers

Author Details

Marc Goerigk
  • Network and Data Science Management, Universität Siegen, Germany
Anita Schöbel
  • Department of Mathematics, TU Kaiserslautern, Germany
  • Fraunhofer-Institut für Techno- und Wirtschaftsmathematik ITWM, Kaiserslautern, Germany
Felix Spühler
  • Business Information Systems, TU Braunschweig, Germany

Cite AsGet BibTex

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)
https://doi.org/10.4230/OASIcs.ATMOS.2021.6

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.

Subject Classification

ACM Subject Classification
  • Applied computing → Operations research
  • Theory of computation → Network optimization
Keywords
  • train timetable optimization
  • periodic event scheduling problem
  • modulo simplex

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Ralf Borndörfer, Heide Hoppmann, Marika Karbstein, and Niels Lindner. Separation of cycle inequalities in periodic timetabling. Discrete Optimization, 35:100552, 2020. Google Scholar
  2. Ralf Borndörfer, Niels Lindner, and Sarah Roth. A concurrent approach to the periodic event scheduling problem. Journal of Rail Transport Planning & Management, 15:100175, 2020. Google Scholar
  3. Elizabeth D Dolan and Jorge J Moré. Benchmarking optimization software with performance profiles. Mathematical programming, 91(2):201-213, 2002. Google Scholar
  4. Marc Goerigk and Christian Liebchen. An improved algorithm for the periodic timetabling problem. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  5. Marc Goerigk, Michael Schachtebeck, and Anita Schöbel. Evaluating line concepts using travel times and robustness: Simulations with the lintim toolbox. Public Transport, 5(3):267-284, 2013. Google Scholar
  6. Marc Goerigk and Anita Schöbel. Engineering the modulo network simplex heuristic for the periodic timetabling problem. In International Symposium on Experimental Algorithms, pages 181-192. Springer, 2011. Google Scholar
  7. Marc Goerigk and Anita Schöbel. Improving the modulo simplex algorithm for large-scale periodic timetabling. Computers & Operations Research, 40(5):1363-1370, 2013. Google Scholar
  8. Peter Großmann, Steffen Hölldobler, Norbert Manthey, Karl Nachtigall, Jens Opitz, and Peter Steinke. Solving periodic event scheduling problems with sat. In International conference on industrial, engineering and other applications of applied intelligent systems, pages 166-175. Springer, 2012. Google Scholar
  9. Sabrina Herrigel, Marco Laumanns, Jacint Szabo, and Ulrich Weidmann. Periodic railway timetabling with sequential decomposition in the pesp model. Journal of rail transport planning & management, 8(3-4):167-183, 2018. Google Scholar
  10. Leo Kroon, Dennis Huisman, Erwin Abbink, Pieter-Jan Fioole, Matteo Fischetti, Gábor Maróti, Alexander Schrijver, Adri Steenbeek, and Roelof Ybema. The new dutch timetable: The or revolution. Interfaces, 39(1):6-17, 2009. Google Scholar
  11. Christian Liebchen. Periodic Timetable Optimization in Public Transport. dissertation.de - Verlag im Internet, Berlin, 2006. Google Scholar
  12. Christian Liebchen. Periodic timetable optimization in public transport. In Operations research proceedings 2006, pages 29-36. Springer, 2007. Google Scholar
  13. Christian Liebchen. The first optimized railway timetable in practice. Transportation Science, 42(4):420-435, 2008. Google Scholar
  14. Niels Lindner and Julian Reisch. Parameterized complexity of periodic timetabling. Technical Report ZIB Report 20-15, Zuse Institute Berlin, 2020. Google Scholar
  15. Karl Nachtigall and Jens Opitz. Solving periodic timetable optimisation problems by modulo simplex calculations. In 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2008. Google Scholar
  16. Jens Opitz. Automatische Erzeugung und Optimierung von Taktfahrplänen in Schienenverkehrsnetzen, volume 1. Springer, 2009. Google Scholar
  17. Julius Pätzold and Anita Schöbel. A matching approach for periodic timetabling. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  18. Philine Schiewe and Anita Schöbel. Periodic timetabling with integrated routing: Towards applicable approaches. Transportation Science, 54(6):1714-1731, 2020. Google Scholar
  19. Anita Schöbel, Alexander Schiewe, Sebastian Albert, Julius Pätzold, Philine Schiewe, and Jochen Schulz. Lintim: An integrated environment for mathematical public transport optimization. Technical report, Documentation. Technical Report 2020.02, 2020. Google Scholar
  20. Paolo Serafini and Walter Ukovich. A mathematical model for periodic scheduling problems. SIAM Journal on Discrete Mathematics, 2(4):550-581, 1989. Google Scholar
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