高速铁路车站进路分配优化模型与拉格朗日松弛方法

Optimization Model and Lagrangian Relaxation Approach of Train Route Allocation for High Speed Railway Stations

摘要

高速铁路车站通常衔接线路多个方向且技术作业过程复杂，优化列车进路对于提高车站作业计划质量的稳定性意义重大。考虑到车站到发线与咽喉区设备间的连通性与制约性，结合道岔分组方法，构建以咽喉区进路—到发线为研究对象的微观时空网络，以列车占用到发线匹配程度最大化为优化目标，构建考虑时空网络流平衡、设备占用唯一性及不相容性等约束的进路分配时空网络优化模型，将进路分配问题中难以描述的约束转化为网络中弧段与节点的制约关系。利用拉格朗日松弛算法将设备占用不相容性约束松弛到目标函数，将原问题分解为求解单列车的最优到发线运用子问题。最后，以宝鸡南车站为背景进行实例验证，算法运行时长为6.45 s，迭代次数为80次，优化GAP值为1.4%，结果表明所提方法能在较短时间内求得无冲突的列车进路分配方案。

Abstract

As high speed railway stations typically connect multiple directions of lines and involve complex technical operations, optimization of train routes is of great significance for enhancing the stability of station operation planning and quality. In consideration of connectivity and constraints between station arrival-departure tracks and throat area equipment and through a turnout grouping method, a microscopic time-space network was constructed with the throat area route and arrival-departure tracks as the research objects. To maximize the matching degree of train occupancy and arrival-departure tracks, a time-space network optimization model for train route allocation was established in consideration of constraints such as time-space network flow balance, equipment occupancy uniqueness, and incompatibility to transform complex constraints in route allocation into constraints between arcs and nodes in the network. By using the Lagrangian relaxation algorithm, the constraints of equipment occupancy incompatibility were relaxed into the objective function, and the original problem was decomposed into subproblems for solving the optimal arrival-departure track for a single train. Finally, the Baojinan Station was taken as the background for case verification. The algorithm operated for 6.45 s, performed 80 iterations, and achieved an optimized GAP value of 1.4%. These results demonstrate that the proposed method can generate conflict-free train route allocation schemes within a short time.

Graphical abstract

关键词

高速铁路车站 / 进路分配方案 / 时空网络 / 拉格朗日松弛 / 不相容弧集合

Key words

High Speed Railway Station / Train Route Allocation Scheme / Time-Space Network / Lagrangian Relaxation / Incompatible Arc Set

0　引言

高速铁路车站进路分配方案优化问题作为车站作业计划制定的核心环节，对于保障高速铁路运输网络的稳定性与高效性意义重大。一般而言，列车进路分配方案优化的本质为对研究时段内车站接发列车的到发线占用方案及咽喉区进路排列方案进行优化，从而有效提升车站到发线与咽喉区资源利用效率。

到发线运用计划作为车站作业计划的子问题，吸引了大量学者深入研究，如贾文峥等^[1]、单奕嘉等^[2]、姚宇峰^[3]在构建以到发线运用均衡性为目标的到发线运用方案优化模型的基础上，分别采用BT搜索算法、CPLEX求解器以及改进的GA算法进行模型求解。针对车站咽喉区网络优化问题，Rodriguez^[4]、赵茜芮等^[5]、林枫^[6]分别采用车间调度法、进路冲突法以及资源冲突法将车站咽喉区进路分配优化问题进行了相应转化。考虑到车站到发线与咽喉区的制约性与连通性，协同优化成为国内外学者近些年的研究重点。如刘杰等^[7]、陈彦等^[8]以及高全等^[9]均构建了考虑设备运用时空唯一性以及作业安全时间间隔等约束的多目标协同优化模型。赵军等^[10]将包含咽喉区进路指派和时刻调度决策的进路分配优化问题转化为约束指派问题，并设计迭代算法求解。彭其渊等^[11]研究了车站作业受到干扰后的到发线运用调整问题，以列车运行晚点和车站秩序影响综合最小为目标，构建混合整数规划模型，并设计分支定界算法求解。此外，列车时刻表与进路分配协同优化问题受到广泛关注，如Zhang等^[12]、Wang等^[13]、Zhou等^[14]及Meng等^[15]分别构建了晚点情形、客流高峰时期、路网条件以及N-轨道网络条件下的列车时刻表与进路分配方案协同优化模型，并均采用拉格朗日松弛算法求解。

考虑到列车进路分配方案对车站设备时空资源占用的双重依赖性，构建时空网络可将列车在站作业流程转化为列车对时空网络中节点与弧段的占用过程。如白紫熙等^[16]从Job-Shop调度角度出发，将车站作业计划调整问题抽象为基于时空网络的车间调度问题，并采用拉格朗日松弛算法求解，然而其忽略了到发线与咽喉区进路间的连通性。针对既有研究的不足之处，结合道岔分组方法，构建以咽喉区进路—到发线为研究对象的进路分配时空网络优化模型，并采用拉格朗日松弛算法进行模型求解。

1　问题分析

1.1　二级作业过程与列车进路的关系

列车在站办理接发列车和调车等作业时占用车站各项设备所构成的运行径路称为列车进路，车站作业过程与列车进路一一对应^[17]。对于高铁站而言，其主要为始发、终到、停站、通过以及折返5类列车办理技术作业，各种类列车办理作业内容及流程不同，其列车技术作业流程如图1所示。

如图1所示，各种类列车在站作业流程均可拆分为若干项作业串联的工序图，各项作业内容及办理进路如下所示。

（1）接车进路：列车占用车站咽喉区办理接车作业，准备进入到发线，对于始发列车则为出段进路，办理动车组出段作业。

（2）到发线停留：列车占用车站到发线办理旅客乘降及其他技术作业。

（3）发车进路：列车占用车站咽喉区办理发车作业，准备驶离车站，对于终到列车则为入段进路，办理动车组入段作业。

1.2　设备占用时间预处理

为方便后续时空网络模型构建，基于列车实际作业流程，对列车在站各项技术作业流程开始及结束时刻进行适当调整，从而保证各项作业时间的关联度及连续性。基于列车实际到发时刻，以停站通过列车为例对列车各项设备占用时间的调整进行说明。停站列车设备占用时间调整如图2所示。

如图2所示，对接车进路结束时刻T{E}_k^{\mathrm{1}}进行延长，将到发线占用结束时刻T{E}_k^{\mathrm{2}}与发车进路占用开始时刻T{S}_k^{\mathrm{3}}缩短，令其分别与列车k在车站的实际到达时刻T_k^a与出发时刻T_k^d相等，从而保证各项作业的时空连续性。值得说明的是，为避免忽略到发线占用时间对列车实际运行造成影响，引入\epsilon表示到发线占用最小安全时间间隔。此外，其他作业种类列车时间预处理过程与停站通过列车类似，故不再赘述。

1.3　设备占用关系矩阵

为有效降低时空网络规模并避免不可行时空节点及弧段的生成，基于车站平面布局结构及网络拓扑图，生成设备占用关系矩阵。给定研究时段内车站接发列车集合K=\{\mathrm{1,2},\cdots ,q\}，其中q为列车数量，车站到发线集合J=\{\mathrm{1,2},\cdots ,n\}，其中n为到发线数量，咽喉区进路集合I=\{\mathrm{1,2},\cdots ,m\}，其中m为咽喉区进路数量，4类设备占用关系矩阵如下所示。

（1）到发线可连接咽喉区进路矩阵A_{n\times m}，参数a_{ji}为1表示到发线j与咽喉区进路i连通，否则为0。

（2）咽喉区进路关系矩阵B_{m\times m}，参数b_{i{i}^{\text{'}}}为1表示咽喉区进路i与i^{\text{'}}互为敌对进路，否则为0。

（3）列车可占用到发线矩阵C_{q\times n}，参数c_{kj}为1表示列车k可占用到发线j，否则为0。

（4）列车可占用咽喉区进路矩阵D_{q\times m}，参数d_{ki}为1表示列车k可占用咽喉区进路i，否则为0。

给定研究时段列车运行图及到发线固定使用方案，结合各类列车技术作业流程，可分别得到列车可占用设备矩阵及车站设备关系矩阵。值得说明的是，车站设备占用关系矩阵的引入可有效降低时空网络规模及可行解空间，从而有效提升算法收敛速度。

2　微观时空网络构建

基于车站设备占用角度，列车进路包括到发线和咽喉区进路2部分，咽喉区进路由若干道岔组构成，1条咽喉区进路可连接多条到发线，1条到发线同时可连接多条咽喉区进路，故以咽喉区进路-到发线为研究对象。此外，考虑到列车进路分配方案对车站时空资源的双重依赖性，其在站作业过程可表述为从进站端至出站端的一条时空轨迹。将<关键设施，离散时刻>二元组实例作为节点，以关键设施之间的空间联系和时间步进关系作为弧，由此可构建离散的列车进路分配时空网络G=(N,A)。

2.1　时空网络节点

对于研究时段内任意列车k\in K，其均对应子网络G_k=(N_k,A_k)，其中N_k，A_k分别代表列车k可占用的时空节点与时空弧段。为保证其时空网络的完整性，为其分别引入虚拟起点{\sigma }_k与虚拟终点{\delta }_k。此外，结合列车作业流程与列车进路关系，其时空网络节点包含以下6类。

（1）接车进路接入点集合R{A}_k=\{(i,t)|i\in I,t=T{S}_k^{\mathrm{1}},d_{ki}=\mathrm{1}\}。

（2）接车进路发出点集合R{D}_k=\{(i,t)|i\in I,t=T{E}_k^{\mathrm{1}},d_{ki}=\mathrm{1}\}。

（3）到发线接入点集合L{A}_k=\{(i,t)|i\in J,t=T{S}_k^{\mathrm{2}},c_{ki}=\mathrm{1}\}。

（4）到发线发出点集合L{D}_k=\{(i,t)|i\in J,t=T{E}_k^{\mathrm{2}},c_{ki}=\mathrm{1}\}。

（5）发车进路接入点集合W{A}_k=\{(i,t)|i\in I,t=T{S}_k^{\mathrm{3}},d_{ki}=\mathrm{1}\}。

（6）发车进路发出点集合W{D}_k=\{(i,t)|i\in I,t=T{E}_k^{\mathrm{3}},d_{ki}=\mathrm{1}\}。

故列车k的时空节点可表示为：N_k=\{{\sigma }_k,{\delta }_k\}\bigcup R{A}_k\bigcup R{D}_k\bigcup L{A}_k\bigcup L{D}_k\bigcup W{A}_k\bigcup W{D}_k。

2.2　时空网络弧段

给定时空网络节点，将其连接可生成各类时空网络弧段，对于任意列车k\in K，其时空弧段A_k包含起始弧A_k^{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}、进站运行弧A_k^{\mathrm{i}\mathrm{n}}、进站连接弧A_k^{\mathrm{i}\mathrm{n}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{k}}、到发线停留弧A_k^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}、出站连接弧A_k^{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{k}}、出站运行弧A_k^{\mathrm{o}\mathrm{u}\mathrm{t}}以及终止弧A_k^{\mathrm{e}\mathrm{n}\mathrm{d}}7类，构造过程如下所示。

（1）起始弧A_k^{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}=\{(i,t;j,\tau )|(i,t)={\sigma }_k,(j,\tau )\in R{A}_k\}。

（2）进站运行弧A_k^{\mathrm{i}\mathrm{n}}=\{(i,t;j,\tau )|(i,t)=R{A}_{\mathrm{k}},(j,\tau )\in R{D}_k,i=j\}。

（3）进站连接弧A_k^{\mathrm{i}\mathrm{n}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{k}}=\{(i,t;j,\tau )|(i,t)=R{D}_k,(j,\tau )\in L{A}_k,\tau -t=\mathrm{0},a_{ij}=\mathrm{1}\}。

（4）到发线停留弧A_k^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}=\{(i,t;j,\tau )|(i,t)=L{A}_k,(j,\tau )\in L{D}_k,i=j\}。

（5）出站连接弧A_k^{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{k}}=\{(i,t;j,\tau )|(i,t)=L{D}_k,(j,\tau )\in W{A}_k,\tau -t=\mathrm{0},a_{ij}=\mathrm{1}\}。

（6）出站运行弧A_k^{\mathrm{o}\mathrm{u}\mathrm{t}}=\{(i,t;j,\tau )|(i,t)=W{A}_k,(j,\tau )\in W{D}_k,i=j\}。

（7）终止弧A_k^{\mathrm{e}\mathrm{n}\mathrm{d}}=\{(i,t;j,\tau )|(i,t)\in W{D}_k,(j,\tau )={\delta }_k\}。

故列车k的时空弧段可表示为：A_k=A_k^{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}\bigcup A_k^{\mathrm{i}\mathrm{n}}\bigcup A_k^{\mathrm{i}\mathrm{n}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{k}}\bigcup A_k^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}\bigcup A_k^{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{i}\mathrm{n}\mathrm{k}}\bigcup A_k^{\mathrm{o}\mathrm{u}\mathrm{t}}\bigcup A_k^{\mathrm{e}\mathrm{n}\mathrm{d}}。

微观时空网络如图3所示。

如图3所示，基于微观时空网络的构建，将列车在站各项作业流程转化为列车对各类时空节点与弧段的占用过程。通过设备占用关系矩阵的引入，对于任意列车k\in K，其可占用时空节点N_k与时空弧段A_k均需满足设备占用关系矩阵。此外，考虑到各类弧段间的彼此联系与相互制约性，为各列车生成无冲突的时空路径将是研究重点。

3　列车进路分配优化模型

3.1　目标函数

以研究时段内车站接发列车与所占用到发线的匹配程度最大化为优化目标，具体包括列车的速度等级、运行方向、作业种类以及作业时间等指标。根据列车占用车站到发线匹配程度的不同，引入到发线占用费用矩阵进行衡量。

假设列车运行方向集合为S=(\mathrm{1,2},\cdots ,s)，不同运行方向列车占用到发线费用矩阵为E=(e_j^s)，此外，假设列车作业种类集合为T=(\mathrm{1,2},\cdots ,t)，给出不同种类列车占用到发线费用矩阵F=(f_j^t)，假设列车速度等级集合为V=(\mathrm{1,2},\cdots ,v)，给出不同速度等级列车占用到发线费用矩阵G=(g_j^v)。定义列车占用到发线费用系数c_k(a)=\mathrm{m}\mathrm{a}\mathrm{x}(e_j^s,f_j^t,g_j^v)，值得说明的是，当到发线占用费用c_k(a)=\mathrm{\infty }时代表列车k不能占用该到发线。式(1)中，x_k(a)为决策变量，表示列车k是否占用到发线停留弧a\in A_k^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}。

\mathrm{m}\mathrm{i}\mathrm{n}Z=\sum _{k\in K}\sum _{a\in A_k^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}}{c}_k(a)\times x_k(a)(1)

3.2　约束条件

（1）时空网络流平衡约束。流平衡约束作为时空网络构建过程中最基本的约束，其保证任意列车k\in K仅可选择一条时空路径供其占用，且该时空路径必须保证在时间与空间维度上的连续性。

\sum _{(i,t):(i,t;j,\tau )\in A_k}{x}_k(i,t;j,\tau )-\sum _{(i,t):(i,t;j,\tau )\in A_k}{x}_k(j,\tau ;i,t)=\left\{\begin{array}{c}-\mathrm{1}(j,\tau )\in {\sigma }_k,\forall k\in K\\ \mathrm{1}(j,\tau )\in {\delta }_k,\forall k\in K\\ \mathrm{0}\hspace{1em}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\end{array}\right.(2)

（2）设备占用唯一性约束。约束式(3)至(5)保证列车对各类弧段占用的唯一性，即对于任意列车k\in K，其分别仅能占用1条接车进路、1条到发线与1条发车进路。此外，列车k所占用的咽喉区进路与到发线之间必须保持连通性，由于时空网络构建过程中考虑了设备占用关系矩阵，故模型中不再体现设备连通性约束。

\sum _{(i,t;j,\tau )\in A_k^{in}}{x}_k(i,t;j,\tau )=\mathrm{1}\hspace{1em}\forall k\in K(3)

\sum _{(i,t;j,\tau )\in A_k^{out}}{x}_k(i,t;j,\tau )=\mathrm{1}\hspace{1em}\forall k\in K(4)

\sum _{(i,t;j,\tau )\in A_k^{dwell}}{x}_k(i,t;j,\tau )=\mathrm{1}\hspace{1em}\forall k\in K(5)

（3）设备占用不相容性约束。在列车进路分配时空网络优化模型中，2类重要的不相容性约束分别为到发线占用安全时间间隔约束和咽喉区进路占用安全时间间隔约束。其中，咽喉区进路安全间隔约束又分为接车进路之间、发车进路之间以及接发车进路之间的安全间隔约束3类。车站设备占用不相容性约束保证了列车对车站设备时空资源占用的排他性，引入不相容弧集合进行描述。到发线不相容弧集合构造过程如图4所示。

到发线占用安全间隔是指列车占用同一条到发线时需满足最小安全间隔时间h_{\mathrm{1}}，对于任意到发线停留弧a=(i,t;j,\tau )\in A^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}，其不相容弧集合A^{\mathrm{1}}(a)包含与弧段a同属一条到发线且存在时间交叉关系的所有到发线停留弧a^{\text{'}}=(i,t^{\text{'}};j,{\tau }^{\text{'}})\in A_{}^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}，包含以下2种情况。

①当到发线停留弧a=(i,t;j,\tau )\in A_{}^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}为不相容弧集合的右边界时，即t^{\text{'}}\le t，若弧a^{\text{'}}=(i,t^{\text{'}};j,{\tau }^{\text{'}})\in A_{}^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}的出发时刻{\tau }^{\text{'}}大于弧a的到达时刻与到发线安全间隔的差值t-h_{\mathrm{1}}，则弧段a^{\text{'}}与a不相容，该集合表示为。

②当到发线停留弧a=(i,t;j,\tau )\in A^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}为不相容弧集合的左边界时，即t^{\text{'}}>t，若弧a^{\text{'}}=(i,t^{\text{'}};j,{\tau }^{\text{'}})\in A^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}的到达时刻t^{\text{'}}小于弧a的到达时刻与到发线安全间隔的和t+h_{\mathrm{1}}，则弧段a^{\text{'}}与a不相容，该集合表示为。综上，弧a=(i,t;j,\tau )\in A^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}的不相容弧集合A^{\mathrm{1}}(a)可表示为

(6)

咽喉区进路安全间隔约束包含接车进路间、发车进路间及接发车进路间安全间隔3类，其不相容弧集合构造过程与到发线占用不相容弧集合类似，此处不再赘述。分别引入接车进路间、发车进路间、接发车进路间以及发接车进路间安全时间间隔h_{\mathrm{2}}，h_{\mathrm{3}}，h_{\mathrm{4}}及h_{\mathrm{5}}，其不相容弧集合可分别表示为

(7)

(8)

(9)

(10)

故列车占用车站设备不相容弧集合可表示为

A(a)=A^{\mathrm{1}}(a)\bigcup A^{\mathrm{2}}(a)\bigcup A^{\mathrm{3}}(a)\bigcup A^{\mathrm{4}}(a)\bigcup A^{\mathrm{5}}(a)(11)

通过不相容弧集合的引入，列车占用车站设备不相容性约束可表示为

\sum _{a^{\text{'}}\in A(a):a^{\text{'}}\ne a}{x}_k(a\text{'})+\sum _{k\text{'}\in K}{x}_{k\text{'}}(a)\le \mathrm{1}\forall k\in K,a\in A_k(12)

约束式(12)保证列车占用车站设备的不兼容性，即对于任意列车k\in K而言，若列车k选择了除弧段a以外的不相容弧a^{\text{'}}，则其他任意列车k^{\text{'}}\in K不能再占用弧段a。此外，若弧段a的不相容弧a^{\text{'}}\in A(a)没有被列车占用，则弧段a可被其他任意列车占用。

（4）变量域约束。

x_k(a)\in \{\mathrm{0,1}\}\hspace{1em}\forall k\in K,a\in A_k(13)

4　拉格朗日松弛算法

4.1　原问题的松弛

考虑到设备占用不相容性约束为模型中的唯一复杂性约束，涉及多列车间的耦合关系，故将约束式(12)松弛到目标函数，原问题转化为求解不考虑设备占用不相容性约束下的列车与到发线占用匹配程度最大化问题。具体的，对研究时段内任意列车k\in K和弧段a\in A_k引入非负拉格朗日乘子{\lambda }_k(a)\ge \mathrm{0},\forall k\in K,a\in A_k，目标函数如下所示。

\mathrm{m}\mathrm{i}\mathrm{n}LR=\sum _{k\in K}\sum _{a\in A_k^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}}{c}_k(a)\times x_k(a)+\sum _{k\in K}\sum _{a\in A_k}{\lambda }_k(a)\times (\sum _{a^{\text{'}}\in A(a):a^{\text{'}}\ne a}{x}_k(a^{\text{'}})+\sum _{k^{\text{'}}\in K}{x}_{k^{\text{'}}}(a)-\mathrm{1})(14)

基于不相容弧集合的互通性，拉格朗日松弛函数可进一步简化^[18]。

\sum _{a\in A}{\lambda }_k(a)\times \sum _{a^{\text{'}}\in A(a):a^{\text{'}}\ne a}{x}_k(a^{\text{'}})=\sum _{a\in A}{x}_k(a)\times\sum _{a^{\text{'}}\in A(a):a^{\text{'}}\ne a}{\lambda }_k(a^{\text{'}})(15)

\mathrm{m}\mathrm{i}\mathrm{n}LR=\sum _{k\in K}\sum _{a\in A_k^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}}{c}_k(a)\times x_k(a)+\sum _{k\in K}\sum _{a\in A_k}{x}_k(a)\times\sum _{k^{\text{'}}\in K}{\lambda }_{k^{\text{'}}}(a)+\sum _{k\in K}\sum _{a\in A_k}{x}_k(a)\times \sum _{a^{\text{'}}\in A(a):a^{\text{'}}\ne a}{\lambda }_k(a^{\text{'}})-\sum _{k\in K}\sum _{a\in A_k}{\lambda }_k(a)=\sum _{k\in K}\sum _{a\in A_k^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}}{c}_k(a)\times x_k(a)+\sum _{k\in K}\sum _{a\in A_k}{x}_k(a)\times(\sum _{k^{\text{'}}\in K}{\lambda }_{k^{\text{'}}}(a)+\sum _{a^{\text{'}}\in A(a):a^{\text{'}}\ne a}{\lambda }_k(a^{\text{'}}))-\sum _{k\in K}\sum _{a\in A_k}{\lambda }_k(a)(16)

移除非正则子问题，原问题分解为求解单列车的最优到发线运用子问题。

L{R}_k=\sum _{a\in A_k}\overline{c_k}(a)\times x_k(a)(17)

其中，\overline{c_k}(a)表示转换后的列车k占用弧段a的拉格朗日费用。

\overline{c_k}(a)=\left\{\begin{array}{c}{c}_k(a)+\sum _{k^{\text{'}}\in K}{\lambda }_{k^{\mathrm{\text{'}}}}(a)+\sum _{a^{\text{'}}\in A(a):a^{\text{'}}\ne a}{\lambda }_k(a^{\text{'}})\hspace{1em}a\in A_k^{\mathrm{d}\mathrm{w}\mathrm{e}\mathrm{l}\mathrm{l}}\\ \sum _{k^{\text{'}}\in K}{\lambda }_{k^{\text{'}}}(a)+\sum _{a^{\text{'}}\in A(a):a^{\text{'}}\ne a}{\lambda }_k(a^{\text{'}})\hspace{1em}\hspace{1em}\mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}\end{array}\right.(18)

该拉格朗日松弛函数需满足约束式(2)至(5)，显然，由于目标函数对设备占用不相容性约束进行了松弛，故所得解为下界解，部分存在时间交叉关系的列车可能占用相同或具有敌对关系的车站设备，违背设备占用安全时间间隔^[19]。因此，需要通过设计专门的启发式算法，消除设备占用冲突。此外，式中拉格朗日乘子更新采用次梯度法，如下所示。

{\lambda }_k^{q+\mathrm{1}}(a)=\mathrm{m}\mathrm{a}\mathrm{x}\{\mathrm{0},{\lambda }_{{}_k}^q(a)+\frac{Z_{IP}^{\mathrm{\text{'}}(q)}-Z_{LD}^{(q)}}{||s^q||}·{\beta }^q\times(\sum _{a^{\text{'}}\in A(a):a^{\text{'}}\ne a}{x}_k(a^{\text{'}})+\sum _{k^{\text{'}}\in K}{x}_{k^{\text{'}}}(a)-\mathrm{1})\}(19)

4.2　可行化算法

既有研究在设计可行化算法时大多基于优先序列法，即将对偶解中各列车占用弧段的拉格朗日费用值作为其权重系数。考虑到该方法并不适用于列车进路分配优化问题，故基于优先序列法，以各列车可占用时空路径数量为权重系数，核心为识别并消解违背松弛约束的所有冲突，逐次为各冲突列车寻找满足设备占用不相容性约束的最优时空路径。可行化算法如下。

输入拉格朗日对偶解x_k(a)、设备占用关系矩阵及时空网络G(N,A)，

统计存在冲突时空路径列车数量k\_num，固定无冲突列车的解，令其不相容弧费用为+\mathrm{\infty }。当k\_num>\mathrm{0}时，第一步根据各冲突列车可选时空路径数量增序排列；第二步以到发线占用费用最小为目标，为列车k=\mathrm{1}重新寻找无冲突时空路径x_k(a)并将其固定，令弧段a的不相容弧a^{\text{'}}费用为+\mathrm{\infty }；第三步基于当前弧段占用费用矩阵，为其余列车重新分配时空路径；第四步更新存在冲突时空路径的列车数量k\_num，返回第一步。最后输出可行解x_k(a)。

4.3　拉格朗日松弛算法流程

步骤1：初始化。读取设备占用关系矩阵A_{n\times m},B_{m\times m},C_{q\times n},D_{q\times n}，各项作业流程时间标准、既有列车时刻表，生成时空网络G(N,A)。初始化迭代次数q=\mathrm{0}，拉格朗日乘子{\lambda }_k(a)=\mathrm{0}，步长{\beta }^{(q)}=0.05，最优上界UB=+\mathrm{\infty }，最优下界LB=-\mathrm{\infty }。

步骤2：计算并更新下界。利用下界生成算法求解拉格朗日对偶子问题，更新最优下界为LB=\mathrm{m}\mathrm{a}\mathrm{x}\{LB,L{B}^{(q)}\}。

步骤3：计算并更新上界。利用上界可行化算法将拉格朗日对偶解转换为可行解，更新上界为UB=\mathrm{m}\mathrm{a}\mathrm{x}\{UB,U{B}^{(q)}\}。

步骤4：计算\mathrm{G}\mathrm{A}\mathrm{P}值。GAP=(UB-LB)/UB。

步骤5：更新拉格朗日乘子。采用上述方法对拉格朗日乘子{\lambda }_k(a)进行更新。

步骤6：终止条件。若当前循环满足以下任意一条则算法终止：①q>Q(最大迭代次数)；②GAP\le \epsilon(最小\mathrm{G}\mathrm{A}\mathrm{P}值)；③次梯度向量的模长||s^{(q)}||=0；④迭代步长{\beta }^{(q)}\le \delta。否则，转步骤2。

步骤7：输出。输出最优列车进路分配方案x_k(a)。

5　案例分析

5.1　案例背景

以宝鸡南车站为研究背景，对其咽喉区两端道岔进行分组，宝鸡南车站平面布局如图5所示，正线Ⅰ、Ⅱ分别用于接发上、下行通过列车，其余奇数、偶数到发线分别用于办理上、下行其他作业种类列车。选取某日17：00—19：00车站接发的20对列车为研究对象，宝鸡南车站17：00—19：00接发列车时刻表如表1所示。

根据各种类列车在站技术作业流程，给出各项作业过程占用车站设备时间标准如下^[20]：接车进路4 min、发车进路4 min、折返进路4 min、出段进路3 min、入段进路3 min、通过进路3 min。结合既有列车时刻表，可得到各项作业过程开始及结束时刻。此外，给定到发线占用最小安全时间间隔为2 min，咽喉区进路最小安全时间间隔为1 min。

5.2　算例求解

选用Python编程求解，算法运行环境为一台CPU为AMD R7-6800H 3.20 GHz，内存16 GB的个人计算机。算法终止条件参数设置如下：最大迭代次数K=\mathrm{200}，最小\mathrm{G}\mathrm{A}\mathrm{P}值\epsilon =\mathrm{0.001}\mathrm{5}，迭代步长最小值\delta =\mathrm{0.005}。算法运行时长为6.45 s，迭代次数为80次，拉格朗日下界解为228.23，上界解为231.48，优化\mathrm{G}\mathrm{A}\mathrm{P}值为1.4%，优化列车进路分配方案如表2所示。

股道运用方案如图6所示，在满足车站设备占用不相容性约束条件下，优化后的到发线运用方案实现了列车与所占用到发线匹配程度的最大化，验证了模型及算法的有效性。考虑到研究时段内各列车间的耦合性，列车在占用最优到发线时不仅需满足到发线占用安全间隔约束，还需满足咽喉区进路安全间隔约束，故主要基于设备占用不相容性角度对研究结果展开论述。

（1）到发线占用不相容性分析。考虑到车站到发线分方向使用，故到发线占用冲突仅存在于同方向运行列车之间。为满足到发线占用最小安全时间间隔，部分列车需以牺牲到发线占用费用为代价。对于G9次列车而言，根据到发线占用费用最小化原则，其最优股道占用为4道。然而，考虑到G9次列车占用到发线时间与G15次列车存在交叉，故G9次列车不能占用4道，并且由于G9次与G11次列车占用到发线时间存在交叉性，故G9次列车不能占用6道，因此优化后的G9次列车股道占用方案为8道。

（2）咽喉区进路占用不相容性分析。由于到发线分方向使用，根据到发线与咽喉区进路连通关系矩阵可知，咽喉区进路冲突通常发生于同方向运行列车之间。然而，考虑到本站折返列车作业的特殊性，其接车作业与折返作业在同侧咽喉区内完成，故其可能与相反运行方向列车存在进路占用冲突，详细讨论如下所示。

①同方向运行列车相同作业过程之间，如上行终到列车G10与上行停站通过列车G12，其第三项作业过程开始和结束时刻分别为17：38—17：41和17：41—17：45，不满足进路占用安全时间间隔，故不能占用敌对进路，优化后的G10入段进路与G12发车进路分别为V_{\mathrm{16}}\to V_{\mathrm{12}}\to V_{\mathrm{8}}及V_{\mathrm{3}}，二者互为平行进路。

②折返列车第三项作业与同方向运行的其他列车第一项作业过程之间，如下行折返列车G3与下行始发列车G7，其第三项作业与第一项作业过程开始和结束时刻分别为17：30—17：34和17：27—17：30，故无法占用敌对进路，优化后的G3折返进路V_{\mathrm{5}}\to V_{\mathrm{3}}与G7出段进路V_{\mathrm{10}}\to V_{\mathrm{6}}\to V_{\mathrm{18}}互为平行进路。

③折返列车与相反方向运行的其他列车第三项作业过程之间。如下行折返列车G3与上行停站通过列车G12，优化后的G3折返进路V_{\mathrm{5}}\to V_{\mathrm{3}}与G12发车进路V_{\mathrm{3}}互为敌对进路，然而其作业过程开始及结束时刻满足进路占用安全时间间隔，验证了所得进路分配方案的正确性。

6　结论

（1）鉴于列车进路分配方案对车站时空资源占用的双重依赖性，基于进路建模角度构建微观时空网络，将列车在站作业流程转化为列车对时空网络中节点及弧段的占用过程。相较于传统基于路径建模及基于区段建模角度而言，可在有效描述到发线与咽喉区进路连通性的基础上降低时空网络节点与弧段数量，从而降低时空网络模型复杂度。

（2）结合5类列车在站实际作业流程，引入4类设备占用关系矩阵，在考虑列车到发线占用固定方案的基础上保证其到发线选择与咽喉区进路排列的灵活性，从而有效降低可行解空间，提升算法收敛速度。

（3）采用不相容弧集合对设备占用不相容性约束进行描述，将设备占用冲突概括为5类不相容弧集合，有效降低了模型规模与复杂度。此外，基于拉格朗日松弛算法框架，提出以列车可选时空路径数量为核心的优先序列法，有效保证解的可行性。

（4）鉴于列车晚点及突发事件可能导致既有优化的列车进路分配方案不可行，因此列车时刻表与进路分配方案的协同优化问题将是进一步研究方向。

参考文献

[1] 贾文峥，毛保华，何天健，等. 大型客运站股道分配问题的模型与算法[J]. 铁道学报，2010，32(2)：8-13.

[2] JIA Wenzheng， MAO Baohua， Tinkin HO，et al. Model and Algorithm for Track Allocation at Large-Scale Railway Passenger Stations[J]. Journal of the China Railway Society，2010，32(2)：8-13.

[3] 单奕嘉，聂　磊，乐逸祥，等. 周期模式下高速铁路车站到发线运用优化模型研究[J]. 铁道学报，2022，44(8)：1-13.

[4] SHAN Yijia， NIE Lei， YUE Yixiang，et al. Optimization of Station Track Utilization for High Speed Railway under Periodic Timetable[J]. Journal of the China Railway Society，2022，44(8)：1-13.

[5] 姚宇峰. 编组站到发线运用计划优化的研究[J]. 铁道货运，2022，40(7)：51-58.

[6] YAO Yufeng. Optimization of Arrival and Departure Track Operation Plan of Marshalling Station[J]. Railway Freight Transport，2022，40(7)：51-58.

[7] RODRIGUEZ J. A Constraint Programming Model for Real-Time Train Scheduling at Junctions[J]. Transportation Research Part B：Methodological，2007，41(2)：231-245.

[8] 赵茜芮，张　琦. 基于同站台换乘的高铁车站作业计划优化编制[J]. 铁道科学与工程学报，2016，13(1)：20-27.

[9] ZHAO Qianrui， ZHANG Qi. Optimization of High Speed Railway Station Operation Plan Based on Across-Platform Transfer[J]. Journal of Railway Science and Engineering，2016，13(1)：20-27.

[10] 林　枫. 高速铁路车站列车进路分配计算方法研究[J]. 铁道运输与经济，2019，41(10)：46-51.

[11] LIN Feng. A Study on Train Route Allocation Scheme of High Speed Railway Terminal Station[J]. Railway Transport and Economy，2019，41(10)：46-51.

[12] 刘　杰，殷　勇，甘志良. 高速铁路车站咽喉区与到发线综合运用优化[J]. 交通运输系统工程与信息，2018，18(1)：193-199.

[13] LIU Jie， YIN Yong， GAN Zhiliang. Comprehensive Optimization for Utilization of Arrival-Departure Tracks and Throat Area in High Speed Railway Station[J]. Journal of Transportation Systems Engineering and Information Technology，2018，18(1)：193-199.

[14] 陈　彦，史　峰，秦　进，等. 旅客列车过站径路优化模型与算法[J]. 中国铁道科学，2010，31(2)：101-107.

[15] CHEN Yan， SHI Feng， QIN Jin，et al. Optimization Model and Algorithm for Routing Passenger Trains through a Railway Station[J]. China Railway Science，2010，31(2)：101-107.

[16] 高　全，张英贵，陈治亚，等. 考虑冗余时间的区域铁路车站股道运用计划协同编制优化方法[J]. 铁道科学与工程学报，2023，20(2)：506-515.

[17] GAO Quan， ZHANG Yinggui， CHEN Zhiya，et al. Track Utilization Plan Coordinative Optimal Method for Regional Railway Stations Based on Redundant Time[J]. Journal of Railway Science and Engineering，2023，20(2)：506-515.

[18] 赵　军，向江海，彭其渊. 铁路技术站进路调度问题优化研究[J]. 铁道学报，2020，42(7)：10-23.

[19] ZHAO Jun， XIANG Jianghai， PENG Qiyuan. Optimizing Route Scheduling Problem at Railway Technical Stations[J]. Journal of the China Railway Society，2020，42(7)：10-23.

[20] 彭其渊，宁　佳，鲁工圆. 大型高铁客运站到发线运用调整模型及算法[J]. 铁道学报，2019，41(1)：10-19.

[21] PENG Qiyuan， NING Jia， LU Gongyuan. Model and Algorithm for Train Platform Scheme Rescheduling at Large High Speed Railway Station[J]. Journal of the China Railway Society，2019，41(1)：10-19.

[22] ZHANG Q， LUSBY R M， SHANG P，et al. Simultaneously re-Optimizing Timetables and Platform Schedules under Planned Track Maintenance for a High Speed Railway Network[J]. Transportation Research Part C：Emerging Technologies，2020，121：102823.

[23] WANG E T， YANG L X， LI P H，et al. Joint Optimization of Train Scheduling and Routing in a Coupled Multi-Resolution Space-Time Railway Network[J]. Transportation Research Part C：Emerging Technologies，2023，147：103994.

[24] ZHOU W L， TENG H L. Simultaneous Passenger Train Routing and Timetabling Using an Efficient Train-Based Lagrangian Relaxation Decomposition[J]. Transportation Research Part B：Methodological，2016，94：409-439.

[25] MENG L Y， ZHOU X S. Simultaneous Train Rerouting and Rescheduling on an N-Track Network：A Model Reformulation with Network-Based Cumulative Flow Variables[J]. Transportation Research Part B：Methodological，2014，67：208-234.

[26] 白紫熙，周磊山，王　劲，等. 基于拉格朗日的高速铁路车站作业优化[J]. 交通运输系统工程与信息，2014，14(4)：120-125.

[27] BAI Zixi， ZHOU Leishan， WANG Jin，et al. A Lagrangian Relaxation Model for High Speed Railway Station Operation Optimization[J]. Journal of Transportation Systems Engineering and Information Technology，2014，14(4)：120-125.

[28] 马　驷，孙建康，鲁工圆. 高速铁路车站列车进路分配方案的优化与调整[J]. 中国铁道科学，2018，39(1)：122-130.

[29] MA Si， SUN Jiankang， LU Gongyuan. Optimization and Adjustment of Train Route Allocation Scheme for High Speed Railway Station[J]. China Railway Science，2018，39(1)：122-130.

[30] GAO R H， NIU H M. A Priority-Based ADMM Approach for Flexible Train Scheduling Problems[J]. Transportation Research Part C：Emerging Technologies，2021，123：102960.

[31] 党杨瑞. 基于道岔分组的高速铁路车站咽喉通过能力计算[J]. 铁道运输与经济，2024，46(4)：9-18.

[32] DANG Yangrui. Calculation of Throat Capacity of High Speed Railway Station Based on Turnout Grouping[J]. Railway Transport and Economy，2024，46(4)：9-18.

[33] 叶海昌. 通辽西站北京端咽喉区通过能力分析[J]. 铁道货运，2022，40(10)：12-20.

[34] YE Haichang. Analysis of Passing Capacity at Beijing End Throat of Tongliaoxi Railway Station[J]. Railway Freight Transport，2022，40(10)：12-20.

基金资助

甘肃省科技厅计划项目(22JR5RA379)

甘肃省教育厅项目(2023A-037)