Document Open Access Logo

Forward Cycle Bases and Periodic Timetabling

Authors Niels Lindner , Christian Liebchen , Berenike Masing

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2021.2.pdf
  • Filesize: 0.72 MB
  • 14 pages

Document Identifiers

Author Details

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

Funding

  • Masing, Berenike: Funded by the 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, Christian Liebchen, and Berenike Masing. Forward Cycle Bases and Periodic Timetabling. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 2:1-2:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/OASIcs.ATMOS.2021.2

Abstract

Periodic timetable optimization problems in public transport can be modeled as mixed-integer linear programs by means of the Periodic Event Scheduling Problem (PESP). In order to keep the branch-and-bound tree small, minimum integral cycle bases have been proven successful. We examine forward cycle bases, where no cycle is allowed to contain a backward arc. After reviewing the theory of these bases, we describe the construction of an integral forward cycle basis on a line-based event-activity network. Adding turnarounds to the instance R1L1 of the benchmark library PESPlib, we computationally evaluate three types of forward cycle bases in the Pareto sense, and come up with significant improvements concerning dual bounds.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
  • Mathematics of computing → Integer programming
  • Applied computing → Transportation
Keywords
  • Periodic Timetabling
  • Cycle Bases
  • Mixed Integer Programming

Metrics

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

References

  1. E. Amaldi, C. Iuliano, T. Jurkiewicz, K. Mehlhorn, and R. Rizzi. Breaking the o(m^2n) barrier for minimum cycle bases. In A. Fiat and P. Sanders, editors, Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, volume 5757 of Lecture Notes in Computer Science, pages 301-312. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-04128-0_28.
  2. R. Borndörfer, H. Hoppmann, M. Karbstein, and N. Lindner. Separation of cycle inequalities in periodic timetabling. Discrete Optimization, 35:100552, 2020. URL: https://doi.org/10.1016/j.disopt.2019.100552.
  3. R. Borndörfer, N. Lindner, and S. Roth. A concurrent approach to the Periodic Event Scheduling Problem. Journal of Rail Transport Planning & Management, 15:100175, 2020. Best Papers of RailNorrköping 2019. URL: https://doi.org/10.1016/j.jrtpm.2019.100175.
  4. G. Galbiati, R. Rizzi, and E. Amaldi. On the approximability of the minimum strictly fundamental cycle basis problem. Discrete Applied Mathematics, 159(4):187-200, 2011. URL: https://doi.org/10.1016/j.dam.2010.10.014.
  5. P. M. Gleiss, J. Leydold, and P. F. Stadler. Circuit bases of strongly connected digraphs. Discussiones Mathematicae Graph Theory, 23(2):241, 2003. URL: https://doi.org/10.7151/dmgt.1200.
  6. M. Goerigk. PESPlib - A benchmark library for periodic event scheduling, 2012. URL: http://num.math.uni-goettingen.de/~m.goerigk/pesplib/.
  7. M. Goerigk and C. 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. M. Goerigk and A. Schöbel. Improving the modulo simplex algorithm for large-scale periodic timetabling. Computers & Operations Research, 40(5):1363-1370, 2013. Google Scholar
  9. Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2021. URL: https://www.gurobi.com.
  10. J. D. Horton. A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J. Comput., 16(2):358-366, 1987. URL: https://doi.org/10.1137/0216026.
  11. T. Kavitha, C. Liebchen, K. Mehlhorn, D. Michail, R. Rizzi, T. Ueckerdt, and K. A. Zweig. Cycle bases in graphs characterization, algorithms, complexity, and applications. Computer Science Review, 3(4):199-243, 2009. URL: https://doi.org/10.1016/j.cosrev.2009.08.001.
  12. C. Liebchen. Periodic timetable optimization in public transport. PhD thesis, Technische Universität Berlin, 2006. Google Scholar
  13. C. Liebchen and R. H. Möhring. The Modeling Power of the Periodic Event Scheduling Problem: Railway Timetables — and Beyond. In F. Geraets, L. Kroon, A. Schöbel, D. Wagner, and C. D. Zaroliagis, editors, Algorithmic Methods for Railway Optimization, Lecture Notes in Computer Science, pages 3-40, Berlin, Heidelberg, 2007. Springer. URL: https://doi.org/10.1007/978-3-540-74247-0_1.
  14. C. Liebchen and L. 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. C. Liebchen and E. Swarat. The Second Chvatal Closure Can Yield Better Railway Timetables. In M. Fischetti and P. Widmayer, editors, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08), volume 9 of OpenAccess Series in Informatics (OASIcs), Dagstuhl, Germany, 2008. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. ISSN: 2190-6807. URL: https://doi.org/10.4230/OASIcs.ATMOS.2008.1580.
  16. N. Lindner and C. Liebchen. Determining All Integer Vertices of the PESP Polytope by Flipping Arcs. In D. Huisman and C. D. Zaroliagis, editors, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020), volume 85 of OpenAccess Series in Informatics (OASIcs), pages 5:1-5:18, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik. ISSN: 2190-6807. URL: https://doi.org/10.4230/OASIcs.ATMOS.2020.5.
  17. N. Lindner and C. Liebchen. Timetable Merging for the Periodic Event Scheduling Problem. Technical Report 21-06, Zuse Institute Berlin, 2021. URL: https://nbn-resolving.org/urn:nbn:de:0297-zib-81587.
  18. N. Lindner, C. Liebchen, and B. Masing. Constructing forward integral cycle bases for periodic timetabling, in preparation. Google Scholar
  19. T. Lindner. Train Scheduling in Public Rail Transport. PhD thesis, Technische Universität Braunschweig, 2000. Google Scholar
  20. K. Nachtigall. Cutting Planes for a Polyhedron Associated with a Periodic Network. Technical Report 112-96/17, Deutsches Zentrum für Luft- und Raumfahrt, 1996. Google Scholar
  21. K. Nachtigall. Periodic Network Optimization and Fixed Interval Timetables. Habilitation thesis, Universität Hildesheim, 1998. Google Scholar
  22. K. Nachtigall and J. Opitz. Solving Periodic Timetable Optimisation Problems by Modulo Simplex Calculations. In Matteo Fischetti and Peter Widmayer, editors, 8th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'08), volume 9 of OpenAccess Series in Informatics (OASIcs), Dagstuhl, Germany, 2008. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. Google Scholar
  23. M. A. Odijk. Construction of periodic timetables, part 1: A cutting plane algorithm. Technical Report 94-61, TU Delft, 1994. Google Scholar
  24. R. Rizzi. Minimum Weakly Fundamental Cycle Bases Are Hard To Find. Algorithmica, 53(3):402-424, 2009. URL: https://doi.org/10.1007/s00453-007-9112-8.
  25. P. Serafini and W. Ukovich. A mathematical model for periodic scheduling problems. SIAM Journal on Discrete Mathematics, 2(4):550-581, 1989. Google Scholar
  26. P. Seymour and C. Thomassen. Characterization of even directed graphs. Journal of Combinatorial Theory, Series B, 42(1):36-45, 1987. URL: https://doi.org/10.1016/0095-8956(87)90061-X.
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