The optimization of periodic timetables is an indispensable planning task in public transport. Although the periodic event scheduling problem (PESP) provides an elegant mathematical formulation of the periodic timetabling problem that led to many insights for primal heuristics, it is notoriously hard to solve to optimality. One reason is that for the standard mixed-integer linear programming formulations, linear programming relaxations are weak, and the integer variables are of pure technical nature and in general do not correlate with the objective value. While the first problem has been addressed by developing several families of cutting planes, we focus on the second aspect. We discuss integral forward cycle bases as a concept to compute improved dual bounds for PESP instances. To this end, we develop the theory of forward cycle bases on general digraphs. Specifically for the application of timetabling, we devise a generic procedure to construct line-based event-activity networks and give a simple recipe for an integral forward cycle basis on such networks. Finally, we analyze the 16 railway instances of the benchmark library PESPlib, match them to the line-based structure, and use forward cycle bases to compute better dual bounds for 14 out of the 16 instances.


    Access

    Download


    Export, share and cite



    Title :

    Forward and Line-Based Cycle Bases for Periodic Timetabling


    Contributors:

    Publication date :

    2023-01-01



    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    004 / 388 / 510




    Forward Cycle Bases and Periodic Timetabling

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

    Free access

    Forward and Line-Based Cycle Bases for Periodic Timetabling

    Masing, Berenike / Lindner, Niels / Ebert, Patricia | BASE | 2023

    Free access

    Forward Cycle Bases and Periodic Timetabling

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

    Free access

    Forward and Line-Based Cycle Bases for Periodic Timetabling

    Masing, Berenike / Lindner, Niels / Ebert, Patricia | BASE | 2023

    Free access

    Recoverable Robust Periodic Timetabling

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

    Free access