A MIP-based Local Search Method for the Railway Rescheduling Problem
A MIP-based Local Search Method for the Railway Rescheduling Problem
复制标题
DOI：
10.1002/net.20384
复制
发表时间：
2011-01-01
期刊：
影响因子：
2.1
通讯作者：
Gueye, Serigne
中科院分区：
文献类型：
--
作者：
Acuna-Agost, Rodrigo;Michelon, Philippe;Gueye, Serigne
由于运营和不可预测的原因，轨道交通系统中每天都会发生许多小事故。它们中的大多数都会对当地产生影响，但在某些情况下，主要是在密集的网络中，最小的中断可以扩散到整个网络，并对列车时刻表产生重大影响。在本文中，我们将铁路调整问题描述为在发生一次或几次事故后，通过最小化影响的措施来寻找新的列车时刻表的问题。我们通过混合整数规划(MIP)的形式研究了该问题的解。由于仅使用标准的MIP求解器不可能精确地求解该问题，我们提出通过用局部分支型切割对整数变量进行硬性和软性固定来限制原始无中断调度的搜索空间。将该方法的不同变体与位于法国和智利的两个不同网络中的右移重新调度策略进行了比较。实验结果还被用来研究不同目标对总时延的影响。(C)2010年威利期刊网络，第57(1)卷，2011年69-86期
For operational and unpredictable reasons, many small incidents occur day after day in rail transportation systems. Most of them have a local impact, but, in some cases, mainly in dense networks, minimal disruptions can spread out through the whole network and affect significantly the train schedules. In this article, we present the railway rescheduling problem as the problem of finding a new schedule of trains after one or several incidents by minimizing some measure of the effect. We investigate the solution of this problem through a mixed-integer programming (MIP) formulation. Because of the impossibility for solving it exactly just using a standard MIP solver, we propose to limit the search space around the original nondisrupted schedule by hard and soft fixing of integer variables with local-branching-type cuts. Different variations of the method are compared to a right-shift rescheduling policy in two different networks located in France and Chile. The experimental results are also used to study the impact of different objectives on the total delay. (C) 2010 Wiley Periodicals, Inc. NETWORKS, Vol. 57(1), 69-86 2011