We consider the problem of planning the annual timetable for all freight trains in Germany simultaneously. That is, for each train, construct a slot through the network such that no two slots of different trains have a conflict. We denote this task by the Train Path Assignment Problem (TPAP) and consider a column generation approach where iteratively, we are given for each train request a growing set of possible slots. In each iteration, we look for a maximum subset without any conflicts. We model this problem as the Maximum Independent Set problem (MIS). Due to the many slots that are constructed, hence variables that are generated, we deal with large scale MIS instances. Therefore, we solve the MIS heuristically and develop a local search algorithm called Conflict Resolving (CR) that is tailored to the specially structured instances from the application. To solve the MIS, CR iteratively perturbs the current solution in order to leave local optima and then repeatedly improves the solution by replacing k-1 solution vertices by k non-solution vertices. These steps are embedded in a simulated annealing framework. In this paper, we present the column generation approach that is solved as an MIS. Furthermore, we introduce the CR algorithm and numerically compare it to both, a MIP solver and Iterated Local Search (ILS), a state-of-the-art heuristics. It turns out that CR performs best for the instances from real-world timetabling, and is also comparable to the ILS on selected MIS benchmark instances.


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Conflict Resolving ; A Local Search Algorithm for Solving Large Scale Conflict Graphs in Freight Railway Timetabling


    Beteiligte:
    Reisch, Julian (Autor:in) / Großmann, Peter (Autor:in) / Pöhle, Daniel (Autor:in) / Kliewer, Natalia (Autor:in)

    Erscheinungsdatum :

    01.01.2020


    Anmerkungen:

    doi:10.1016/j.ejor.2021.01.006



    Medientyp :

    Paper


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :



    Resolving instability in railway timetabling problems

    Bešinović, Nikola / Quaglietta, Egidio / Goverde, Rob M. P. | Online Contents | 2019


    Railway junction conflict resolution by local search method

    Yeung, T. H. / Ho, T. K. / Wessex Institute of Technology | British Library Conference Proceedings | 2000



    Integrating Timetabling and Crew Scheduling at a Freight Railway Operator

    Bach, Lukas / Dollevoet, Twan / Huisman, Dennis | British Library Online Contents | 2016


    Computer-aided methods for railway operation conflict solving

    Betge-Brezetz, S. / Benoliel, S. / Bain, G. et al. | British Library Conference Proceedings | 1998