在铁路系统中, 经常有各类异常事件影响列车正常运行. 以异常事件发生的位置分类, 可以把它们分为发生在区间的异常事件与发生在车站的异常事件^[1]. 这两类异常事件中发生在区间上发生的异常事件造成的影响往往比在车站发生的异常事件更大, 而在发生在区间的异常事件中, 又以区间失效造成的影响更大. 为了避免异常事件带来更坏的影响, 调度员需及时做出最优或次优的调整. 调整涉及到的内容有列车时刻表、乘务计划与列车交路计划, 其中列车时刻调整是首要调整任务^[2].

区间失效后的列车时刻调整问题及相关研究中使用的方法主要有启发式算法、分支定界法、元启发式算法与专业数学优化软件等, 其中启发式算法与分支定界法是最常使用的两种方法^[3]. Josyula等人把解空间表示为树, 并提出以深度优先的搜索策略为基础的顺序启发算法来快速遍历树^[4]. 兰泽康等人提出使用组合列生成算法与分支定界法的分支定价法求解基于列车路径的整数规划模型^[5]. Zhou等人分别使用进化算法与混沌萤火虫算法获得列车时刻调整方案^[6]. 邓念和占曙光等人主要研究了高速铁路列车运行实时调整问题, 然后直接使用CPLEX求解其构建的模型^{[7, 8]}; Hou等研究地铁系统发生异常状况时如何调整列车, 同样使用CPLEX求解^[9]. 彭其渊等人则指出随着列车和车站数的增加, 模型求解呈指数型增长, 直接求解十分困难, 因此他们利用二阶段启发式算法结合CPLEX求解^[10]. 这些经典的方法存在的问题是面对较大规模问题时, 求解时间较长, 算法的实时性较低. 为了提高算法的实时性, 引入变邻域下降算法(Variable Neighborhood Descend, VND)快速解决区间失效后的列车调整问题.

VND是由变邻域搜索算法(Variable Neighborhood Search, VNS)变化而来的一个算法框架, 它以某种方式搜索解的邻域. Shakibayifar与Sheikholeslami使用多目标变邻域搜索算法寻找列车调整问题的帕累托最优集^[11], 本文则利用VND的局部搜索能力, 并定义适用于列车时刻调整的邻域结构, 结合禁忌表提出多阶段变邻域下降算法(Multi Stage Variable Neighborhood Descend, MSVND), 高效地获得不改变列车顺序时的调整后的列车运行时刻.

1 高速铁路区间失效的列车时刻调整模型

双线高速铁路上的列车分向运行, 两个运行方向上的列车互不干扰. 为了简便起见, 本文研究双线高速铁路某一个方向上区间失效后的列车时刻调整问题, 线路上除了全程运行的列车以外, 还有只在线路上部分区间运行的列车.

1.1 模型假设

(1) 区间失效之前的所有列车活动都正常进行;

(2) 一旦区间失效, 失效持续时间可以预测;

(3) 刚好进入失效区间的列车在区间等待区间恢复;

(4) 时间的最小单位为分钟.

1.2 符号说明

某高速铁路的运行指定方向列车的轨道与车站组成有向图 $GA = \left( {S,R} \right)$ , 其中 $S = \{ {s_{{1}}},{s_2},\cdots,{s_N}\}$ 是按指定方向排序的车站集合, $R = \{ ({s_{{1}}},{s_2}),({s_2},{s_3})\cdots, ({s_{{{N - 1}}}}, {s_N})\}$ 是轨道区间的集合, $({s_{{i}}},{s_{i + 1}})$ 表示车站s_i至车站s_i+1的轨道区间, N是线路上的办理客运业务的车站数量.

在GA上运行的列车集合为 $T = \{ {t_1},{t_2},\cdots,{t_M}\}$ , 其中M是列车的数量. T中的任意一列列车t在GA上运行的第一个车站与最后一个车站分别为 $s_t^f$ 与 $s_t^l$ , 其图定到发时刻与调整后的到发时刻分别为:

$ \begin{array}{*{20}{l}} {{O_t} = \{ o_1^t,o_2^t,o_3^t,o_4^t, \cdots ,o_{2N - 1}^t,o_{2N}^t\} ,}\\ {{X_t} = \{ x_1^t,x_2^t,x_3^t,x_4^t, \cdots ,x_{2N - 1}^t,x_{2N}^t\} .} \end{array} $

${O_t}$ 与 ${X_t}$ 都有 ${{2}} N$ 个值, 从索引1至索引 ${{2}} N$ 依次为车站s₁至车站s_N的到站时刻与出站时刻. 如果列车t不在某车站运行, 那么其对应的到站与出站时刻的值为0. 相应地, $E = \{ {e_1},{e_2},{e_3},{e_4},\cdots,{e_{2N - 1}},{e_{2N}}\}$ 依次是列车在车站s₁至车站s_N的进站附加时间、出站附加时间; $G = \{ {g_1},{g_2},{g_3},{g_4},\cdots,{g_{2N - 1}},{g_{2N}}\}$ 依次是列车在车站s₁至车站s_N的最小到站间隔时间、最小出站间隔时间.

其余的参数与变量及其说明如表1所示, 其中 $\beta _t^s$ , $\lambda _{tt'}^s$ , $\varphi _{tt'}^s$ 与 $Q_{tt'}^{{s}}$ 都是变量符号.

1.3 模型构建 1.3.1 基本模型

以最小化列车在各车站的总晚点时间为目标, 可以构建列车运行调整的基本模型如下:

$\min \sum\limits_{i \in D} {\sum\limits_{t \in T} {(x_i^t - o_i^t)} } $

(1)

$ {\rm{s.t.}}\;\;x_i^t = o_i^t\;\;\;\;\forall t \in T,\forall t \in D \cup A:x_i^t \le {r_1} $

(2)

$ x_i^t \ge o_i^t\;\;\;\;\forall t \in T,\forall t \in D:o_i^t \ne o_{i - 1}^t $

(3)

$ \begin{split}& o_{i + 1}^t - o_i^t + \theta _t^{{s^ + }}{e_{i + 1}} + \theta _t^{{s^ + }}{e_i} \le x_{i + 1}^t - y_i^t\\ &s = i \div 2,\forall i \in D,\forall t \in T:s_t^f \le s \le s_t^l \end{split} $

(4)

$ \begin{split} &{h_s}\beta _t^s \le x_{i + 1}^t - x_i^t \le {M^ + }\beta _t^s\\ &s = (i + 1) \div 2,\forall i \in A,\forall t \in T:s_t^f \le s \le s_t^l \end{split} $

(5)

$ \alpha _t^s \le \beta _t^s\;\;\;\;\;\;\forall s \in S,\forall t \in T:s_t^f \le s \le s_t^l $

(6)

式(1)是列车时刻调整的目标; 式(2)表示区间失效之前; 列车按照计划时刻运行; 式(3)表示列车在计划停站的车站的出站时刻不早于其计划出站时刻; 式(4)限定列车的区间运行时分; 式(5)限定若列车在车站s停站, 则其停站时间不能小于最小停站时间, 若列车在车站s不停车, 则列车的停站时间为0; 式(6)表示列车的停站选择约束, 在其计划停站的车站必须停站.

1.3.2 其他约束

除了单列列车的约束条件以外, 还有列车之间因为互相影响而需遵守的一些约束条件.

(1) 出发间隔时间与到达间隔时间约束

$ \left\{ \begin{array}{*{20}{l}} \left| {x_i^t \le x_i^{t'}} \right| \le {g_i}\\ s = \left\lceil {i \div 2} \right\rceil ,\forall i \in A \cup D,\forall t \in T,t' \in T:t \ne t' \end{array} \right. $

(7)

式(7)表示任意两列列车在车站的到站与出站间隔时间都满足最小间隔时间约束.

(2) 出发与到达间隔时间约束

$ \left\{ {\begin{array}{*{20}{l}} {lQ_{tt'}^s(x_{i + 1}^t - x_i^{t'}) + Q_{tt'}^s(x_{i + 1}^{t'} - x_i^t) \ge (Q_{tt'}^s + Q_{tt'}^s)G_s^{d,a}}\\ {\forall s \in S;\forall t,t' \in T:t \ne t',s_t^f \le s \le s_t^l,s_{t'}^f \le s \le s_{t'}^l} \end{array}} \right.$

(8)

式(8)表示两列列车占用车站相同轨道需要满足最小发到间隔时间.

(3) 车站能力约束

$ \left\{ \begin{array}{*{20}{l}} l\displaystyle\sum\limits_{t,t' \in T} {\lambda _{tt'}^s} - \displaystyle\sum\limits_{t,t' \in T} {\varphi _{tt'}^s} \le {C_s} - 1\\ \forall s \in S:t \ne t',s_t^f \le s \le s_t^l,s_{t'}^f \le s \le s_{t'}^l \end{array} \right.$

(9)

式(9)表示列车t在到达车站s的时候, 车站s应有能力为列车t提供服务.

(4) 列车越行约束

$ \left\{ \begin{array}{*{20}{l}} l(x_{i + 1}^{t'} - x_{i + 1}^t)(x_i^{t'} - x_i^t) > 0\\ \forall i \in D;\forall t,t' \in T:t \ne t',s_t^f \le s \le s_t^l,s_{t'}^f \le s \le s_{t'}^l \end{array} \right.$

(10)

式(10)表示列车 $t$ 与 $t'$ 在某站的出站时刻之差与在前一车站的到站时刻之差应同正负, 其意义是列车不能在区间越行.

2 多阶段变邻域下降算法 2.1 初始解

在获得初始解之前, 根据列车的所有图定时刻是否在 ${r_1}$ 之前把列车分为需调整的列车集合 $ {T}_{1} $ 与不需调整的列车集合, 其中 ${T_{{1}}}$ 的列车数量为M₁. 在需调整的列车集合 ${T_{{1}}}$ 中有两类车直接导致线路上的列车受到影响, 一类是在 ${r_1}$ 及之前的某时刻进入区间 $({s_0},s_0^ + )$ 且未在 ${r_2}$ 前离开的列车, 另一类是在时间段 $\left( {{r_1},{r_2}} \right)$ 到达车站 $ {{s}}_{0} $ 的列车, 分别如图1中实斜线与虚斜线所示, 并令它们分别组成集合 $ {T}_{0} $ 与 ${T_{\rm{0}}}^{\prime} $ . 如果没有上述两类列车, 所有的列车能够按照各自的图定时刻运行. 如果有这两类列车的任意一种, 则需要调整列车集合 $ {T}_{1} $ 中列车的时刻, 并且需调整的时刻是大于 ${r_1}$ 的时刻. 令(I_t, J_t)为列车集合 $ {T}_{1} $ 中任意一列列车t的图定到发时刻 ${O_t} = \{ o_1^t, o_2^t,o_3^t,o_4^t,\cdots,o_{2N - 1}^t,o_{2N}^t\} $ 中大于 ${r_1}$ 的时刻的起止索引, I_t与J_t分别是大于 ${r_1}$ 的时刻的最小索引与最大索引. 例如某列车在车站 $ {s}_{0} $ 与车站 $ {s}_{N} $ 之间的所有时刻都需调整, 它的起止索引为(1, 2N).

本文使用右移法获得算法的初始解, 该方法把图定的大于 ${r_1}$ 的所有时刻加上某时间长度, 相当于大于 ${r_1}$ 的所有时刻在列车运行图上整体向右移动了某时间长度. 假设集合 $ {T}_{0} $ 中的列车到达车站 $ {{s}}_{0}^{+} $ 的时刻最早为 ${r_1}$ , 集合 ${T_0}^{\prime} $ 中的列车从 $ {{s}}_{0} $ 出站的时刻最早为 ${r_1}$ , 则右移的时间长度如下:

$ \max (\max ({r_2} - o_{2*s_0^ + - 1}^{{t_1}}),\max ({r_2} - o_{2*{s_0}}^{{t_2}})) \;\;{t_1} \in {T_0},{t_2} \in {T_0}^{\prime} . $

2.2 多阶段变邻域下降算法 2.2.1 第1阶段变邻域下降算法

(1) 邻域结构

为列车集合 $ {T}_{1} $ 中的每列列车t定义一个与其图定时刻 $ {O}_{t} $ 等长的整体平移邻域结构 $ {\cal{N}}_t$ , 在其起止索引(I_t, J_t)范围内的值为−1, 其余值为0, 例如某列车从车站 ${s_0}$ 到车站 ${s_N}$ 的全部时刻都需调整, 其邻域结构为{−1,−1,−1,−1,…,−1,−1}, 其意义是列车t所有需调整的时刻在列车运行图中都整体向左平移1分钟.

因为运行时刻在前的列车影响运行时刻在后的列车、运行位置在前方的列车影响运行位置在后方的列车, 优先平移运行时刻与运行位置在前方的列车可以加快邻域搜索. 因此列车集合 $ {T}_{1} $ 对应的整体平移邻域结构集合 $ {\cal{N}}\_{T_1}$ 中邻域结构按照列车的起始索引与索引对应的时刻排序.

(2) 禁忌表

在对列车集合 $ {T}_{1} $ 中的列车进行邻域搜索的过程中, 当某列车恢复到其图定时刻时, 将该列车加入到禁忌表中, 在禁忌表中的列车不再进行邻域搜索.

(3) 约束条件

列车图定时刻 ${O_t}$ 隐式地包含了列车安全运行的约束条件, 在列车时刻整体平移的过程中不需要检验邻域中的解是否满足模型中的所有约束条件, 只需遵守式(3), 式(7), 式(9)就能保证列车安全运行.

基于前述邻域结构、禁忌表与约束条件设计的第1阶段多邻域下降算法的伪代码如算法1.

算法1. 第1阶段多邻域下降算法

输入: $\scriptstyle X{\rm{ = }}({X_t}_{_1},{X_{{t_{{2}}}}},\cdots,{X_{{t_{M1}}}}),\;\;\; {\cal{N}}\_{T_{{1}}} = ({\cal{N}}\_{t_1},{\cal{N}}\_{t_2}, \cdots ,{\cal{N}}\_{t_{M1}})$ ,

1 Tabu: = Ø

2repeat

3　 for k=1 to M₁

4　　change = True

5　　while change do

6 　　　 $\scriptstyle {X_{{t_k}}}^{\prime} : = {\cal{N}}\_{t_k}({X_{{t_k}}})$

7　　　 if $\scriptstyle {X_{{t_k}}}^{\prime}$ 满足各种约束条件 then

8　　　　 $\scriptstyle {X_{{t_k}}}$ $\scriptstyle : = {X_{{t_k}}}^{\prime}$

9　　　 else then

10　　　change = False

11　　 end

12　　 if $\scriptstyle {X_{{t_k}}}{\rm{ = }}{{{O}}_{{{{t}}_k}}}$ then

13　　　 $\scriptstyle Tabu:=Tabu\cup {t}_{k}$

14　　 end

15　 end

16 M₁:=在列车集合 $\scriptstyle {T}_{1}$ 中但不在禁忌表Tabu中的列车数量;

17 until 某列车在第1次没有更优解与第2次没有更优解之间其他列车也没有更优解.

算法1中步骤2至17调整 ${T_{{1}}}$ 中所有列车直至它们在对应的邻域结构中没有更优解. 其中步骤3至 13按照指定规则依次调整 ${T_{{1}}}$ 的一列列车, 步骤5至11循环调整列车 ${{{t}}_{{k}}}$ , 如果列车的新时刻 ${X_{{t_k}}}^{\prime} $ 能满足约束条件就一直搜索其邻域, 否则就跳出循环; 步骤12至14表示列车 ${{{t}}_{{k}}}$ 调整后的时刻与原计划时刻相等时, 将列车加入到禁忌表中.

2.2.2 第2阶段变邻域下降算法

第2阶段的算法流程与第1阶段一致, 区别只是第2阶段调整区间失效后仍在车站 ${s_{{1}}}$ 与 ${s_0}$ 之间运行的列车. 假设这些列车组成集合 ${T_{{2}}}^{\prime} $ , 令列车集合 ${T_{{2}}}^{\prime} $ 中的列车调整的起止索引为 $\left( {I_{{t}}^2,J_t^2} \right)$ , 其中 $I_{{t}}^2={I_t}$ , $J_t^2 = \min (2 * {s_0} - 1,{J_t})$ .

(1) 邻域结构

为列车集合 ${T_{{2}}}^{\prime} $ 中的每列列车t定义一个与 $ {O}_{t} $ 等长的部分平移邻域结构, 在索引范围 $\left( {I_{{t}}^2,J_t^2} \right)$ 内的值为–1, 其余则为0.

(2) 禁忌表

如果 ${T_{{2}}}^{\prime} $ 中的列车t在其调整的起止索引范围 $ ({I}_{t}^{2}, {J}_{t}^{2}) $ 内恢复图定时刻, 将列车t加入到第2阶段禁忌表中, 在第2阶段邻域搜索中不再搜索该列车.

(3) 约束条件

第2阶段变邻域下降算法需要遵守式(3), 式(5), 式(7)–式(9)表示的约束条件.

2.2.3 第3阶段变邻域下降算法

第3阶段调整的列车是 ${T_{{2}}}$ 中不在第2阶段禁忌表中的列车或在禁忌表中而其终止索引 ${J_t} \ge 2 * {s_0} - 2$ 引的列车, 假设它们组成集合 ${T_3}$ , ${T_3}$ 中列车数量为 ${M_3}$ , 其中的列车t需要调整时刻的起止索引为 $ ({I}_{t}^{3},{J}_{t}^{3}) $ . 如果列车t在第2阶段禁忌表中而其终止索引 ${J_t} \ge 2 * {s_0} - 1$ , 那么列车t的起止索引更新为 $(2 * {s_0} - 1,{J_t})$ , 其余列车的起止索引不变.

(1) 邻域结构

为列车集合 ${T_3}$ 中的每列列车t定义一系列与 $ {O}_{t} $ 等长的邻域结构. 如果列车t的起始索引 $I_{{t}}^{{3}}$ 对应的是到达时刻, 为该列车定义一个到达平移邻域结构, 该索引 $I_{{t}}^{{3}}$ 对应的值为−1, 其余值为0; 然后定义 $\left( {J_t^{{3}} - I_t^3 - 1} \right) \div 2$ 个发到平移邻域结构, 这些邻域结构分别在索引 $\left( {I_{{t}}^{{3}} + 1,I_{{t}}^{{3}} + 2} \right)$ 、 $ \left( {I_{{t}}^{{3}} + 2,I_{{t}}^{{3}} + 3} \right) $ 等对应位置取值为−1, 其余取0. 如果列车t的起始索引 $I_{{t}}^{{3}}$ 对应的是出发时刻, 则直接定义 $\left( {J_t^{{3}} - I_t^3} \right) \div 2$ 个发到平移邻域结构, 它们分别在索引 $\left( {I_{{t}}^{{3}},I_{{t}}^{{3}}{{ + 1}}} \right)$ 、 $\left( {I_{{t}}^{{3}} + 2,I_{{t}}^{{3}} + 3} \right)$ 等对应位置取值为−1, 其余取值为0. 因此列车集合 ${T_3}$ 中的列车t具有一个邻域结构集合 ${\cal{N}}\_t$ , 集合中至少有一个邻域结构.

(2) 约束条件

第3阶段变邻域下降算法需要遵守式(3), 式(5), 式(7)–式(9)表示的约束条件.

第3阶段变邻域下降算法的伪代码如算法2.

算法2. 第3阶段多邻域下降算法

输入: $\scriptstyle X{\rm{ = }}({X_{{t_1}}},{X_{{t_{{2}}}}},\cdots,{X_{{t_{{M_{\rm{3}}}}}}}),$ $\scriptstyle {\cal{N}}\_{T_3} = ({\cal{N}}\_{t_1},{\cal{N}}\_{t_2}, \cdots ,{\cal{N}}\_{t_{N3}})$

1 $\scriptstyle k: = \min (I_{{t_{{1}}}}^3,I_{{t_2}}^3,\cdots,I_{{t_{M{\rm{3}}}}}^3)$ $\scriptstyle {t_{{1}}},{t_2},\cdots,{t_{{M_3}}} \in T$

2 repeat

3　 for $\scriptstyle s = \left\lfloor {(k + 1) \div 2} \right\rfloor$ to ${s_N}$

4　　 $\scriptstyle T_{\rm{3}}^s: =$ $\scriptstyle {T_3}$ 中索引 $\scriptstyle I_t^3 \le 2 \times s \le J_t^3$ 的列车组成的集合

5　　 $\scriptstyle M_{\rm{3}}^s: =$ 列车集合 $\scriptstyle {T}_{3}^{s}$ 中元素个数

6　　 for m=1 to $\scriptstyle M_{\rm{3}}^s$

7　　　change = True

8　　　 while change do

9　　　 $\scriptstyle {X_{{t_{{m}}}}}^{\prime} : = {\cal{N}}\_t_m^s({X_{{t_{{m}}}}})$ $\scriptstyle {t_{{m}}} \in T_{\rm{3}}^s$ ,

　　　 $\scriptstyle {\cal{N}}\_t_m^s$ 为 $\scriptstyle {\cal{N}}\_{t_m}$ 中车站s对应的邻域结构

10　　　 if $\scriptstyle {X_{{t_{{m}}}}}^{\prime}$ 满足各种约束条件 then

11　　　　 $\scriptstyle {X_{{t_{{m}}}}}: = {X_{{t_{{m}}}}}^{\prime}$

12　　　 else then

13　　　　change = False

14　　　 end

15　　 end

16　 end

17 until 在列车集合 $\scriptstyle {T}_{3}$ 中的任意列车的任意邻域中搜索都不能获得更优解.

2.2.4 调整阶段

本阶段针对列车t在某车站s原计划不停车而调整后到达时刻与出发时刻不同的情况. 若满足条件的列车t在车站s的出发时刻与到达时刻之差大于等于 ${h_s}{\rm{ + }}{{{e}}_{s \times 2}} + {e_{s \times 2 - 1}}$ 且满足其他约束条件, 令其在车站s的停站计划 $\beta _t^s$ 为1; 否则, 令到达时刻与到达时刻等于它们两个时刻之间最小的且满足约束条件的时刻.

3 实例分析

以西成客运专线上行方向为例, 根据2019年7月某日上线运行的列车进行实例分析. 算法基于Python3.6实现, 所有实验都使用CPU为Intel(R) Core(TM) i7-7500U 2.70 GHz, 内存为8 GB的计算机完成.

3.1 数据准备

西成客运专线上行方向办理客运业务的车站共有22个, 车站将线路划分为21个区间. 当日上线运营的列车有89列, 其中44列全程运行, 其余45列只在西成客运专线某段运行.

算例的其他参数按如下规则设置. 两列列车同一车站的到达间隔时间与出发间隔时间都为2分钟, 车站使用相同到发线的发到间隔约束时间为3分钟. 青川站的起停附加时间为3分钟, 其余车站的起停附加时间为2分钟.

3.2 实验及对比分析

实验设置4种基本失效场景, 4种场景由两类失效区间(绵阳至青莲, 宁强南至汉中)与两类失效开始时刻(10:00, 16:00)两两组合而成, 每种失效场景下又分别对应20, 60, 120分钟3类失效持续时间. 此外, 使用CPLEX获得上述多种失效场景下的列车停止结果并进行对比分析. CPLEX求解时间设置为3小时, 其余保持默认设置, 不包含约束条件(8). 由MSVND与CPLEX获得的列车调整结果如表2所示.

由表2可以看出, MSVND在获得列车调整结果上展示了优秀的效率. 相同失效区间与失效开始时刻下, 计算时间随着失效持续时间增加而增加. 在所有失效场景中(宁强南至汉中, 10:00, 120)的计算时间最长, 共20.765 s; 失效持续时间为20 s的场景的最长计算时间是 3.322 s. 此外, 从表2可以看出第一阶段计算时间占比都大于60%, 且失效持续时间为20与60分钟时, 该占比大于80%.

由表2中目标值与CPLEX求解目标值进行比较可以看出, M-S VND得到的列车运行时调整结果与CPLEX得到的结果差别较小. 在计算时间方面, CPLEX计算时间只有(宁强南至汉中, 16:00, 20)的计算时间小于3小时, 其余场景在使用CPLEX求解时在3小时内都未完成求解. 与MSVND相比, CPLEX求解耗费的计算时间太多, 反应了MSVND在计算时间方面优秀的性能.

4 结论与展望

将多阶段变邻域下降算法应用到区间失效后的列车运行时刻调整问题, 实验证明算法调整的结果与全局最优结果相比没有差距, 同时其计算时间又有显著的提升, 表明了算法在列车运行时刻调整问题中的有效性与实时性. 第一阶段快速确定哪些列车恢复到图定时刻, 可以结合其他方法对未恢复到图定时刻的列车进行调整, 减少其他方法直接调整的范围.