Document Open Access Logo

A Matching Approach for Periodic Timetabling

Authors Julius Pätzold, Anita Schöbel

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2016.1.pdf
  • Filesize: 466 kB
  • 15 pages

Document Identifiers

Author Details

Julius Pätzold
Anita Schöbel

Cite As Get BibTex

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). Open Access Series in Informatics (OASIcs), Volume 54, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/OASIcs.ATMOS.2016.1

Abstract

The periodic event scheduling problem (PESP) is a well studied problem known as intrinsically hard, but with important applications mainly for finding good timetables in public transportation. In this paper we consider PESP in public transportation, but in a reduced version (r-PESP) in which the driving and waiting times of the vehicles are fixed to their lower bounds. This results in a still NP-hard problem which has less variables, since only one variable determines the schedule for a whole line. We propose a formulation for r-PESP which is based on scheduling the lines. This enables us on the one hand to identify a finite candidate set and an exact solution approach. On the other hand, we use this formulation to derive a matching-based heuristic for solving PESP. Our experiments on close to real-world instances from LinTim show that our heuristic is able to compute competitive timetables in a very short runtime.

Subject Classification

Keywords
  • PESP
  • Timetabling
  • Public Transport
  • Matching
  • Finite Dominating Set

Metrics

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

References

  1. M. Goerigk. Exact and heuristic approaches to the robust periodic event scheduling problem. Public Transport, 7(1):101-119, 2015. Google Scholar
  2. M. Goerigk, M. Schachtebeck, and A. Schöbel. Evaluating line concepts using travel times and robustness: Simulations with the lintim toolbox. Public Transport, 5(3), 2013. Google Scholar
  3. M. Goerigk and A. Schöbel. Improving the modulo simplex algorithm for large-scale periodic timetabling. Computers and Operations Research, 40(5):1363-1370, 2013. Google Scholar
  4. P. Großmann, S. Hölldobler, N. Manthey, K. Nachtigall, J. Opitz, and P. Steinke. Solving periodic event scheduling problems with sat. In H. Jiang, W. Ding, M. Ali, and X. Wu, editors, Advanced Research in Applied Artificial Intelligence, volume 7345, pages 166-175. Springer, 2012. Google Scholar
  5. J. Harbering, A. Schiewe, and A. Schöbel. LinTim - Integrated Optimization in Public Transportation. Homepage. see http://lintim.math.uni-goettingen.de/. Google Scholar
  6. L. Kroon, G. Maróti, M. R. Helmrich, M. Vromans, and R. Dekker. Stochastic improvement of cyclic railway timetables. Transportation Research Part B: Methodological, 42(6):553 - 570, 2008. Google Scholar
  7. L.G. Kroon, D. Huisman, E. Abbink, P.-J. Fioole, M. Fischetti, G. Maroti, A. Shrijver, A. Steenbeek, and R. Ybema. The new Dutch timetable: The OR Revolution. Interfaces, 39:6-17, 2009. Google Scholar
  8. C. Liebchen. Periodic Timetable Optimization in Public Transport. dissertation.de - Verlag im Internet, Berlin, 2006. Google Scholar
  9. C. Liebchen. The first optimized railway timetable in practice. Transportation Science, 42(4):420-435, 2008. Google Scholar
  10. M. Michaelis and A. Schöbel. Integrating line planning, timetabling, and vehicle scheduling: A customer-oriented approach. Public Transport, 1(3):211-232, 2009. Google Scholar
  11. K. Nachtigall. Periodic Network Optimization and Fixed Interval Timetables. PhD thesis, University of Hildesheim, 1998. Google Scholar
  12. K. Nachtigall and J. Opitz. Solving periodic timetable optimisation problems by modulo simplex calculations. In Proc. ATMOS, 2008. Google Scholar
  13. K. Nachtigall and S. Voget. A genetic approach to periodic railway synchronization. Computers Ops. Res., 23(5):453-463, 1996. Google Scholar
  14. M. A. Odijk. A constraint generation algorithm for the construction of periodic railway timetables. Transportation Research, 30B:455-464, 1996. Google Scholar
  15. J. Pätzold. Periodic timetabling with fixed driving and waiting times. Master’s thesis, Fakultät für Mathematik und Informatik, Georg August University Göttingen, 2016. (in German). Google Scholar
  16. L. Peeters and L. Kroon. A cycle based optimization model for the cyclic railway timetabling problem. In S. Voß and J. Daduna, editors, Computer-Aided Transit Scheduling, volume 505 of Lecture Notes in Economics and Mathematical systems, pages 275-296. Springer, 2001. Google Scholar
  17. P. Serafini and W. Ukovich. A mathematical model for periodic scheduling problems. SIAM Journal on Discrete Mathematic, 2: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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact