Document Open Access Logo

Tree Decomposition Methods for the Periodic Event Scheduling Problem

Author Irving van Heuven van Staereling

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2018.6.pdf
  • Filesize: 491 kB
  • 13 pages

Document Identifiers

Author Details

Irving van Heuven van Staereling
  • Centrum Wiskunde & Informatica, Science Park 123, Amsterdam, Netherlands

Cite As Get BibTex

Irving van Heuven van Staereling. Tree Decomposition Methods for the Periodic Event Scheduling Problem. In 18th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2018). Open Access Series in Informatics (OASIcs), Volume 65, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/OASIcs.ATMOS.2018.6

Abstract

This paper proposes an algorithm that decomposes the Periodic Event Scheduling Problem (PESP) into trees that can efficiently be solved. By identifying at an early stage which partial solutions can lead to a feasible solution, the decomposed components can be integrated back while maintaining feasibility if possible. If not, the modifications required to regain feasibility can be found efficiently. These techniques integrate dynamic programming into standard search methods. 
The performance of these heuristics are very satisfying, as the problem using publicly available benchmarks can be solved within a reasonable amount of time, in an alternative way than the currently accepted leading-edge techniques. Furthermore, these heuristics do not necessarily rely on linearity of the objective function, which facilitates the research of timetabling under nonlinear circumstances.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Dynamic Programming
  • Trees
  • Periodic Event Scheduling Problem

Metrics

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

References

  1. M. R. Bussieck, T. Winter, and U.Y. Zimmerman. Discrete optimization in public rail transport. Mathematical Programming B 79, pages 415-444, 1997. Google Scholar
  2. M. Goerigk and A. Schobel. Improving the modulo simplex algorithm for large-scale periodic timetabling. Computers &Operations Research 40, page 1363–1370, 2013. Google Scholar
  3. L. G. Kroon, D. Huisman, and G. Maróti. Railway timetabling from an operations research perspective. Econometric Institute Report EI2007-22, 2007. Google Scholar
  4. C. Liebchen. A cut-based heuristic to produce almost feasible periodic railway timetables. Lecture Notes in Computer Science, 2005:354-366, 2005. Google Scholar
  5. C. Liebchen and R. H. Mohring. The modeling power of the periodic event scheduling problem: Railway timetabes - and beyond. Algorithmic Methods for Railway Optimization, pages 3-40, 2007. Google Scholar
  6. C. Liebchen and L. Peeters. Some practical aspects of periodic timetabling. In Operations Research Proceedings 2001, pages 25-32, 2001. Google Scholar
  7. T. Lindner. Train Schedule Optimization in Public Rail Transport. PhD thesis, Braunschweig University of Technology, 2000. Google Scholar
  8. K. Nachtigall. Cutting planes for a polyhedron associated with a periodic network. Technical report, DLR Interner Bericht, 1996. Google Scholar
  9. Karl Nachtigall and Jens 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 fuer Informatik. URL: http://dx.doi.org/10.4230/OASIcs.ATMOS.2008.1588.
  10. M. A. Odijk. Construction of periodic timetables, part i: A cutting plane algorithm. Technical report, Delft University of Technology, 1994. Google Scholar
  11. M. A. Odijk. Construction of periodic timetables, part ii: An application. Technical report, Delft University of Technology, 1994. Google Scholar
  12. M. A. Odijk. A constraint generation algorithm for the construction of periodic railway timetables. In Transportation Research Part B: Methodological, volume 30, pages 455-464, 1996. Google Scholar
  13. L. W. Peeters. Cyclic Railway Timetable Optimization. PhD thesis, Erasmus University Rotterdam, 2003. Google Scholar
  14. G. J. Polinder. Resolving infeasibilities in the PESP model of the Dutch railway timetabling problem. PhD thesis, Erasmus University Rotterdam, 2015. Google Scholar
  15. A. Schrijver and A. Steenbeek. Spoorwegdienstregelingontwikkeling. Technical report, Centrum voor Wiskunde en Informatica, 1993. Google Scholar
  16. P. Serafini and W. Ukovich. A mathematical model for periodic event scheduling problem. SIAM Journal of Discrete Mathematics, 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