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 :

    31.08.2023


    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

    Incremental Heuristics for Periodic Timetabling

    Lindner, Niels / Liebchen, Christian | BASE | 2023

    Freier Zugriff

    Forward Cycle Bases and Periodic Timetabling

    Lindner, Niels / Liebchen, Christian / Masing, Berenike | BASE | 2021

    Freier Zugriff

    Forward Cycle Bases and Periodic Timetabling

    Lindner, Niels / Liebchen, Christian / Masing, Berenike | BASE | 2021

    Freier Zugriff

    An Improved Algorithm for the Periodic Timetabling Problem

    Marc, Goerigk / Liebchen, Christian | BASE | 2017

    Freier Zugriff