Conflict resolving – A local search algorithm for solving large scale conflict graphs in freight railway timetabling

Julian Reisch, Peter Großmann, Daniel Pöhle and Natalia Kliewer

European Journal of Operational Research, 2021, vol. 293, issue 3, 1143-1154

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 present a column generation approach where iteratively, the set of possible slots grows. In each iteration, we look for a maximum subset without any conflicts. Modelling the slots as vertices joint by an edge if they have a conflict, this problem is 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, the MIS is solved heuristically with a local search algorithm called Conflict Resolving (CR) that is tailored to the specially structured instances from the application. 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 and numerically compare three MIS solution methods, CR, a MIP solver and Iterated Local Search (ILS), a state-of-the-art MIS heuristics. It turns out that CR performs best for the instances from real-world timetabling, and is also comparable to the ILS on MIS benchmark instances. With this approach, we can solve the TPAP for more than 5000 freight trains.

Keywords: Timetabling; Heuristics; Railways (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221721000084
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:293:y:2021:i:3:p:1143-1154

DOI: 10.1016/j.ejor.2021.01.006

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().