We present incremental heuristics for the Periodic Event Scheduling Problem (PESP), the standard mathematical tool to optimize periodic timetables in public transport. The core of our method is to solve successively larger subinstances making use of previously found solutions. Introducing the technical notion of free stratifications, we formulate a general scheme for incremental heuristics for PESP. More practically, we use line and station information to create heuristics that add lines or stations one by one, and we evaluate these heuristics on instances of the benchmarking library PESPlib. This approach is indeed viable, and leads to new incumbent solutions for six PESPlib instances.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Incremental Heuristics for Periodic Timetabling


    Beteiligte:

    Erscheinungsdatum :

    22.09.2023


    Medientyp :

    Paper


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Klassifikation :

    DDC:    004 / 388



    On the Benefit of Preprocessing and Heuristics for Periodic Timetabling

    Liebchen, Christian | British Library Conference Proceedings | 2017


    Recoverable Robust Periodic Timetabling

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

    Freier Zugriff

    Forward Cycle Bases and Periodic Timetabling

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

    Freier Zugriff

    Periodic Timetabling with Cyclic Order Constraints

    Bortoletto, Enrico / Lindner, Niels / Masing, Berenike | DataCite | 2023

    Freier Zugriff

    Forward Cycle Bases and Periodic Timetabling

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

    Freier Zugriff