Graph learning-assisted logic-based Benders decomposition for distributionally robust in-station train rescheduling under disruptions
Organizations: School of Transportation Engineering, East China Jiaotong University, Nanchang, Jiangxi 330038, China
Abstract
Resource closures, arrival delays, and processing-time extensions jointly alter station operations during disruptions. Uncertain reopening times further complicate decisions about holding trains and selecting alternative routes. We use observations of disruption-resolution stages to update conditional predictions of the remaining closure duration. A distributionally robust model accounts for errors in scenario probability estimates and jointly optimizes train routes, sequences, and timings. Logic-based Benders decomposition coordinates routing and resource scheduling. Conditional cuts exploit resource-use patterns, and a graph neural network guides the solution order of resource relaxations. Together, these components form the GNN-LBBD algorithm. Across 28 test instances for a five-track station, GNN-LBBD achieved a mean total completion delay of 61.13 train-min. This was 16.63% lower than tabu search and 20.06% lower than variable neighborhood search. Its mean total computation time was close to that of tabu search. On six representative instances, using stage observations reduced mean total completion delay by approximately 21.7%. Continued updating of reopening-time predictions allows route and entry-time adjustments during closures, reducing delays caused by waiting for reopening.
Figures & tables
| Symbol | Definition |
|---|---|
| Set of all trains; set of trains not yet started at update | |
| Feasible routes for train ; ordered sections of route | |
| Set of controlled resources and resource index | |
| Time of update and information history available at that time | |
| Remaining closure duration at update | |
| Conditional scenario set and nominal probability of scenario |
| Experiment | Instances | Comparison | Event seeds |
|---|---|---|---|
| Algorithm comparison | All 28 test instances | GNN-LBBD, TS, and VNS | 2001–2005 |
| Disturbance combinations | t005-06, t006-06 t013-06, t019-06 t040-03, t045-03 | 8 presence/absence combinations of closures, arrival delays, and processing-time extensions | 2001–2005 |
| Value of information | t005-06, t006-06 t013-06, t019-06 t040-03, t045-03 | With stage observations: scenario-based and conditional-mean predictions; with closure-status observations only: scenario-based prediction | 2001–2005 |
| Component ablation | t005-06, t019-06 t040-03, t045-03 | LBBD with resource lower bounds and cut strengthening, followed by GNN-assisted resource ordering | 2001–2005 |
| Sensitivity analysis | t005-06, t019-06 t040-03, t045-03 | Closure-duration scale: , , ; direct-increment scale: , , | 2001–2005 |
| Distribution shift | t005-06, t019-06 t040-03, t045-03 | Actual closure-duration scale: , , ; predicted scale: ; | 3001–3005 |
| Parameter | Value | Parameter | Value |
|---|---|---|---|
| Budget per rescheduling call (s) | 5 | Training scenarios | 510 |
| Periodic check interval (s) | 120 | Supervision labels | 20880 |
| Post-disruption observation window (s) | 7200 | Training epochs | 200 |
| Maximum rescheduling rounds | 160 | Learning rate | 0.001 |
| Prediction and search budget share (%) | 95 | Algorithm seeds | 101, 211 |
| Conditional stratified scenarios | 6 | Probability radius | 0.2 |
| Intensity | Probability | Increment factor | Closure-duration scale (s) | Affected proportion |
| Low | 0.25 | 0.5 | 300 | 0.20 |
| Medium | 0.50 | 1.0 | 600 | 0.40 |
| High | 0.25 | 2.0 | 1200 | 0.60 |
| Metric | GNN-LBBD | TS | VNS |
|---|---|---|---|
| Total completion delay (train-min) | 61.13 | 73.33 | 76.47 |
| Maximum train delay (min) | 10.31 | 10.53 | 10.70 |
| Delayed trains (trains) | 7.30 | 7.79 | 7.86 |
| On-time completion rate (%) | 50.30 | 47.96 | 47.46 |
| Final completion extension (min) | 5.79 | 6.42 | 6.65 |
| Total scheduling waiting time (train-min) | 83.47 | 95.83 | 98.97 |
| Resource lower bounds and cut strengthening | GNN-assisted resource ordering | Total completion delay (train-min) | Maximum train delay (min) | Maximum backlog (trains) | Lower/unchanged/higher delay vs. previous configuration (events) |
| Disabled | Disabled | 98.88 | 12.47 | 6.58 | — |
| Enabled | Disabled | 85.15 | 12.16 | 6.24 | 19/19/2 |
| Enabled | Enabled | 60.90 | 9.98 | 4.83 | 20/20/0 |
| Disturbance combination | Total completion delay (train-min) | Disturbance combination | Total completion delay (train-min) |
|---|---|---|---|
| No disturbance | 0.00 | Closure and arrival delays | 57.64 |
| Resource closure | 54.46 | Closure and processing-time extensions | 60.20 |
| Arrival delays | 4.04 | Arrival delays and processing-time extensions | 7.76 |
| Processing-time extensions | 3.83 | All three disturbances | 45.41 |
| Instance | Total completion delay (train-min) | ||
|---|---|---|---|
| Scenario-based with stage observations | Conditional mean with stage observations | Scenario-based with closure-status observations only | |
| t005-06 | 23.56 | 23.56 | 23.56 |
| t006-06 | 14.66 | 14.66 | 14.66 |
| t013-06 | 14.22 | 14.22 | 14.21 |
| t019-06 | 63.93 | 64.04 | 91.66 |
| t040-03 | 65.41 | 66.75 | 102.99 |
| Setting | Total completion delay (train-min) | Maximum train delay (min) | Maximum backlog (trains) |
|---|---|---|---|
| Baseline | 60.90 | 9.98 | 4.83 |
| Closure-duration scale | 44.26 | 7.02 | 4.53 |
| Closure-duration scale | 170.60 | 21.43 | 8.21 |
| Arrival-delay and processing-time increments | 82.60 | 11.84 | 6.20 |
| Arrival-delay and processing-time increments | 83.36 | 12.17 | 6.04 |
| Actual scale | Model | Total completion delay (train-min) | Maximum train delay (min) | Maximum backlog (trains) |
|---|---|---|---|---|
| Expected-loss | 97.64 | 13.97 | 7.56 | |
| Distributionally robust | 100.92 | 13.92 | 7.41 | |
| Expected-loss | 132.09 | 19.69 | 6.76 | |
| Distributionally robust | 127.98 | 19.28 | 6.63 | |
| Expected-loss | 255.42 | 36.88 | 6.86 | |
| Distributionally robust | 284.37 | 36.88 | 7.46 |
Combinatorial Optimization
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
See all 405 papers