Document Open Access Logo

Determining All Integer Vertices of the PESP Polytope by Flipping Arcs

Authors Niels Lindner , Christian Liebchen

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2020.5.pdf
  • Filesize: 0.62 MB
  • 18 pages

Document Identifiers

Author Details

Niels Lindner
  • Zuse Institute Berlin, Germany
Christian Liebchen
  • Technical University of Applied Sciences Wildau, Germany

Funding

  • Lindner, Niels: Funded by Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy - The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689).

Cite AsGet BibTex

Niels Lindner and Christian Liebchen. Determining All Integer Vertices of the PESP Polytope by Flipping Arcs. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/OASIcs.ATMOS.2020.5

Abstract

We investigate polyhedral aspects of the Periodic Event Scheduling Problem (PESP), the mathematical basis for periodic timetabling problems in public transport. Flipping the orientation of arcs, we obtain a new class of valid inequalities, the flip inequalities, comprising both the known cycle and change-cycle inequalities. For a point of the LP relaxation, a violated flip inequality can be found in pseudo-polynomial time, and even in linear time for a spanning tree solution. Our main result is that the integer vertices of the polytope described by the flip inequalities are exactly the vertices of the PESP polytope, i.e., the convex hull of all feasible periodic slacks with corresponding modulo parameters. Moreover, we show that this flip polytope equals the PESP polytope in some special cases. On the computational side, we devise several heuristic approaches concerning the separation of cutting planes from flip inequalities. We finally present better dual bounds for the smallest and largest instance of the benchmarking library PESPlib.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorial optimization
  • Applied computing → Transportation
  • Theory of computation → Network optimization
Keywords
  • Periodic Event Scheduling Problem
  • Periodic Timetabling
  • Mixed Integer Programming

Metrics

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

References

  1. Tobias Achterberg, Thorsten Koch, and Alexander Martin. MIPLIB 2003. Oper. Res. Lett., 34(4):361-372, 2006. URL: https://doi.org/10.1016/j.orl.2005.07.009.
  2. Ralf Borndörfer, Heide Hoppmann, Marika Karbstein, and Niels Lindner. Separation of cycle inequalities in periodic timetabling. Discrete Optimization, 35:100552, 2020. URL: https://doi.org/10.1016/j.disopt.2019.100552.
  3. Ralf Borndörfer, Niels Lindner, and Sarah Roth. A concurrent approach to the Periodic Event Scheduling Problem. Journal of Rail Transport Planning & Management, pages 100-175, 2019. URL: https://doi.org/10.1016/j.jrtpm.2019.100175.
  4. Gabrio Caimi, Leo G. Kroon, and Christian Liebchen. Models for railway timetable optimization: Applicability and applications in practice. J. Rail Transp. Plan. Manag., 6(4):285-312, 2017. URL: https://doi.org/10.1016/j.jrtpm.2016.11.002.
  5. Ewgenij Gawrilow and Michael Joswig. polymake: a framework for analyzing convex polytopes. In Polytopes - combinatorics and computation (Oberwolfach, 1997), volume 29 of DMV Sem., pages 43-73. Birkhäuser, Basel, 2000. Google Scholar
  6. Marc Goerigk. PESPlib - A benchmark library for periodic event scheduling, 2012. URL: http://num.math.uni-goettingen.de/~m.goerigk/pesplib/.
  7. Marc Goerigk and Christian Liebchen. An improved algorithm for the periodic timetabling problem. In ATMOS, volume 59 of OASICS, pages 12:1-12:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  8. Refael Hassin. A flow algorithm for network synchronization. Operations Research, 44:570-579, 1996. Google Scholar
  9. IBM. IBM CPLEX Optimizer 12.10 user’s manual, 2019. URL: https://www.ibm.com/analytics/cplex-optimizer.
  10. C. Liebchen. Periodic Timetable Optimization in Public Transport. Dissertation.de - Verlag im Internet, 2006. Google Scholar
  11. Christian Liebchen. Optimierungsverfahren zur Erstellung von Taktfahrplänen. Diploma Thesis, Technische Universität Berlin, 1998. In German. Google Scholar
  12. Christian Liebchen. A cut-based heuristic to produce almost feasible periodic railway timetables. In Sotiris E. Nikoletseas, editor, Experimental and Efficient Algorithms, 4th InternationalWorkshop, WEA 2005, Santorini Island, Greece, May 10-13, 2005, Proceedings, volume 3503 of Lecture Notes in Computer Science, pages 354-366. Springer, 2005. URL: https://doi.org/10.1007/11427186_31.
  13. Christian Liebchen and Rolf H. Möhring. The modeling power of the periodic event scheduling problem: Railway timetables - and beyond. In Frank Geraets, Leo G. Kroon, Anita Schöbel, Dorothea Wagner, and Christos D. Zaroliagis, editors, Algorithmic Methods for Railway Optimization, International Dagstuhl Workshop, Dagstuhl Castle, Germany, June 20-25, 2004, 4th International Workshop, ATMOS 2004, Bergen, Norway, September 16-17, 2004, Revised Selected Papers, volume 4359 of Lecture Notes in Computer Science, pages 3-40. Springer, 2004. URL: https://doi.org/10.1007/978-3-540-74247-0_1.
  14. Christian Liebchen and Leon Peeters. Integral cycle bases for cyclic timetabling. Discrete Optimization, 6(1):98-109, 2009. URL: https://doi.org/10.1016/j.disopt.2008.09.003.
  15. Christian Liebchen, Mark Proksch, and Frank Wagner. Performance of algorithms for periodic timetable optimization. In Mark Hickman, Pitu Mirchandani, and Stefan Voß, editors, Computer-aided Systems in Public Transport, volume 600 of Lecture Notes in Economics and Mathematical Systems, pages 151-180. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-73312-6_8.
  16. Christian Liebchen and Romeo Rizzi. Classes of cycle bases. Discret. Appl. Math., 155(3):337-355, 2007. URL: https://doi.org/10.1016/j.dam.2006.06.007.
  17. Christian Liebchen and Elmar Swarat. The second Chvátal closure can yield better railway timetables. In Matteo Fischetti and Peter Widmayer, editors, ATMOS 2008 - 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems, Karlsruhe, Germany, September 18, 2008, volume 9 of OASICS. Internationales Begegnungs- und Forschungszentrum fuer Informatik (IBFI), Schloss Dagstuhl, Germany, 2008. URL: http://drops.dagstuhl.de/opus/volltexte/2008/1580.
  18. Niels Lindner and Christian Liebchen. New perspectives on PESP: T-partitions and separators. In Valentina Cacchiani and Alberto Marchetti-Spaccamela, editors, 19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2019, September 12-13, 2019, Munich, Germany, volume 75 of OASICS, pages 2:1-2:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/OASIcs.ATMOS.2019.2.
  19. Niels Lindner and Julian Reisch. Parameterized complexity of periodic timetabling. Technical Report 20-15, Zuse Institute Berlin, 2020. Google Scholar
  20. Thomas Lindner. Train Schedule Optimization in Public Rail Transport. Ph.d. thesis, Technische Universität Braunschweig, 2000. Google Scholar
  21. Karl Nachtigall. Cutting planes for a polyhedron associated with a periodic network. Institutsbericht IB 112-96/17, Deutsche Forschungsanstalt für Luft- und Raumfahrt e.V., July 1996. Google Scholar
  22. Karl Nachtigall. Periodic Network Optimization and Fixed Interval Timetables. Habilitation thesis, Universität Hildesheim, 1998. Google Scholar
  23. Michiel A. Odijk. Construction of periodic timetables, part 1: A cutting plane algorithm. Technical Report 94-61, TU Delft, 1994. Google Scholar
  24. Siegfried Rüger. Transporttechnologie städtischer öffentlicher Personenverkehr. Transpress Verlag für Verkehrswesen, Berlin, 3rd edition, 1986. Google Scholar
  25. Alexander Schrijver. Combinatorial Optimization - Polyhedra end Efficiency. Algorithms and Combinatorics. Springer, 2003. Google Scholar
  26. Paolo Serafini and Walter Ukovich. A mathematical model for periodic scheduling problems. SIAM Journal on Discrete Mathematics, 2(4):550-581, 1989. Google Scholar
  27. Gregor Wünsch. Coordination of Traffic Signals in Networks. Ph.D. thesis, Technische Universität Berlin, 2008. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact