﻿ 基于变邻域下降的列车运行时刻调整算法
 计算机系统应用  2020, Vol. 29 Issue (10): 167-172 PDF

Train Rescheduling Algorithm Based on Variable Neighborhood Descent
ZUO Yi-Meng
School of Information Science and Engineering, Chongqing Jiaotong University, Chongqing 400074, China
Abstract: The blockage of the high-speed railway segment may seriously affect the original timetable of the train. If it happens, the dispatcher needs to adjust the timetable. This study focuses on how to reschedule the timetable without changing the sequence of trains that are affected by the segment blockage. A train rescheduling model is formulated with aiming at minimizing the sum of the delay time of all trains in each station, and all constraints of the model is used to ensure the safety of trains. And a multi-stage variable neighborhood descent algorithm is proposed to solve the problem that it takes a long time to get the optimal or suboptimal solution. In the first and second stages of the algorithm, variable neighborhood descent combined with tabu table is used to quickly ascertain the trains which can maintain the original timetable after several adjustments, and then adjust other trains in the third stage. Finally, taking Xi’an-Chengdu Passenger Dedicated Line and the timetable of a single day as an example, the validity and real-time performance of the algorithm is verified by getting the timetable adjusted under various interval failure scenarios.
Key words: segment blockage     train rescheduling     variable neighborhood descent     tabu table

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上运行的列车集合为 $T = \{ {t_1},{t_2},\cdots,{t_M}\}$ , 其中M是列车的数量. T中的任意一列列车tGA上运行的第一个车站与最后一个车站分别为 $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$ 依次为车站s1至车站sN的到站时刻与出站时刻. 如果列车t不在某车站运行, 那么其对应的到站与出站时刻的值为0. 相应地, $E = \{ {e_1},{e_2},{e_3},{e_4},\cdots,{e_{2N - 1}},{e_{2N}}\}$ 依次是列车在车站s1至车站sN的进站附加时间、出站附加时间; $G = \{ {g_1},{g_2},{g_3},{g_4},\cdots,{g_{2N - 1}},{g_{2N}}\}$ 依次是列车在车站s1至车站sN的最小到站间隔时间、最小出站间隔时间.

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.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)

(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)

(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)

(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)

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

 图 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) 邻域结构

(2) 禁忌表

(3) 约束条件

1 Tabu: = Ø

2repeat

3　 for k=1 to M1

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 M1:=在列车集合 $\scriptstyle {T}_{1}$ 中但不在禁忌表Tabu中的列车数量;

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

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

(1) 邻域结构

(2) 禁忌表

(3) 约束条件

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

(1) 邻域结构

(2) 约束条件

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 调整阶段

3 实例分析

3.1 数据准备

3.2 实验及对比分析

4 结论与展望

 [1] 占曙光. 区间通过能力临时失效下高速铁路列车运行实时调整模型与算法研究[博士学位论文]. 成都: 西南交通大学, 2016. [2] Cacchiani V, Huisman D, Kidd M, et al. An overview of recovery models and algorithms for real-time railway rescheduling. Transportation Research Part B: Methodological, 2014, 63: 15-37. DOI:10.1016/j.trb.2014.01.009 [3] Fang W, Yang SX, Yao X. A survey on problem models and solution approaches to rescheduling in railway networks. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(6): 2997-3016. DOI:10.1109/TITS.2015.2446985 [4] Josyula SP, Krasemann JT, Lundberg L. A parallel algorithm for train rescheduling. Transportation Research Part C: Emerging Technologies, 2018, 95: 545-569. DOI:10.1016/j.trc.2018.07.003 [5] 兰泽康, 何世伟, 黎浩东. 铁路网络列车运行调整的优化模型及其分支定价算法. 交通运输系统工程与信息, 2018, 18(1): 179-185. [6] Zhou XZ, Xu W, Zhang Q, et al. Application research for high-speed railway traffic intelligent rescheduling based on chaotic firefly algorithm. Proceedings of the 2018 33rd Youth Academic Annual Conference of Chinese Association of Automation. Nanjing, China. 2018. 258–263. [7] 邓念, 彭其渊, 占曙光. 干扰条件下高速铁路列车运行实时调整问题研究. 交通运输系统工程与信息, 2017, 17(4): 118-123. [8] 占曙光, 赵军, 彭其渊. 高速铁路区间能力部分失效情况下列车运行实时调整研究. 铁道学报, 2016, 38(10): 1-13. DOI:10.3969/j.issn.1001-8360.2016.10.001 [9] Hou ZP, Dong HR, Gao SG, et al. Energy-saving metro train timetable rescheduling model considering ATO profiles and dynamic passenger flow. IEEE Transactions on Intelligent Transportation Systems, 2019, 20(7): 2774-2785. DOI:10.1109/TITS.2019.2906483 [10] 彭其渊, 陆柳洋, 占曙光. 基于突发故障的高速列车运行调整研究. 交通运输工程与信息学报, 2018, 16(1): 1-8, 23. DOI:10.3969/j.issn.1672-4747.2018.01.001 [11] Shakibayifar M, Sheikholeslami A, Jamili A. A multi-objective decision support system for real-time train rescheduling. IEEE Intelligent Transportation Systems Magazine, 2018, 10(3): 94-109. DOI:10.1109/MITS.2018.2842037