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.


    Access

    Download


    Export, share and cite



    Title :

    Incremental Heuristics for Periodic Timetabling


    Contributors:

    Publication date :

    2023-09-22


    Type of media :

    Paper


    Type of material :

    Electronic Resource


    Language :

    English


    Classification :

    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

    Free access

    Forward Cycle Bases and Periodic Timetabling

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

    Free access

    Periodic Timetabling with Cyclic Order Constraints

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

    Free access

    Forward Cycle Bases and Periodic Timetabling

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

    Free access