A Parallel DFS Algorithm for Train Re-scheduling During Traffic Disturbances — Early Results
| Document type: | Conference Papers |
|---|---|
| Peer reviewed: | Yes |
| Full text: | |
| Author(s): | Syed Muhammad Zeeshan Iqbal, Håkan Grahn, Johanna Törnquist Krasemann |
| Title: | A Parallel DFS Algorithm for Train Re-scheduling During Traffic Disturbances — Early Results |
| Conference name: | 4th Swedish workshop on Multicore Computing MCC |
| Year: | 2011 |
| Pagination: | 115-120 |
| City: | Linköping, Sweden |
| Organization: | Blekinge Institute of Technology |
| Department: | School of Computing (Sektionen för datavetenskap och kommunikation) School of Computing S-371 79 Karlskrona +46 455 38 50 00 http://www.bth.se/com |
| Authors e-mail: | Muhammad.Zeeshan.Iqbal@bth.se, Hakan.Grahn@bth.se, Johanna.Tornquist@bth.se |
| Language: | English |
| Abstract: | 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 final delay for all trains in the scenarios. We propose a parallel algorithm based on a depth-first 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 significantly improves the solution for 5 out of 20 disturbance scenarios, as compared to the sequential algorithm. |
| Subject: | Computer Science\General Computer Science\Computersystems Computer Science\Artificial Intelligence |
