TY - JOUR

T1 - A real-time conflict solution algorithm for the train rescheduling problem

AU - Bettinelli, Andrea

AU - Santini, Alberto

AU - Vigo, Daniele

PY - 2017/12/1

Y1 - 2017/12/1

N2 - We consider the real-time resolution of conflicts arising in real-world train management applications. In particular, given a nominal timetable for a set of trains and a set of modifications due to delays or other resources unavailability, we are aiming at defining a set of actions which must be implemented to grant safety, e.g., to avoid potential conflicts such as train collisions or headway violations, and restore quality by reducing the delays. To be compatible with real-time management, the required actions must be determined in a few seconds, hence specialized fast heuristics must be used. We propose a fast and effective parallel algorithm that is based on an iterated greedy scheduling of trains on a time-space network. The algorithm uses several sortings to define the initial train dispatching rule and different shaking methods between iterations. The performance is further enhanced by using various sparsification methods for the time-space network. The best algorithm configuration is determined through extensive experiments, conducted on a set of instances derived from real-world networks and instances from the literature. The resulting heuristic proved able to consistently resolve the existing conflicts and obtaining excellent solution quality within just two seconds of computing time on a standard personal computer, for instances involving up to 151 trains and two hours of planning time horizon.

AB - We consider the real-time resolution of conflicts arising in real-world train management applications. In particular, given a nominal timetable for a set of trains and a set of modifications due to delays or other resources unavailability, we are aiming at defining a set of actions which must be implemented to grant safety, e.g., to avoid potential conflicts such as train collisions or headway violations, and restore quality by reducing the delays. To be compatible with real-time management, the required actions must be determined in a few seconds, hence specialized fast heuristics must be used. We propose a fast and effective parallel algorithm that is based on an iterated greedy scheduling of trains on a time-space network. The algorithm uses several sortings to define the initial train dispatching rule and different shaking methods between iterations. The performance is further enhanced by using various sparsification methods for the time-space network. The best algorithm configuration is determined through extensive experiments, conducted on a set of instances derived from real-world networks and instances from the literature. The resulting heuristic proved able to consistently resolve the existing conflicts and obtaining excellent solution quality within just two seconds of computing time on a standard personal computer, for instances involving up to 151 trains and two hours of planning time horizon.

KW - Heuristic

KW - Railway optimization

KW - Real-time algorithm

KW - Train rescheduling

UR - http://www.scopus.com/inward/record.url?scp=85032382471&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85032382471&partnerID=8YFLogxK

U2 - 10.1016/j.trb.2017.10.005

DO - 10.1016/j.trb.2017.10.005

M3 - Article

AN - SCOPUS:85032382471

VL - 106

SP - 237

EP - 265

JO - Transportation Research. Part B: Methodological

JF - Transportation Research. Part B: Methodological

SN - 0191-2615

ER -