A Hierarchical Decomposition Approach for Railway Disruption Recovery

Motivation：

• With rapid urbanization, railway systems in cities play a increasingly significant role in daily transportation.
• The railway system’s normal schedules might be disrupted by unexpected events (e.g., train breakdown, bad weather). Intelligent scheduling technology is urgently needed to quickly repair operational plans.

Problem Definition:

1. Given

• Normal planned schedules
• Emergencies (such as train delays 

2. Operational Constraints

The railway operations have to respect the following three types of constraints:

• rolling stock duty feasibility, including considerations such as minimum run time, minimum dwell time, changing end, etc.
• minimum headway
• minimum separation

3. Decisions

Timetable amendments in order to restore feasibility:

• Rerouting trains: swaps, deadhead or repositioning of trains
• Course cancellation: cancel courses partially or fully
• Re-timing: adjust the planned arrival/departure times (prepone up to

5 minutes or postpone)

• Skipping stops: skips some planned stops

Solution Approach:

We propose a novel hierarchical decomposition approach:

1. Rerouting: Key decisions such as course cancellation and course-swapping have the most profound impact on the timetable amendments.
2. Retiming: This stage mainly concerns a proper adjustment of departure and arrival times for each course at each node.
3. Repairing: We design an efficient repairing procedure to attain feasibility of the returned solution.

Team members：

Longfei Wang, Akang Wang, Xiaodong Luo from SRIBD

Shengcheng Shao, Dong Zhang from Huawei

Award:

We won the second place in the INFOMRS 2022 RAS Problem Solving Competition.