Document Open Access Logo

Integrating Passengers' Routes in Periodic Timetabling: A SAT approach

Authors Philine Gattermann, Peter Großmann, Karl Nachtigall, Anita Schöbel

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2016.3.pdf
  • Filesize: 0.64 MB
  • 15 pages

Document Identifiers

Author Details

Philine Gattermann
Peter Großmann
Karl Nachtigall
Anita Schöbel

Cite As Get BibTex

Philine Gattermann, Peter Großmann, Karl Nachtigall, and Anita Schöbel. Integrating Passengers' Routes in Periodic Timetabling: A SAT approach. In 16th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Open Access Series in Informatics (OASIcs), Volume 54, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/OASIcs.ATMOS.2016.3

Abstract

The periodic event scheduling problem (PESP) is a well studied problem known as intrinsically hard. Its main application is for designing periodic timetables in public transportation. To this end, the passengers' paths are required as input data. This is a drawback since the final paths which are used by the passengers depend on the timetable to be designed. Including the passengers' routing in the PESP hence improves the quality of the resulting timetables. However, this makes PESP even harder.

Formulating the PESP as satisfiability problem and using SAT solvers for its solution has been shown to be a highly promising approach. The goal of this paper is to exploit if SAT solvers can also be used for the problem of integrated timetabling and passenger routing. In our model of the integrated problem we distribute origin-destination (OD) pairs temporally through the network by using time-slices in order to make the resulting model more realistic. We present a formulation of this integrated problem as integer program which we are able to transform to a satisfiability problem. We tested the latter formulation within numerical experiments, which are performed on Germany's long-distance passenger railway network. The computation's analysis in which we compare the integrated approach with the traditional one with fixed passengers' weights, show promising results for future scientific investigations.

Subject Classification

Keywords
  • PESP
  • Timetabling
  • Public Transport
  • Passengers' Routes
  • SAT

Metrics

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

References

  1. R. Borndörfer, H. Hoppmann, and M. Karbstein. Timetabling and passenger routing in public transport. In Proceedings of the 13th Conference on Advanced Systems in Public Transport (CASPT) 2015, 2015. Google Scholar
  2. 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
  3. P. Großmann. Polynomial reduction from PESP to SAT. Technical Report 4, Technische Universität Dresden, Germany, October 2011. Google Scholar
  4. P. Großmann, J. Opitz, R. Weiß, and M. Kümmling. On resolving infeasible periodic event networks. In Proceedings of the 13th Conference on Advanced Systems in Public Transport (CASPT) 2015. Erasmus University, 2015. Google Scholar
  5. Peter Großmann, Steffen Hölldobler, Norbert Manthey, Karl Nachtigall, Jens Opitz, and Peter Steinke. Solving periodic event scheduling problems with SAT. In Advanced Research in Applied Artificial Intelligence, pages 166-175. Springer, 2012. Google Scholar
  6. Z. Gu, E. Rothberg, and R. Bixby. Gurobi 6.0.3. Gurobi Optimization, Inc., Houston, TX, May 2015. 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. M. Kümmling, P. Großmann, K. Nachtigall, J. Opitz, and R. Weiß. A state-of-the-art realization of cyclic railway timetable computation. Public Transport, 7(3):281-293, 2015. Google Scholar
  9. M. Kümmling, J. Opitz, and P. Großmann. Combining cyclic timetable optimization and traffic assignment. In 20th Conference of the International Federation of Operational Research Societies (IFORS), Barcelona, Spain, presentation, 2014. Google Scholar
  10. C. Liebchen. Finding short integral cycle bases for cyclic timetabling. In Proceedings of European Symposium on Algorithms (ESA) 2003, pages 715-726, 2003. Google Scholar
  11. C. Liebchen. Periodic Timetable Optimization in Public Transport. dissertation.de - Verlag im Internet, Berlin, 2006. Google Scholar
  12. C. Liebchen. The first optimized railway timetable in practice. Transportation Science, 42(4):420-435, 2008. Google Scholar
  13. C. Liebchen and R. Möhring. The modeling power of the periodic event scheduling problem: railway timetables - and beyond. In Algorithmic Methods for Railway Optimization, number 4359 in Lecture Notes on Computer Science, pages 3-40. Springer, 2007. Google Scholar
  14. C. Liebchen and R. Rizzi. A greedy approach to compute a minimum cycle basis of a directed graph. Information Processing Letters, 94(3):107-112, 2005. Google Scholar
  15. R. Martins, V. Manquinho, and I. Lynce. Open-WBO: A Modular MaxSAT Solver. In Carsten Sinz and Uwe Egly, editors, Theory and Applications of Satisfiability Testing - SAT 2014, volume 8561 of Lecture Notes in Computer Science, pages 438-445. Springer International Publishing, 2014. Google Scholar
  16. K. Nachtigall. Periodic Network Optimization and Fixed Interval Timetables. PhD thesis, University of Hildesheim, 1998. Google Scholar
  17. K. Nachtigall and J. Opitz. Solving periodic timetable optimisation problems by modulo simplex calculations. In Proc. ATMOS, 2008. Google Scholar
  18. K. Nachtigall and S. Voget. A genetic approach to periodic railway synchronization. Computers Ops. Res., 23(5):453-463, 1996. Google Scholar
  19. M. A. Odijk. A constraint generation algorithm for the construction of periodic railway timetables. Transportation Research, 30B:455-464, 1996. Google Scholar
  20. L. Peeters. Cyclic Railway Timetabling Optimization. PhD thesis, ERIM, Rotterdam School of Management, 2003. Google Scholar
  21. 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
  22. L. Peeters and L. Kroon. A variable trip time model for cyclic railway timetabling. Transportation Science, 37(2):198-212, 2003. Google Scholar
  23. M. Schmidt. Integrating Routing Decisions in Public Transportation Problems, volume 89 of Optimization and Its Applications. Springer, 2014. Google Scholar
  24. M. Schmidt and A. Schöbel. Timetabling with passenger routing. OR Spectrum, 37:75-97, 2015. Google Scholar
  25. A. Schöbel. Line planning in public transportation: models and methods. OR Spectrum, 34(3):491-510, 2012. Google Scholar
  26. 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