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.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Forward and Line-Based Cycle Bases for Periodic Timetabling


    Beteiligte:
    Masing, Berenike (Autor:in) / Lindner, Niels (Autor:in) / Ebert, Patricia (Autor:in)

    Erscheinungsdatum :

    31.01.2023


    Medientyp :

    Paper


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Klassifikation :

    DDC:    004 / 388



    Forward Cycle Bases and Periodic Timetabling

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

    Freier Zugriff

    Forward and Line-Based Cycle Bases for Periodic Timetabling

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

    Freier Zugriff

    Forward Cycle Bases and Periodic Timetabling

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

    Freier Zugriff

    Forward and Line-Based Cycle Bases for Periodic Timetabling

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

    Freier Zugriff

    Recoverable Robust Periodic Timetabling

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

    Freier Zugriff