第21卷第3期2021年6月
月亮湾风景区交通运输系统工程与信息
Journal of Transportation Systems Engineering and Information Technology
V ol.21No.3
June2021
文章编号：1009-6744(2021)03-0176-11中图分类号：U292.12文献标志码：A DOI:10.16097/jki.1009-6744.2021.03.022
钟明轩，乐逸祥*，周磊山
(北京交通大学，交通运输学院，北京100044)
摘要：复杂高铁站作业计划的编制质量是影响整个路网运输能效发挥的重要因素，为快速编制高质量车站作业计划，分析了各类列车在车站列车和调车作业，构建列车作业链，并描述车站作业计划优化 问题的本质，结合车站布局和轨道电路分布，构建基于微观层面的车站作业计划优化模型；针对实际问题变量巨大，约束条件复杂的特点，将模型转换为对偶形式，在不需要初始解的情况下，通过拉格朗日松弛算法求解，并通过基于对称性破缺规则的分支定界法快速对松弛问题的解可行化，获得可行车站作业计划。以北京南站为例测试模型和算法，计算时间不超过20min，对偶间隙不超过10%，计算结果无冲突，表明该方法能够实现复杂高铁站高质量列车作业计划的快速求解，具有实际应用意义。 关键词：铁路运输；车站作业计划编制；拉格朗日松弛；高速铁路车站；作业优化
Scheduling Method for Integrated Plan of Train Operation and Shunting Operation in High-speed Railway Station
ZHONG Ming-xuan,YUE Yi-xiang*,ZHOU Lei-shan
(School of Traffic and Transportation,Beijing Jiaotong University,Beijing100044,China) Abstract:The quality of train operation plan for complex high-speed railway station is an important factor affecting the transportation efficiency of the high-speed railway network.To generate high-quality station operation plans in short time,this paper analyzes the train operation and shunting operation of all types of trains in the station,and establishes the train operation chain.Based on these,the essence of
station operation planning optimization problem has been described,which can be taken as a resource optimization problem.Then,considering the station layout and track circuit distribution,the study proposes a microscopic optimization model to create station operation plans.In view of the large number of variables and the complex constraints in the problem,the model is transformed into dual form and then solved by the Lagrange relaxation algorithm without initial feasible solution.A branch and bound method based on symmetry breaking rule is used to make the solution of Lagrange relaxation problem feasible.The case study uses Beijing South Railway Station to test the proposed model and algorithm.The calculation time in the case study is within20minutes,the results are feasible and the dual gaps are less than10%.The results show that this method can generate high-quality train operation plan for complex high-speed railway stations effectively and has good potentials for practical applications.
Keywords:railway transportation;station operation plan scheduling;lagrange relaxation;high-speed railway station;
operation optimization
0引言
大型高铁站是高速铁路网中的关键节点，其作业质量影响着整个高铁路网的运输效率。大型高铁站通常站场规模大，接入方向多，结构复杂，咽喉
收稿日期：2021-01-15修回日期：2021-04-02录用日期：2021-04-06
基金项目：国家自然科学基金高铁联合基金/High-speed Rail Joint Fund of National Natural Science Foundation of China (U1834211，U1934216)；中国铁路北京局集团有限公司2020重大项目/Research Project of China Railway Beijing Group Co. Ltd.(2020AY01)。
作者简介：钟明轩(1994-)，男，甘肃嘉峪关人，博士生。*通信作者：**************
第21卷第3期高铁站列车和调车作业计划一体化编制方法区平行进路多，其接发车数量、站内作业种类和作业复杂度都远超一般车站，站内列车作业(进出站、站台停车等)和调车作业(转线、出入段等)往往会相互影响，冲突频繁，严重影响车站作业效率和质量。虽然某些大站大多数情况下可以将各车场独立考虑，并通过运行图为不同方向列车给定列车径路和站内经由车场，但是在各车场之间，特别是咽喉区，仍可能存在大量作业交叉干扰，因此，在考虑分方向指定列车作业方案的同时，仍需要将整个大站作为一个整体建模优化。车站作业计划作为车站运输组织的主要依据，是保障车站运输生产顺利进行的关键因素。车站作业计划的编制和调整通常由人工完成，效率低，且质量难以保证，特别是对于大型高铁站，列车密度大、作业冲突繁杂且相互交织影响范围广，人工调整难度极大。因此，如 何实现复杂高铁站作业计划的快速优化编制，成为铁路运输生产中急需解决的关键问题之一。
本质上，车站作业计划的编制、调整和优化属于作业调度问题(Operation Scheduling Problem,OSP)，核心是根据列车运行图或时刻表为每个列车的各项作业在规定的作业时间合理分配相应的车站“资源”，包括：基础设施(如轨道、站台、闭塞区间等)、机车车辆/动车和人员等，以保证列车在车站按时、无冲突的完成各项技术作业，保障列车运行图的实施。本文不考虑车站作业人员的调度调配问题，OSP 描述为在车站范围内为大量列车作业合理、高效地分配资源，同时，确保无作业冲突的作业
调度问题。
本文针对复杂高铁车站的作业优化问题，综合考虑列车和调车作业一体化的车站作业计划编制的可行性、质量和求解速度；基于车站平面图和轨道电路构建通用的高铁站作业优化模型(Operation Scheduling Model,OSM)；同时，针对实际OSM 具有巨量的变量及约束条件个数，提出一种基于拉格朗日松弛的求解算法，在不需要初始可行解的前提下，实现车站作业计划的快速求解，并通过实例进行验证。
1问题描述
根据列车在高铁站的作业类型将其分为４类：
终到列车、始发列车、通过列车和立折列车。主要调车作业包括：转线、出入段、出入存车线，并基于列车方向、作业车场及股道的不同，细分为不同作业方案的列车。如图1所示，每列列车在站内至少进行一组作业，根据作业类型将其分为静态作业和动态作业。静态作业指列车在股道停留完成的作业，在作业时间内静止；动态作业指列车在站内的走行作业，通常会沿某条进路从起点运行到终点。设定静态作业的作业时间为一个可接受的作业时间窗；对于动态作业，考虑列车在走行过程中往往需要避免中途停止或刻意延长作业时间，实际生产中，作业时间虽然会在小范围内波动，但不会实时进行调整，往往由调度人员给定作业完成时间便不再变化，故将动态作业时间设定为一个能够充分完成作业的、
适当的标准时间值。
图1高铁站作业工序示意
Fig.1Operations illustration for high -speed railway station
列车在站内的列车作业和调车作业视为按照时间顺序连续进行的，为更好地描述列车的站内作业集合，引入作业链的定义。
定义：列车i 的作业集合{}
|o i,j 0≤j ≤τi ，若对于
任意作业j ()0≤j ≤τi -1，均有E i,j =S i,j +1，则称集合
{}|o i,j
0≤j ≤τi
-1为列车i 的作业链C i
。
其中，
i 为列车索引；j 为列车作业索引；o i,j 为列车i 的作业j ；
τi 为列车i 的作业数目；S i,j 、E i,j 177
交通运输系统工程与信息2021年6月
分别为作业o
i,j
的开始、结束时间。如图1所示，高铁站内各类列车的技术作业方案可以描述为将列车和调车等多个作业串联的作业链，形成对应的作业工序图，每个作业的表现形式为资源或进路的占用。根据实际情况，将立折列车视为共用车底的一次终到列车和一次始发列车的组合。基于列车种类及列车径路，可匹配不同的作业链作为输入条件之一，作业链与列车接发方向的进站信号机位置及所衔接车场相关联，从而确定每一项详细作业内容。此时，OSP可以描述为优化站内每次列车每项作业的作业时间和资源占用，在无冲突的情况下实现最大的作业效益或最低的资源使用成本，引入作业链概念后，可表示为按照作业链顺序和时间约束，在解决进路或资源占用冲突的情况下，依次为各项作业规划作业时间、分配资源。
车站的OSP问题属于NP-hard问题，在多项式事件范围内很难求到最优解。目前，学者大多将其视为站台分配问题[1-4]、复杂Job-shop问题[5-7]或资源分配问题[8-11]，目标是基于现有车站作业方案优化到发线运用，进路分配或完成冲突疏解及最小化列车延误等。部分学者研究车站作业计划与列车时刻表的协同优化问题[12-14]，以优化车站资源运用或实现计划的协同编制。
通过对现有研究成果的总结分析发现：目前多数研究只针对到发线运用、接发车等常规列车作业安排，极少考虑站内调车作业，大部分案例以简单车站为主，车站的复杂度、列车作业数目远小于实际情况，对于存在转线、出入段等调车作业的大型车站，模型和算法的适用性有限；大多数求解方法采用启发式算法或结合启发式算法和数学优化算法，很少使用精确算法，较难评估解的质量；绝大多数算法在求解时需要输入初始解，求解效率依赖初始解的质量，实际应用效果有限。
2车站作业优化模型
目前，多数建模方法将站台和到发线视为整体，进路的冲突通过轮询该进路的敌对进路进行检测和疏解，实现问题的简化建模。本文根据车站轨道电路分布，将列车的各类作业进路拆分为若干轨道电路区段(例如：股道、道岔和交叉渡线等)的集合，构建基于微观层面的车站作业优化模型(OSM)，OSM通过微观层面分配占用资源(进路、股道等)，实现精细化的冲突判断和占用成本计算。2.1符号含义
(1)引用下标
i——列车索引，i∈I，I为列车集合；
N——站内列车数目；
j——列车作业索引，j∈J，J为列车作业集合；
k——时间索引，k∈T，T为时间点集合；
h——股道索引，H为站内股道数目；
r——进路索引，r∈R，R为进路集合，进路由站内资源构成(股道，道岔，交叉渡线)，股道可视为特殊进路；
l——道岔索引，L为站内道岔数目；
m——交叉渡线索引，M为站内交叉渡线数目；
w——列车作业方案索引；
n——迭代次数。
(2)参数定义
γ——本站列车作业计划；
γ
i,w
——列车i的作业方案w；
o
i,j
——列车i的作业j；
τ
i
——列车i的作业数目；
A
i
——列车i在本站的到达时间，对于始发列
车A
i=-1；
D
天津市著名景点i
——列车i在本站的出发时间，对于终到列
车D
i
=-1；
T min
i,j
——作业o
i,j
的最小作业时间；
T max
i,j
——作业o
i,j
的最大作业时间；
μ
i
—
—列车i的类型，1为终到列车，0为通过列车，-1为始发列车；
R next()r——进路r可衔接的下一进路集合，R next()r∈R；
R operation()j——列车作业j可占用的进路集合，R operation()j∈R。
(3)决策变量
S
i,j
——作业o
i,j
开始时间；
x
i,j,k,r
—
—列车i的作业j在时间点k占用进路r状态；
δ
i,j,k,h
——列车i的作业j在时间点k占用股道h状态；
θ
i,j,k,l
——列车i的作业j在时间点k占用道岔l状态；
E
i,j
——作业o
i.j
结束时间；
178
第21卷第3期高铁站列车和调车作业计划一体化编制方法νi,j,k ——列车i 的作业j 在时间点k 执行状态；ρi,j,k,m ——列车i 的作业j 在时间点k 占用交叉
渡线m 状态。2.2模型设计
设目标函数为f ()γ，列车i 在当前车站作业方案的集合为γi ，第w 个作业方案γi,w 的效益为ξw ()γi,w ，γi,w ={}
|o i,j,r 0≤j ≤τi ,r ∈R operation ()j ，列车i 的
作业方案γi,w 根据对应作业链生成，各项作业o i,j,r 已确定对应占用进路为r 。令当前站内所有列车的效益之和为f ()γ，对应目标函数为
f ()γ=∑i =1
N ξw ()
γi,w (1)
根据列车类型、接发方向等为列车匹配相应的作业链，生成对应的列车作业方案集合，并根据列车等级，为列车赋予效益值。当列车在作业时间标准内完成作业时，效益最大，不影响车站正常作业；当列车作业时间过长，则会对其他列车作业产生负面影响，时间越长，影响越大，效益值越低；当列车作业时间超过一定阈值，效益值为0，表示该列车作业对车站正常作业产生不可接受的负面影响。优化目标根据当前时刻表，最小化站内列车作业时间，减少作业成本，实现车站能力的最大化运用。列车效益与作业时间的关系通过函数表达。
ξw ()γi,w 与作业时间的关系如图2所示，图中，Γmax
0为列车某一作业的最大效益；T standard
i,j 为列车i 作业j
的标准作业时间，即不会对车站产生负面影响的时间点。对于动态作业，其作业时间固定，效益值为定值；对于静态作业，在规定的标准作业时间内，效益值不变，超过标准作业时间后，其效益值随作业
时间增加而降低。
图2列车i 作业j 的效益曲线
Fig.2Profit curve for operation j of train i
令P 表示原问题(Primal Problem)，Z 表示目
标函数值，则OSM 原始问题模型Model 1(P )为
max Z =f ()γ=∑i =1
N ξw ()
γi,w (2)
约束条件为
∑i
N
∑j =1τi δ
i,j,k,h
≤1,∀k ,h (3)∑i
N ∑j =1τi
θ
i,j,k,l
≤1,∀k ,l (4)∑i
N
∑j =1
τi
ρ
i,j,k,m
≤1,∀k ,m
(5)δi,j,k,h =∑r ∍h
x i,j,k,r ,∀i ,j ,k ,h (6)θi,j,k,l =∑r ∍l x i,j,k,r ,∀i ,j ,k ,l
(7)ρi,j,k,m =∑r ∍m
x i,j,k,r ,∀i ,j ,k ,m
(8)∑i =1
τi
∑r
x
i,j,k,r
≤∑i =1
τi
v i,j,k ,∀i ,k
(9)
∑r ∈R operation ()j
x
i,j,k,r
=v i,j,k ≤1,Vi ,j ,k (10)x i,j,k,r -x i,j,k ′,r -
∑
r ′∈R next ()
r x i,j ′,k ′,r ′≤1-v i,j,k ′-v i,j ′,k ′,
∀i ,j ,k ,r ;j ′=j +1;k ′=k +1
(11)T min
i,j ≤∑k
v i,j,k ≤T max i,j ,∀i ,j
(12)E i,j =S i,j -∑k
三亚当地旅游团哪个好
v i,j,k ,∀i ,j ,k (13)E i,j =S i,j ′,∀i ,j ,j ′=j +1
(14)
()E
i,1
-A i ()1+μi +()S i,τi
-D i ()1-μi =0,∀i
(15)式(2)为OSM 的目标函数，表示站内所有列车作业方案的效益之和。式(3)~式(5)为资源约束条件，表示在任意时间点，站内资源都只能被不超过一个的列车作业占用，占用时间持续到该作业完
成，当某时间点k 的资源占用次数大于1，表示包含该资源的作业进路在此时存在冲突。式(6)~式(8)为当进路被某一列车作业占用时，该进路上的所有资源(包括股道、道岔和交叉渡线等)均被占用。式(9)和式(10)为进路与列车作业之间的关系，只有当列车作业进行时可以占用进路。式(11)为需要接续的进路之间的逻辑约束，表示列车只有在作业进行中才可以占用股道或进路。式(12)~式(15)为列车作业的时间约束：式(12)为作业时间窗，每项作业都必须在作业时间窗内完成；式(13)和式(14)确保列车i 的作业是按照作业链连续进行的，即上一作
业完成立即进行下一作业，时间间隔与等待时间计入上一作业中；式(15)为站内列车的作业方案必须满足列车时刻表上列车在本站的到达/出发时间。
OSM 在实际问题中规模巨大，通过一般启发式方法很难在合理的计算时间内求得精确解，本文引入基于拉格朗日松弛的优化算法求解问题，并通
179
交通运输系统工程与信息2021年6月
过可行化算法实现问题的精确求解。
3基于拉格朗日松弛的算法设计
3.1拉格朗日松弛对偶问题构建
在Model 1(P )中，式(3)~式(5)为资源约束，是
问题最复杂的约束集合，定义不同列车之间的关系，确保最终解的可行性。采用拉格朗日松弛算法可以松弛式(3)~式(5)，表示可以在不考虑不同列车进路冲突的情况下求解问题。令P LR 表示拉格朗日松弛问题(Lagrangian Relaxation Problem),Z LR 表示松弛问题函数值，则得到对应松弛问题模型Model 2(P LR )为
P LR =max Z LR
(16)
Z LR =∑i =1N
ξw ()γi,w +∑k,h λk,h æèçö
ø
÷1-∑i =1N
∑j =1τi
δi,j,k,h +∑k,l φk,l æèçöø÷1-∑i =1N ∑j =1τi
θi,j,k,l +∑k,m εk,m æèçöø
÷1-∑i =1N
∑j =1τi
ρi,j,k,m =∑i =1N
北京疫情太严重了é
ëêξw ()γi,w -∑k,h λk,h ∑j =1
τi
δi,j,k,h -ù
ûú∑k,l φk,l ∑j =1τi
θi,j,k,l -∑k,m εk,m ∑j =1τ
i
ρi,j,k,m +æèçöø
÷∑k,h λk,h +∑k,l φk,l +∑k,m εk,m ,
λk,h ≥0;φk,l ≥0;εk,m ≥0;∀k ,h ,l
(17)满足式(6)~式(15)
引入两个新的变量，即
z i =ξw ()γi,w -∑k,h
λk,h ∑j =1
τi
δi,j,k,h -∑k,l
φk,l ∑j =1
τi
θi,j,k,l -∑k,m
εk,m ∑j =1
τi
ρi,j,k,m
(18)
ℛ=∑k,h
λk,h +∑k,l
φk,l +∑k,m
鞍山千山风景区门票
εk,m
(19)
此时Model 2(P LR P LR )表示为
P LR =max Z LR =∑i =1
N z i +ℛ
(20)
满足式(6)~式(15)
令P LD 表示拉格朗日松弛对偶问题(Lagrangian Relaxation Dual Problem)，则Model 2
(P LR )的松弛对偶问题模型Model 3(-P LD )表示为
P LD =
min
()
λk,h ,φk,l ,εk,m
∑i =1
N
z i +ℛ(21)
满足式(6)~式(15)
拉格朗日乘子λk ,h ，φk ,l 和εk ,m 分别为股道、道
岔和交叉渡线在时间点k 的资源占用惩罚。模型
的上界为P best
LD =min {}
P ()
n LD ，P ()
n LD 表示n 次迭代中所
有的松弛对偶问题解的函数值，下界为
P best =max {}P
()
n ，P
()
n 表示n 次迭代中所有的原问题
解的函数值。在对偶问题-P LD 中，拉格朗日乘子λk,h ，φk,l 和εk,m 的次梯度和资源惩罚乘子值更新公
式为
S ()λk,h =1-∑i =1N
∑j =1
N δi,j,k,h
(22)S ()φk,l =1-∑i =1N
∑j =1N θi,j,k,l
(23)S ()εk,m =1-∑i =1N
∑j =1
N ρi,j,k,m
(24)λ()n +1k,h =max éëù
û
0,λ()n k,h -η()n S ()
λ()
n k,h (25)φ()n +1k,l =max éë
ù
û0,φ()
n k,l -η()
n S ()φ()
n k,l
(26)
ε()
n +1k,m =max éëù
û
最精确几点几分下雨天气预报下载
0,ε()
n k,m -η()
n S ()ε()
n k,m
(27)η()n =βZ ()
n -Z ˉ S ()λ()n k,h 2+ S ()φ()n k,l 2+
S ()
ε()n k,m 2
,0≤β≤2(28)Z ˉ=()
1-α()n P best LD +α()n P best ,0≤α()n ≤1
(29)
式中：β——步长调节因子；
Z ()
n ——第n 次迭代对偶问题P LD 的目标函
数值；
Z ˉ——目标函数值Z 的期望，是当前对偶问题最佳函数值和原问题最佳函数值的凸组合；
α()
n ——初始值为1，
当P best
LD 多次迭代没有改进时可修改；
⋅——欧几里得范数。
式(28)为步长计算公式。
3.2拉格朗日松弛子问题求解
在Model 3(-P LD )中，每轮迭代都会更新乘子
的值，但ℛ为常数，那么当每个z i 取最大值时，对应目标函数Z LR 即为最大值。z i 可以被视为单一列车i 作业方案的效益。此时，主问题被分解为几个求解单一列车最优作业方案的子问题。对所有子问题求最优解后，即可获得对应的松弛解。
单一列车作业方案的求解可以在可扩展的资源时空网络上进行描述，其所有作业方案进路集合称为限制进路集合。如图3所示，终到列车i 自车站边界点b 1进站的可行进路有6条，每条股道停留时间为5~10min ，在每条进站进路的终点可铺画6条弧表示列车停站计划(5~10min)；若从列车所在股道到存车场有ω条进路，则需要再分别铺画ω
180
