A tabu search algorithm for rerouting trains during rail operations
A tabu search algorithm for rerouting trains during rail operations
复制标题
DOI：
10.1016/j.trb.2009.05.004
复制
发表时间：
2007
期刊：
影响因子：
8.8
通讯作者：
F. Corman;A. D’Ariano;D. Pacciarelli;M. Pranzo
中科院分区：
文献类型：
--
作者：
F. Corman;A. D’Ariano;D. Pacciarelli;M. Pranzo
本文研究了交通管制员每天处理的列车冲突检测和解决问题，以使列车时刻表适应实时发生的延误和其他不可预测的事件。我们描述了实时交通管理系统ROMA（铁路交通优化方法替代图）中实现的一些算法改进，通过在禁忌搜索方案中结合有效的重新调度算法和本地重路由策略来实现。在较短的计算时间内交替使用快速启发式算法和截断分支定界算法来计算列车时刻表，并研究了使用不同邻域结构进行列车改道的有效性。计算实验是基于荷兰铁路网络调度区域的实际尺寸实例，包括多个延迟列车和阻塞轨道的复杂干扰。为了将启发式解与最优解进行比较，对几个小实例进行了最优解求解。对于小实例，新的禁忌搜索算法可以找到最优解。对于大型实例，新算法在20秒的计算后产生的解决方案比以前版本的ROMA在180秒内得到的解决方案高出15%以上。
This paper addresses the problem of train conflict detection and resolution, which is dealt every day by traffic controllers to adapt the timetable to delays and other unpredictable events occurring in real-time. We describe a number of algorithmic improvements implemented in the real-time traffic management system ROMA (Railway traffic Optimization by Means of Alternative graphs), achieved by incorporating effective rescheduling algorithms and local rerouting strategies in a tabu search scheme. We alternate a fast heuristic and a truncated branch and bound algorithm for computing train schedules within a short computation time, and investigate the effectiveness of using different neighborhood structures for train rerouting. The computational experiments are based on practical size instances from a dispatching area of the Dutch railway network and include complex disturbances with multiple late trains and blocked tracks. Several small instances are solved to optimality in order to compare the heuristic solutions with the optimum. For small instances, the new tabu search algorithms find optimal solutions. For large instances, the solutions generated by the new algorithms after 20s of computation are up to more than 15% better than those achieved within 180s by the previous version of ROMA.