A Parallel DFS Algorithm for Train Re-scheduling During Trafﬁc Disturbances — Early Results
Blekinge Institute of Technology, School of Computing2011 (English)Conference paper (Refereed) Published
Railways are an important part of the infrastructure in most countries. As the railway networks become more and more saturated, even small traffic disturbances can propagate and have severe consequences. In this paper, the train re-scheduling problem is studied in order to minimize the ﬁnal delay for all trains in the scenarios. We propose a parallel algorithm based on a depth-ﬁrst search branch-and-bound strategy. The parallel algorithm is compared to a sequential algorithm in terms of the quality of the solution and the number of nodes evaluated, as well as to optimal solutions found by Cplex, using 20 disturbance scenarios. Our parallel algorithm signiﬁcantly improves the solution for 5 out of 20 disturbance scenarios, as compared to the sequential algorithm.
Place, publisher, year, edition, pages
Linköping, Sweden, 2011.
IdentifiersURN: urn:nbn:se:bth-7341Local ID: oai:bth.se:forskinfoBA57C435F7C5E05BC125797C002E660DOAI: oai:DiVA.org:bth-7341DiVA: diva2:834948
4th Swedish workshop on Multicore Computing MCC