Periodic timetabling for highly utilized railway networks is a demanding challenge. We formulate an infrastructure-aware extension of the Periodic Event Scheduling Problem (PESP) by requiring that not only events, but also activities using the same infrastructure must be separated by a minimum headway time. This extended problem can be modeled as a mixed-integer program by adding constraints on the sum of periodic tensions along certain cycles, so that it shares some structural properties with standard PESP. We further refine this problem by fixing cyclic orders at each infrastructure element. Although the computational complexity remains unchanged, the mixed-integer programming model then becomes much smaller. Furthermore, we also discuss how to find a minimal subset of infrastructure elements whose cyclic order already prescribes the order for the remaining parts of the network, and how cyclic order information can be modeled in a mixed-integer programming context. In practice, we evaluate the impact of cyclic orders on a real-world instance on the S-Bahn Berlin network, which turns out to be computationally fruitful.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Periodic Timetabling with Cyclic Order Constraints


    Beteiligte:
    Bortoletto, Enrico (Autor:in) / Lindner, Niels (Autor:in) / Masing, Berenike (Autor:in) / Frigioni, Daniele (Herausgeber:in) / Schiewe, Philine (Herausgeber:in)


    Erscheinungsdatum :

    2023-08-31


    Format / Umfang :

    18 pages , 755273 byte


    Anmerkungen:

    OASIcs, Vol. 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023), pages 7:1-7:18





    Medientyp :

    Aufsatz (Konferenz)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch





    Recoverable Robust Periodic Timetabling

    Grafe, Vera / Schöbel, Anita | DataCite | 2023

    Freier Zugriff

    An Improved Algorithm for the Periodic Timetabling Problem

    Marc, Goerigk / Liebchen, Christian | BASE | 2017

    Freier Zugriff


    An adjustable robust optimization approach for periodic timetabling

    Polinder, Gert-Jaap / Breugem, Thomas / Dollevoet, Twan et al. | Elsevier | 2019


    Hierarchical Decomposition Methods for Periodic Railway Timetabling Problems

    Herrigel, Sabrina / Laumanns, Marco / Nash, Andrew et al. | Transportation Research Record | 2013