We consider the computation of periodic timetables, which is a key task in the service design process of public transportation companies. We propose a new approach for solving the periodic timetable optimisation problem. It consists of a (partially) heuristic network aggregation to reduce the problem size and make it accessible to standard mixed-integer programming (MIP) solvers. We alternate the invocation of a MIP solver with the well-known problem specific modulo network simplex heuristic (ModSim). This iterative approach helps the ModSim-method to overcome local minima efficiently, and provides the MIP solver with better initial solutions. Our computational experiments are based on the 16 railway instances of the PESPlib, which is the only currently available collection of periodic event scheduling problem instances. For each of these instances, we are able to reduce the objective values of previously best known solutions by at least 10.0%, and up to 22.8% with our iterative combined method.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    An Improved Algorithm for the Periodic Timetabling Problem


    Beteiligte:

    Erscheinungsdatum :

    2017-01-01



    Medientyp :

    Aufsatz/Kapitel (Buch)


    Format :

    Elektronische Ressource


    Sprache :

    Englisch


    Schlagwörter :

    Klassifikation :

    DDC:    005 / 385




    Recoverable Robust Periodic Timetabling

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

    Freier Zugriff

    Periodic Timetabling with Cyclic Order Constraints

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

    Freier Zugriff

    Passenger centric train timetabling problem

    Robenek, Tomáš | Online Contents | 2016


    Passenger centric train timetabling problem

    Robenek, Tomáš / Maknoon, Yousef / Azadeh, Shadi Sharif et al. | Elsevier | 2016


    An adjustable robust optimization approach for periodic timetabling

    Polinder, Gert-Jaap / Breugem, Thomas / Dollevoet, Twan et al. | Elsevier | 2019