列车到发不确定的客站咽喉利用与股道分配
刘伟, 朱晓宁, 李燕晶
北京交通大学 交通运输学院,北京 100044

第一作者:刘伟(1984—),男,湖北宜昌人,博士生.研究方向为运输组织优化. email: 13114210@bjtu.edu.cn

摘要

研究了列车到发时刻不确定条件下的铁路客站咽喉利用优化与股道分配问题.首先,建立了基于不确定列车运行图的咽喉利用与股道分配优化模型,模型考虑股道占用时间与均衡使用性,满足列车、咽喉、股道三者的耦合关系.然后分析并统计了不确定列车运行图的列车到、发站时刻的均值与方差,通过函数模拟的形式抽离出列车时刻表.此外,考虑到问题的NP-hard性,设计了基于模拟退火算法的启发式算法.最后,以宝鸡车站一个阶段计划内的咽喉利用与股道分配问题为实例进行了仿真验算.

关键词: 铁路运输; 客运站; 咽喉利用; 股道分配
中图分类号:U291.6 文献标志码:A
Utilization of bottleneck sections and track allocation in railway stations with train arrival and departure uncertainty
LIU Wei, ZHU Xiaoning, LI Yanjing
School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044,China
Abstract

This paper studies the utilization of bottleneck sections and track allocation problems (UBSTAP) for large railway passenger stations under uncertain train arrival/departure at/from stations. First, an integrated model of the UBSTAP for large railway passenger stations under an uncertain scenario is developed. The UBSTAP model considers the occupation times of tracks and their occupation frequencies. In addition, the relationships of train-bottleneck-track are mathematically proposed to represent train routes. After processing the average and variance of train arrival and departure times for one month’s data from Baoji railway station, the train arrival and departure times are mathematically represented by functions. Meanwhile, considering the NP-hardness of the problem, a simulated annealing based heuristic algorithm is developed to solve the UBSTAP model. Finally, a case study of Baoji railway station is carried out to illustrate the effectiveness of the model and the algorithm.

Keyword: railway transportation; railway passenger station; utilization of bottleneck sections; track allocation

运行图是铁路列车在路网中运行的基本要素, 它规定各车次列车占用区间的程序, 列车在每个车站的到达、出发或通过时刻, 列车在区间的运行时间及在车站的停站时间等, 是全路组织列车运行的基础.然而, 由于气候、设备故障等原因经常造成列车晚点, 使列车不能按初始运行图行驶, 出现这种状况时, 铁路客站的咽喉利用与股道分配问题与正常运行条件下的分配将有所不同.

针对铁路客站咽喉利用与优化问题, 国内外学者做了很多相关研究.张嘉敏等[1]利用FTHNs-Conflict Graph双层模型解决列车占用车站股道时序优化问题.Kang等[2]将车站股道分配问题看成时间上具有限制的排序问题, 并说明到发线运用属于NP-hard问题.Carey[3]建立了到发线运用的混合整数规划模型, 初次尝试解决到发线运用问题.青学江等[4]将区段站到发线运用优化为复杂的非线性组合优化问题, 用实例验证并使用遗传算法得出计算结果优于人工安排.吕红霞等[5]建立了计算机编制到发线运用计划的二次0-1规划模型, 并将该模型化解为两个相对简单的0-1规划子模型来求解.Zwaneveld等[6]用点包装问题描述到发线运用问题, 建立了0-1整数规划模型.Cardillo等[7]将客运站的到发线分配优化问题转化为kL-list τ 图染色模型.谢楚农等[8, 9]将客运站到发线分配优化模型分为3个子模型, 其优化目标分别为方便旅客乘降、保障列车技术作业安全、有效利用车站行车技术设备, 并采用多目标规划原理和分支定界法进行求解.刘启钢等[10]对大型铁路客运站到发线运用方案的计算机辅助编制方法进行了研究.雷定猷等[11]分析了客运站旅客列车到达和发车作业的特点, 采用分支定界、定性-定量分析法相结合方法进行模型求解.

事实上, 列车因为天气、设备故障等造成列车到发时刻不确定的情况较多, 而目前针对不确定情况的铁路客站咽喉利用优化与股道分配研究较少, 鉴于此, 本文作者考虑股道占用时间与均衡使用性, 建立不确定到发时刻的铁路客站咽喉利用优化与股道分配模型, 满足列车、咽喉、股道三者的耦合关系, 使模型与实际情况更相符.利用模型可以判断咽喉两侧的利用率, 为车站改扩建和新增列车对两侧咽喉资源占用分配提供理论依据.

1 列车到发时刻不确定下的优化模型
1.1 研究问题的提出

构成一个铁路网络的基本元素包括线路、车站(节点)、区间.一个铁路车站又可简单地由线路(正线、侧线)、道岔及信号机构成, 由此开展列车的接发车作业, 列车的进站路径由若干道岔组及中间线路构成.在车站具体作业过程中, 列车停靠某条股道的进、出站径路和所遍历的道岔组是相对固定的, 径路、股道、道岔组三者关系为已知条件.列车进、出站的走行路径如图1所示, 当列车停留在股道Ⅰ 作业需依次遍历道岔组a、b、c、d.当列车停经股道上时, 列车出发时刻和到达时刻决定了列车占用股道的时长, 这部分时间由列车运行图决定, 而在突发故障或其他情况带来列车运行早到或晚点造成列车到发时刻不确定时, 将对车站咽喉及股道分配与合理利用产生影响, 本文研究列车到发时刻不确定条件下的铁路客站咽喉利用优化与股道分配问题.

图1 铁路网络、车站结构及列车进出站路径Fig.1 Illustration of railway network, station structure and train paths in a passenger station

1.2 数学模型

1.2.1 集合变量定义

D为车站道岔组集合, 任意道岔组dD, D={d|d=1, 2, …, n}, 其中n为道岔组总数; L为阶段计划内到发列车集合, 任意列车lL, L={l|l=1, 2, …, m}, 其中m为该阶段计划内的列车到发总数; G为车站股道集合, 任意股道gG, G={g|g=1, 2, …, r}, 其中r为到发线总数.

t表示时间指针(24小时制); tg-l表示列车l进站时刻与出站时刻之差; xg-l表示列车l停留股道g的0-1变量; t~g-lS表示列车l占用股道g的实际开始时刻; t~g-lE表示列车l占用股道g的实际结束时刻; xd-l表示道岔占用0-1变量; E( t~g-lS)表示列车l占用股道g的开始时刻均值; δ ( tg-lS)表示列车l占用股道g的开始时刻方差; E( t~g-lE)表示列车l占用股道g的结束时刻均值; δ ( tg-lE)表示列车l占用股道g的结束时刻方差; Δ T表示列车进出站占用道岔组时间(假设为常数); Tmin表示安全间隔时间(假设为常数); tg-lmin表示列车l最小停站时间, 为已知条件.

1.2.2 目标函数

1)股道占用时间.

为表示股道占用时间, 引入不确定条件下的列车到、离站时刻函数.其值为列车实际到、离站均值E( t~g-lS)、E( t~g-lE)与方差δ ( tg-lS)、δ ( tg-lE)的权重之和.

t~g-lS=E(t~g-lS)+λ1·δ(t~g-lS)(1)t~g-lE=E(t~g-lE)+λ2·δ(t~g-lE)(2)

式中λ 1λ 2为参数, 用来调整列车到、离站时刻方差.

股道占用时间的目标函数为

minZ1=l=1m(t~g-lE-t~g-lS)·xg-l(3)

式中 t~g-lE-t~g-lS表示列车l占用股道g的时长.

2)股道均衡使用.

股道均衡使用目标函数为

minZ2=g=1rl=1mxg-l-l=1mg=1rxg-lr2(4)

式中: l=1mxg-l表示股道g被所有列车(l=1, …, m)占用的次数之和; l=1mg=1rxg-lr表示股道被列车占用次数的平均值, 其中r为车站股道总数.至此, 采用方差公式表示所有股道被占用的均衡性, Z2值越小, 表示股道使用越均衡.

1.2.3 约束条件

1)股道占用唯一性约束.

可表示成“ 1-1-1” 模式, 即一时段, 一股道, 一列车.具体为在某一时段同一股道只能被一列列车占用.

l=1mxg-l1, t~g-lS-Tmintt~g-lE+Tmin(5)

在时间 t~g-lS-Tmintt~g-lE+Tmin内, 列车l能否停留在股道g, 取决于股道g是否被占用.对∀ l, 当xg-l=1, 则股道处于占用状态; 当xg-l=0, 则股道处于空闲状态.

2)进站列车必须安排股道约束.

g=1rxg-l=1, t~g-lS-Tmintt~g-lE+Tmin(6)

3)最小停站时间约束.

列车l进、出站时刻之差tg-l需要满足一定的停站时间, 以保证列车l在站正常作业.

tg-l=t~g-lE-t~g-lStg-lmin(7)

4)道岔占用唯一性约束.

可表示成“ 2-1-1” 模式, 即两时段, 一道岔, 一列车.

l=1mxd-l1,  t~g-lS-ΔTtt~g-lSl=1mxd-l1,  t~g-lEtt~g-lE+ΔT(8)

在时段 t~g-lS-Δ Ttt~g-lSt~g-lEtt~g-lE+Δ T内, 即列车进、出站遍历左右两侧咽喉道岔组时间段内, 列车l能否占用道岔d, 取决于股道d的状态是否被占用.

5)最小安全时间间隔约束.

为确保列车在站内运行的安全, 还需满足列车安全间隔时间(Tmin)约束.如图2所示, 时间轴标明列车l占用股道g的开始( t~g-lS)与结束( t~g-lE)时刻, 以及两列列车占用同一股道时需满足的最小安全间隔时间, 因此后续列车l'不能停留在(l'-2)、(l'-1)所处的位置.

图2 列车安全间隔时间示意图Fig.2 Illustration of the security interval time

当后续列车l'预停留在前行列车l所停留的股道上, 其到达时刻 t~g-l'S与前行列车离站时刻 t~g-lE之差需不小于安全间隔时间Tmin.

t~g-l'S-t~g-lE-TminM·(xg-l'-1)(9)

式中M为极大整数.

2.3 优化模型

将以上多目标优化模型转化成单目标函数, 考虑到式(3)、式(4)量纲不统一, 引入系数处理.

minZ=α×Z1r×β×Z2(10)

式中: Z1/r表示股道平均占用时间; 股道占用时间的目标函数利用系数α 调整; 股道占用均衡性目标函数利用系数β 调整; 通过调整α β 的值统一量纲.

式(10)和约束条件式(1)、(2), (5)~(9)构成了本文的优化模型.

3 模拟退火算法求解模型

本文研究列车到发不确定条件下的股道分配问题, 鉴于优化目标的非线性特质, 且问题具有NP-hard性, 因此采用模拟退火算法这种启发式算法进行求解.在求解过程中由于决策变量xg-l为0-1变量, 故采取0-1编码来表示列车l与股道g的一一对应关系, 取1表示列车l停留在股道g上, 取0表示不停留, 求解步骤如下.

第一步, 初始化.

1)初始输入.初始温度值T0, 算法停止温度τ , 降温系数ω 以及马尔科夫链长度L为算法的初始输入值.

2)到发时刻处理.用SPSS软件统计车站列车的到发时刻、准点率等, 采用式(1)、式(2)计算列车到发时刻.

3)基础数据读取.读取车站咽喉结构, 输入咽喉道岔组占用时间以及安全间隔时间Δ TTmin.

4)产生初始解.初始化当前温度T=T0, 根据车站图定股道安排, 产生初始解s0, 计算目标函数值f(0), 检查约束条件式(5)~式(9), 若满足条件保留该初始解, 如果不满足通过交叉产生新解, 直至满足约束条件.

第二步, 迭代优化.

1)产生新解.初始解通过交换某列车的停站股道生成一个新的子代解, 两个父代解通过交换某列列车的停站股道产生两个新子代解sn.

2)新解判断.判断以上子代解是否满足约束条件式(5)~式(9), 并计算满足约束条件解的目标函数值f(η ), 计算当前解与前解的目标函数之差Δ f, Δ f=f(η )-f(η -1).若Δ f≤ 0, 则sn 替换sn-1, 否则采用随机概率事件让sn替换sn-1, 概率为ρ =exp(-Δ f/T).

3)迭代终止判断.对于当前温度T, 如果Tτ , 停止; 否则更新T=T× 0.95, 继续进行下一次迭代.

4 实例研究
4.1 案例分析背景

为了测试模型与算法的有效性, 选取宝鸡车站作为案例进行研究与分析.图3为宝鸡站站场示意图, 其中到发线11条(股道VII, VIII号为正线), 道岔组28组.宝鸡车站分为左右两侧咽喉, 左侧咽喉由奇数号道岔组构成(1-3-5-…-25), 右侧咽喉由偶数号道岔组构成(2-4-6-…-28).宝鸡车站为连通式车站, 由左向右行车方向为上行列车方向.此外, 表1为车站内的股道-道岔连通表, 表示列车进站、出站的走行径路.

图3 宝鸡车站站场示意图Fig.3 Map of station bottleneck structure of Baoji railway station

表1 股道-道岔组关系表 Tab.1 Track-groups of turnout connection
4.2 案例优化结果分析

1)均衡性分析.

连续统计宝鸡车站一个月的列车到、发站时刻, 通过SPSS软件对数据处理, 将均值、方差代入模型, 优化后的咽喉区利用及股道分配方案如表2所示.

表2 股道分配及道岔组组成优化结果 Tab.2 Computational results of track allocations and occupied turnouts

表2可以看出, 各股道安排列车数量由原来的[3 1 3 2 5 1 3 2 2 4 2]优化为[2 2 3 2 3 3 3 2 3 3 2], 股道占用频次方差从1.473降低为0.273, 表现为股道使用更加均衡.

2)咽喉通过能力分析.

咽喉占用时间表示咽喉的繁忙程度, 接发一定数量的列车, 当左侧咽喉占用时长大于右侧占用时长, 表明左侧咽喉更为繁忙, 反之则相反.列车通过左侧咽喉的总时长用TL表示, 列车通过右侧咽喉的总时长用TR表示, 两侧咽喉的总时长比用TR/TL表示.根据不同的λ 1λ 2的取值, 通过测试21组不同数据, λ 1λ 2的取值从-0.10~0.10, 计算结果如表3.

表3 车站两侧咽喉通过能力比较 Tab.3 Comparing two bottlenecks carrying capacity

表3可知, 车站左侧咽喉较空闲, 其通过能力较富余, 右侧咽喉较繁忙, 其通过能力较紧张(TR/TL≈ 1.48).根据宝鸡车站站场图3, 车站右侧咽喉由14组道岔组构成, 左侧咽喉含13组道岔组, 在结构上表明车站右侧咽喉较为复杂.因此, 在车站改扩建过程中应重点考虑扩大右侧咽喉的通过能力, 此方法也为车站两侧咽喉能力判断提供了理论依据.同时, 当增加进站作业列车数量时, 列车应尽量安排至右侧咽喉资源占用较小的股道作业.

5 结语

本文针对列车到发时刻不确定条件下的铁路客站咽喉利用优化与股道分配问题, 建立了基于不确定列车到发时刻的咽喉利用与股道分配优化模型, 设计了基于模拟退火算法的启发式算法, 以宝鸡站为例计算结果验证了模型的合理性.本研究能够判断车站两侧道岔组的应用情况, 对于车站的改扩建、股道的编排调整有一定的理论指导作用.考虑到列车准点率问题, 图定列车进、出站作业方案的不合理性可导致列车的进一步晚点, 因此, 在后续可针对车站股道分配方案调整后对列车运行的二次影响展开研究.

The authors have declared that no competing interests exist.

参考文献
[1] 张嘉敏, 韩宝明. 铁路列车占用车站股道时序优化研究[J]. 交通运输系统工程与信息, 2011, 11(3): 100-107.
ZHANG J M, HAN B M. Optimization on the occupation order for trains on tracks of the railway station[J]. Journal of Transportation Systems Engineering and Information Technology, 2011, 11(3): 100-107. (in Chinese) [本文引用:1]
[2] KANG L J, WU J J, SUN H J. Using simulated annealing in a bottleneck optimization model at railway stations[J]. Journal of Transportation Engineering, 2012, 138(11): 1396-1402. [本文引用:1]
[3] CAREY M. A model and strategy for train pathing with choice of lines, platforms, and routes[J]. Transportation Research Part B Methodological, 1994, 28(5): 333-353. [本文引用:1]
[4] 青学江, 马国忠. 遗传算法在区段站到发线的应用研究[J]. 西南交通大学学报, 1998, 33(4): 387-393.
QING X J. MA G Z. Application of GA to arrival and departure lines in district stations[J]. Journal of Southwest Jiaotong University, 1998, 33(4): 387-393. (in Chinese) [本文引用:1]
[5] 吕红霞, 倪少权, 纪洪业. 技术站调度决策支持系统的研究——到发线的合理使用[J]. 西南交通大学学报, 2000, 35(3): 255-258.
LYU H X, NI S Q, JI H Y. The study on DSS of the technical station dispatching—rationally utilizing reception and departure siding[J]. Journal of Southwest Jiaotong University, 2000, 35(3): 255-258. (in Chinese) [本文引用:1]
[6] ZWANEVELD P, KROON L G, HOESEL S P M V. Routing trains through a railway station based on a node packing model[J]. European Journal of Operational Research, 1997, 128(1): 14-33. [本文引用:1]
[7] CARDILLO D D L, MIONE N K. L-list colouring of graphs[J]. European Journal of Operational Research, 1998, 106(1): 160-164. [本文引用:1]
[8] XIE C N, LI X H. Optimization research for utilization of arrival and departure tracks in railroad passenger station[J]. China Railway Science, 2004, 25(5): 130-133. [本文引用:1]
[9] 谢楚农. 客运站旅客列车运行组织优化[D]. 长沙: 中南大学, 2010.
XIE C N. Optimization method on running organization of passenger trains in railway station [D]. Changsha: Central South University, 2010. (in Chinese) [本文引用:1]
[10] 刘启钢, 杜旭升, 朱亮. 大型铁路客运站到发线运用方案计算机辅助编制方法研究[J]. 铁道运输与经济, 2010, 32(11): 73-76.
LIU Q G, DU X S, ZHU L. Study oncomputer auxiliary program method for arrival-departure track application plan of large-scale railway stations[J]. Railway Transport and Economy, 2010, 32(11): 73-76. (in Chinese) [本文引用:1]
[11] 雷定猷, 王栋, 刘明翔. 客运站股道运用优化模型及算法[J]. 交通运输工程学报, 2007, 7(5): 84-87.
LEI D Y, WANG D, LIU M X. Optimization model and algorithm of utilization of arrival and departure tracks in railroad passenger station[J]. Journal of Traffic and Transportation Engineering, 2007, 7(5): 84-87. (in Chinese) [本文引用:1]