Dispatching and coordination in multi-area railway traffic management.

*(English)*Zbl 1307.90095Summary: This paper deals with the development of decision support systems for traffic management of large and busy railway networks in case of severe disturbances. Railway operators typically structure the control of complicated networks into the coordinated control of several local dispatching areas. A dispatcher takes rescheduling decisions on the trains running on its local area while a coordinator addresses global issues that may arise between areas. While several advanced train dispatching models and algorithms have been proposed to support the dispatchers’ task, the coordination problem did not receive much attention in the literature on train scheduling. This paper presents new heuristic algorithms for both local dispatching and coordination and compares centralized and distributed procedures to support the task of dispatchers and coordinators. We adopt dispatching procedures driven by optimization algorithms and based on local or global information and decisions. Computational experiments on a Dutch railway network, actually controlled by ten dispatchers, assess the performance of the centralized and distributed procedures. Various traffic disturbances, including entrance delays and blocked tracks, are analyzed on various time horizons of traffic prediction. Results show that the new heuristics clearly improve the global performance of the network with respect to the state of the art.

##### MSC:

90B90 | Case-oriented studies in operations research |

90B35 | Deterministic scheduling theory in operations research |

90B20 | Traffic problems in operations research |

##### Keywords:

train rescheduling; disturbance handling; large-scale problems; centralized and distributed optimization
Full Text:
DOI

##### References:

[1] | Almodóvar, M.; García-Ródenas, R., On-line reschedule optimization for passenger railways in case of emergencies, Comput Oper Res, 40, 3, 725-736, (2013) · Zbl 1349.90307 |

[2] | Caimi, G.; Fuchsberger, M.; Laumanns, M.; Lüthi, M., A model predictive control approach for discrete-time rescheduling in complex central railway station areas, Comput Oper Res, 39, 11, 2578-2593, (2012) · Zbl 1251.90005 |

[3] | Cheng, Y.-H.; Yang, L.-A., A fuzzy Petri nets approach for railway traffic control in case of abnormalityevidence from Taiwan railway system, Expert Syst Appl, 36, 4, 8040-8048, (2009) |

[4] | Chou, Y. H.; Weston, P. F.; Roberts, C., Dynamic distributed control for realtime rescheduling of railway networks, (Hansen, I. A.; Radtke, A.; Pachl, J.; Wendler, E., Proceedings of the 2nd international seminar on railway operations modelling and analysis, (2007), Hannover Germany) |

[5] | Chou YH, Weston PF, Roberts C. Collaborative Rescheduling in a Distributed Railway Control System. In: Hansen IA, Wendler E, Weidmann U, Luethi M, Rodriguez J, Ricci S, et al., editors. Proceedings of the 3rd international seminar on railway operations modelling and analysis, Zurich, Switzerland; 2009. |

[6] | Coffman, E. G.; Elphick, M. J.; Shoshani, A., System deadlocks, Comput Surv, 3, 1, 67-78, (1971) · Zbl 0226.68015 |

[7] | Corman, F.; D’Ariano, A.; Pacciarelli, D.; Pranzo, M., A tabu search algorithm for rerouting trains during rail operations, Transp Res Part B, 44, 1, 175-192, (2010) |

[8] | Corman, F.; D’Ariano, A.; Pacciarelli, D.; Pranzo, M., Centralized versus distributed systems to reschedule trains in two dispatching areas, Public Transp, 2, 3, 219-247, (2011) |

[9] | Corman, F.; D’Ariano, A.; Pacciarelli, D.; Pranzo, M., Optimal inter-area coordination of train rescheduling decisions, Transp Res Part E, 48, 1, 71-88, (2012) |

[10] | Corman, F.; D’Ariano, A.; Pranzo, M.; Hansen, I. A., Effectiveness of dynamic reordering and rerouting of trains in a complicated and densely occupied station area, Transp Plan Technol, 34, 4, 341-362, (2011) |

[11] | D’Ariano, A.; Corman, F.; Pacciarelli, D.; Pranzo, M., Reordering and local rerouting strategies to manage train traffic in real-time, Transp Sci, 42, 4, 405-419, (2008) |

[12] | D’Ariano, A.; Pacciarelli, D.; Pranzo, M., A branch and bound algorithm for scheduling trains in a railway network, Eur J Oper Res, 183, 2, 643-657, (2007) · Zbl 1179.90135 |

[13] | D’Ariano, A.; Pranzo, M., An advanced real-time train dispatching system for minimizing the propagation of delays in a dispatching area under severe disturbances, Netw Spat Econ, 9, 1, 63-84, (2009) · Zbl 1162.90375 |

[14] | Fay, A., A fuzzy knowledge-based system for railway traffic control, Eng Appl Artif Intell, 13, 6, 719-729, (2000) |

[15] | Hansen, I. A.; Pachl, J., Railway timetable and trafficanalysis, modelling and simulation, (2008), Eurailpress Hamburg, Germany |

[16] | Iyer, R. V.; Gosh, S., DARYN, A distributed decision-making algorithm for railway networksmodeling and simulation, IEEE Trans Veh Technol, 44, 1, 180-191, (1995) |

[17] | Jia, L.-M.; Zhang, X.-D., Distributed intelligent railway traffic controla fuzzy-decision making-based approach, Eng Appl Artif Intell, 7, 3, 311-319, (1994) |

[18] | Lamma, E.; Mello, P.; Milano, M., A distributed constraint-based scheduler, Artif Intell Eng, 11, 2, 91-105, (1997) |

[19] | Lee, T. S.; Gosh, S., Stability of rynsorda decentralized algorithm for railway networks under perturbations, IEEE Trans Veh Technol, 50, 1, 287-301, (2001) |

[20] | Lusby, R. M.; Larsen, J.; Ehrgott, M.; Ryan, D. M., A set packing inspired method for real-time junction train routing, Comput Oper Res, 40, 3, 713-724, (2013) · Zbl 1349.90595 |

[21] | Mascis, A.; Pacciarelli, D., Job shop scheduling with blocking and no-wait constraints, Eur J Oper Res, 143, 3, 498-517, (2002) · Zbl 1082.90528 |

[22] | Mazzarello, M.; Ottaviani, E., A traffic management system for real-time traffic optimization in railways, Transp Res Part B, 41, 2, 246-274, (2007) |

[23] | Pacciarelli D. Deliverable D3: traffic regulation and co-operation methodologies - code WP4UR_DV_7001_D. Project COMBINE 2 “enhanced COntrol centres for fixed and Moving Block sIgNalling systEms - 2” Number: IST-2001-34705; 2003. |

[24] | Parodi, G.; Vernazza, G.; Zunino, F., Stability and deadlock avoidance in distributed system for traffic control, IEEE Trans Veh Technol, 45, 4, 732-743, (1996) |

[25] | Pranzo M, Meloni C, Pacciarelli D. A new class of greedy heuristics for job shop scheduling problems. In: Lecture notes in computer science, vol. 2647; 2003. pp. 223-36. · Zbl 1023.90515 |

[26] | Rodriguez, J., A constraint programming model for real-time train scheduling at junctions, Transp Res Part B, 41, 2, 231-245, (2007) |

[27] | Şahin, İ, Railway traffic control and train scheduling based on inter-train conflict management, Transp Res Part B, 33, 7, 511-534, (1999) |

[28] | Salido, M. A.; Abril, M.; Barber, F.; Ingolotti, L.; Tormos, P.; Lova, A., Domain-dependent distributed models for railway scheduling, Knowl-Based Syst, 20, 2, 186-194, (2007) |

[29] | Strotmann, C. Railway scheduling problems and their decomposition [Ph.D. thesis]. Germany: Universität Osnabrück; 2007. |

[30] | Törnquist, J.; Persson, J. A., N-tracked railway traffic re-scheduling during disturbances, Transp Res Part B, 41, 3, 342-362, (2007) |

[31] | Vernazza, G.; Zunino, R., A distributed intelligence methodology for railway traffic control, IEEE Trans Veh Technol, 39, 3, 263-270, (1990) |

[32] | Wegele, S.; Slovák, R.; Schnieder, E., Real-time decision support for optimal dispatching of train operation, (Hansen, I. A.; Radtke, A.; Pachl, J.; Wendler, E., Proceedings of the 2nd international seminar on railway operations modelling and analysis, (2007), Hannover Germany) |

[33] | Zhu P. Betriebliche Leistung von Bahnsystemen unter Störungsbedingungen [Ph.D. thesis]. TU Braunschweig, Germany: Berichte der Institute für Automatisierungstechnik; 2001 (In German). |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.