Rescheduling Trains Using Petri Nets and Heuristic Search
Rescheduling Trains Using Petri Nets and Heuristic Search
复制标题
DOI：
10.1109/tits.2015.2481091
复制
发表时间：
2016-03
影响因子：
8.5
通讯作者：
Pengling Wang;Lei Ma;R. Goverde;Qingyuan Wang
中科院分区：
文献类型：
--
作者：
Pengling Wang;Lei Ma;R. Goverde;Qingyuan Wang
铁路系统可能会被不可预见的事件打断，这些事件需要快速重新重建为可行的新时间表。本文涉及在双轨线上重新安排的火车重新安排问题。重新安排问题被视为冲突检测和解决程序。采用定时的彩色培养皿用来建模铁路系统：地点代表铁路资源，代币代表火车。根据铁路行动的安全原则，建立了冲突检测规则，以预测潜在的冲突。根据A*算法改编的基于PETRI-NET的冲突解决算法旨在搜索最佳或近乎最理想的可行时间表。该算法在生成新标记时考虑了铁路运营原则，因此新的时间表的火车延迟较少，尊重安全原则。该方法在案例研究中应用于荷兰铁路网络的双轨走廊。对于较小的延迟，该算法可以在几秒钟内使延迟的火车恢复到计划的时间表。对于大型扰动，该算法产生的解决方案可以有效地减少火车延迟，同时确保交通安全。
Railway systems may be interrupted by unforeseen events that require quick replanning to a feasible new schedule. This paper deals with the train rescheduling problem on double-track lines. The rescheduling problem is regarded as a conflict detection and resolution procedure. Timed Colored Petri nets are adopted to model the railway system: places represent rail resources, and tokens represent trains. A conflict detection rule is established in accordance with the safety principles of railway operations to predict potential conflicts. A Petri-net-based conflict resolution algorithm adapted from the A* algorithm is designed to search for an optimal or a near-optimal feasible schedule. The algorithm takes into account the railway operational principles when generating new markings, so that the new schedule has less train delays and respects the safety principles. The approach is applied in a case study to a double-track corridor from the Dutch railway network. For small delays, the algorithm can make delayed trains recover to their scheduled timetable within seconds. For large perturbations, the solutions generated by the algorithm can effectively reduce train delays while ensuring traffic safety.