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

Abstract

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.