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.


    Access

    Download


    Export, share and cite



    Title :

    Periodic Timetabling with Cyclic Order Constraints


    Contributors:


    Publication date :

    2023-08-31


    Size :

    18 pages , 755273 byte


    Remarks:

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





    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English





    Recoverable Robust Periodic Timetabling

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

    Free access

    Incremental Heuristics for Periodic Timetabling

    Lindner, Niels / Liebchen, Christian | BASE | 2023

    Free access

    Forward Cycle Bases and Periodic Timetabling

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

    Free access

    Forward Cycle Bases and Periodic Timetabling

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

    Free access

    Periodic Timetabling with Flexibility Based on a Mesoscopic Topology

    Bütikofer, Stephan / Steiner, Albert / Wüst, Raimond | Springer Verlag | 2020