基于时空状态网络的铁路中小型技术站进路不确定性规划研究

Route Planning of Small and Medium-Sized Technical Stations of Railways under Uncertainty Based on Spatio-Temporal State Network

摘要

针对调度集中系统在普速铁路车站难于进一步扩大应用的问题，分析普速铁路应用调度集中系统存在的难点，以车站进路规划为研究重点，着重研究调车作业不确定性问题。分析进路不确定规划问题特性，将该问题抽象为多阶段最小费用流问题，并建立车站时空状态网络，给出进路冲突问题在网络上的表达方法，借助时空资源这一概念对冲突进行检测和疏解。以最短路问题为基础，构建调车钩作业进路备选集；将车站作业总延误时间最小和单条进路开放次数最少2个目标相结合作为综合目标函数，构建车站进路不确定规划模型。综合2个模型给出基于列生成算法的模型求解算法。以B车站作为实例，验证了提出的车站进路不确定规划模型和算法的可行性和有效性，为车站进路自动规划问题提供参考。

Abstract

This paper aimed to address the challenge associated with the further expansion of the centralized traffic control (CTC) system at general speed railway stations. It analyzed the difficulties in applying CTC system in these stations. The station route planning was taken as the research focus, emphasizing the issue of uncertainty in shunting operations. The characteristics of uncertainty in route planning were analyzed, and the problem was simplified as a multi-stage minimum cost flow issue. A spatio-temporal state network of the station was established to represent route conflicts. By utilizing the concept of spatio-temporal resources, this paper detected and resolved route conflicts. Based on the shortest path problem, an alternative route set for shunting operations was constructed. Two objectives of minimizing overall station delay and the times of opening a single route were integrated into a comprehensive objective function. This function was then used to build a model for route planning under uncertainty. A column generation algorithm was developed to solve this model by combining two models. The feasibility and effectiveness of the proposed model and algorithm of route planning under uncertainty were verified using an example from station B, providing references for automatic route planning at stations.

Graphical abstract

关键词

车站进路规划 / 不确定规划 / 调车作业 / 时空状态网 / 列生成算法

Key words

Station Route Planning / Planning under Uncertainty / Shunting Operation / Spatio-Temporal State Network / Column Generation Algorithm

随着调度集中系统(CTC)的不断发展和国铁对于铁路自动化的进一步要求，CTC系统已于2019年实现了在我国高速铁路车站的全覆盖^[1]；但在普速铁路车站中，该系统还未实现普遍应用，车站作业的自动化水平需进一步提升，导致这一现状的原因是普速铁路车站中存在着大量调车作业，调车作业组织复杂、类型多样，具有开始时间和作业时长不确定性强的特点，因此调车作业自动化问题是普速车站进路自动规划推进中亟待解决的问题。研究将以CTC系统在普速铁路车站中的应用为背景，着眼于普速铁路中小型车站的作业进路规划问题，针对车站调车作业不确定性进行研究。通过车站时空状态网络对车站进路规划问题进行分析，进行车站内所有作业的不确定规划，以期实现普速铁路车站作业不确定规划的目标。

1　问题描述

车站进路规划即根据作业目的对车站进路进行选择，在避免各项作业冲突的前提下进行合理的进路触发。在车站进路规划的相关研究中，学者们通常应用车站网络模型对车站作业进行分析，并将进路规划划分为进路选择和进路排列2个部分，进行一体化研究^[2-4]。部分学者采用蚁群算法和遗传算法等元启发算法应用于一组已建立的车辆路径问题并进行优化求解^[5-7]。在车站调度优化问题研究中，有学者针对编组站调度优化问题进行了仿真模拟^[8]。部分研究探讨了作业进路自动触发的条件和冲突疏解问题^[9-11]。

与列车作业随着运行图进行确定性接发作业不同，调车作业具有作业类型多样、作业方式灵活、作业过程复杂等特点，并集中反映在调车作业触发时机、进路选择及作业时长的不确定性^[12]。因此，对于调车作业的不确定性研究是车站进路规划研究中的突破点和难点，也是分析的重点。

调车作业的不确定性除了体现在进路选择、触发时机及进路占用时长以外，进路之间的广义冲突和前后作业逻辑制约等方面也影响着调车作业。部分学者已经在车站自动化研究中加入了不确定条件下的作业分析和研究。王振宏等^[13]对调车作业时间的不确定性进行分析，建立调机运用的期望模型并设计了遗传算法和随机模拟相结合的混合算法进行求解。刘霆等^[14]基于机会约束刻画车站解编作业时长的随机波动性，建立了编组站阶段计划随机机会约束规划模型。景云等^[15]将编组站解编作业时间作为模糊变量，以阶段内车站发车量最大为目标，建立了不确定条件下的编组站动态配流模型。黎浩东^[16]在考虑列车解编作业时间不确定因素的基础上建立了随机相关机会规划模型。

当前学者通常采用随机规划模型并建立启发式算法的方法解决不确定问题。随机规划模型因其特性可以更好地对不确定性问题进行定义和描述，并在不确定的环境下通过极大化随机事件发生的概率从而给出问题的最优解^[17]。但是，当前对不确定性问题的研究大多聚焦于调度计划问题，关于动态的车站进路综合规划问题的研究还存在一定探索空间。因此，将在随机规划的基础上对包含调车作业的车站进路规划这一动态问题在时空维度上进行分析和研究。

2　面向车站进路规划的车站时空状态网络构建

2.1　面向车站进路规划的车站时空状态网络特性分析

由于铁路车站有其固有属性和列车运行规则，一般时空网络不能很好地对现实车站作业场景进行描述，需要依照车站实际作业情况改进一般网络使其能完整描述车站作业过程。由车站线路及设备形成的网络与一般网络的不同之处在于以下方面。

（1）列车运行方向分为上行方向和下行方向，一列车在进行作业时，其运行方向的反方向联锁设备皆对其封闭。同时，调车作业存在推送和牵引2种不同的行进方式，从不同方向进入线路进行摘车和挂车将产生与调车计划规定完全不同的结果，因此车站空间网络是一个有向网络。

（2）调车作业计划是由多个连续的钩计划构成的，因此调车作业计划可以分解成一个路径序列，在路径之间还存在连挂和摘解等工作，从而改变各个作业地点车列作业后的存车量，下一个钩作业将在上一个钩作业形成的车列存车量变化上进行。

（3）车站网络基于车站真实信息构建，即网络中的信息应符合车站作业的现实场景，例如作业进路不能穿越停留有车辆的线路等。

（4）车站中存在互相关联的进路，即若进路A被列车作业或调车作业占用时，与A进路相关联的线路和设备将被锁闭，不允许进行其他作业。因此，可以将这种相关联的线路和设备视为网络中的同一资源，当资源中的一部分被占用时，整个资源都被占用。

为使网络符合现实情况，本研究所建时空状态网络为包含时间信息和设备状态信息的多方向网络。

2.2　多方向时空状态网络构建

2.2.1　空间状态网络构建

建立车站空间网络时，可以将现实中的车站分界点和线路终端作为空间网络的节点，连接各节点的线路作为网络的弧。由于车站网络为多方向网络，节点需要从<空间设备，走行方向>2个维度进行描述，因此，车站任一节点应根据上、下行方向衍生出2个不同方向状态的节点，如此便可保证车列走行方向一致，符合现实情况。部分车站空间状态网络示意图如图1所示。

图1表示了现实车站抽象成的空间网络，车站空间网络中节点是对所有分界点和线路终端的抽象，即车站中的钢轨绝缘、车挡以及区间内的闭塞分区分界点都将被描述为节点，弧段则是连接相邻节点的线路的抽象。若一条可行的列车走行路径顺序经过了2个节点，那么这2个节点之间会形成一条沿列车运行方向的有向弧。

调车作业中经常需要进行折返操作，由于所创建的网络使用双层网络表示多方向，因此虚拟转向弧(图1中以虚线表达的边)用来表达车列折返换向操作。由于只有可以提供调车车列停留的线路才能进行折返作业，因此转向弧连接的2个节点为不同方向属性的可供车列停留和折返的节点。转向弧还应具有容车长度属性，表示实际车站线路能容纳车列停留或作业的长度，只有当转向弧容车长度大于车列长度时，车列才可在此线路进行折返。

车站内轨道区段的设备或设施可以抽象成为车站资源。车站作业会占用车站内设备设施，多个作业在同一时空内可能产生设备的争用，此时会产生冲突。将车站内互相关联的联锁设备看作同一车站资源，可以更好地分析车站作业间产生的冲突。车站资源划分示意图如图2所示。

车站作业具有时间属性，被作业占用的资源也应具备时间属性。因此，需要在空间属性的基础上将车站空间资源在离散时刻上扩展为时空资源。

2.2.2　时空状态网络的构建

为车站网络添加时间维度时，由于车站作业计划以固定时间间隔进行编制，可以以车站作业密度和设备能力利用率为依据选择合适的单位将时间离散化，在此基础上将车站网络扩展成为时空状态网络。车站时空网络示意图如图3所示。

车站空间网络为二维网络，车站时空网络添加了时间维度，给空间网络在二维坐标系上进行刻画的空间节点增加时间量，使每个空间节点以时间为坐标轴扩展出若干不同时刻的时空节点。空间网络的边表示空间节点之间的连接关系，时空网络的边表示2个时空节点位移过程消耗的时间单位。空间网络可以认为是时空网络在空间坐标系上的投影。

2.3　调车作业不确定性表达

2.3.1　时空冲突的刻画

作业之间的冲突是进行车站进路规划时应着重考虑的问题。使用锁闭时间这一概念对时空状态网络中的作业冲突进行描述。锁闭时间可以表达一列车对某时空资源进行占用时其他作业不能在该时间范围内侵入此时空资源的排他性，检测各条进路因作业产生的闭塞是否有时空上的重叠。

锁闭时间通过附加时间、接近走行时间、占用时间、出清时间、释放时间5部分，描述列车使用一条进路时进路中的轨道区段被占用情况。线路占用时段的表达方法示意图如图4所示。

图4中t_{\mathrm{0}}表示车站开始处理调车进路触发工作的时刻，t_{\mathrm{1}}表示调车进路开放的时刻，t_{\mathrm{2}}表示车列开始运行的时刻，t_{\mathrm{3}}为车列头部到达DG1区段钢轨绝缘的时刻，t_{\mathrm{4}}为车列越过DG1区段的出口钢轨绝缘的时刻，t_{\mathrm{5}}为车列全部出清DG1，DG1成功解锁的时刻。则称t_{\mathrm{0}}至t_{\mathrm{3}}为车列对区段的预占用阶段，t_{\mathrm{3}}至t_{\mathrm{4}}为对区段的占用阶段，t_{\mathrm{4}}至t_{\mathrm{5}}为清空区段阶段。

2.3.2　调车进路对资源占用的不确定性表达

由于调车进路开放时机和作业时长具有不确定性，因此无法确切地描述调车作业对线路的占用情况。为解决这种不确定性，研究的核心思想是将作业占用进路的锁闭时间进行概率化表述。线路占用时段及冲突的不确定性表达示意图如图5所示。

图5a中，有A和B两个不同概率的进路开放时机，其中有25％的可能性A开放，则在该时刻A进路开放确定的锁闭时段对区段锁闭的概率是0.25；有75％的可能性B进路开放，则该时刻B进路开放确定的锁闭时段对区段锁闭的概率是0.75。由此，不确定性问题可以通过锁闭时间概率化的表述转化为确定性问题。A和B的开放会导致产生图5b的冲突，冲突发生的概率可以确定性表达为0.75×0.25=0.187 5。在进行冲突疏解时，可设定一个冲突的容忍程度，只要冲突发生概率低于该冲突容忍度，就认为该时刻该线路有很大可能不会发生冲突。

因此，总结冲突检测方法的主要特征如下。

（1）建立包含空间位置和时间属性的车站时空资源，使用时空资源表示车站作业对设施设备的占用。

（2）车列对线路内区段的占用可划分为预占用、占用和清空3个阶段，在该阶段内与该区段对应的时空资源将被占用。

（3）若2项作业占用同一时空资源，则认为这2项作业存在时空冲突，需要进行疏解。

（4）由于进路的开放时机以及作业时长都具有不确定性，因此时空资源的占用也具有不确定性，可以将其概率化，进而因占用同一时空资源产生冲突也是概率性事件。

（5）为了判断冲突发生的概率，需要明确占用每一个时空资源的车列ID、作业种类、占用概率等信息。

2.3.3　调机与车列顺序的关系

车列作业时需要由调机带动走行。由于调机以不同方式带动车列运动时的平均速度不同，为解决现实车站作业问题，还应考虑调机和车列的顺序关系，即调车作业是以推送作业的方式还是以牵引作业的方式进入目标线路。由前文分析可知，能够提供车列停留的地点均可提供车列转向，因此这些地点在网络中存在转向弧，车列只要从正确的转向弧所关联的节点进入进路即可保证正确的调车方向。问题随之转化为判断目标路径需要经过的节点与转向弧所关联的节点是否一致，并且把错误方向的转向弧所关联的节点设置为不能使用。总结得到调机和车列位置关系如下：根据对车站作业的分析可知，当车列经过折返弧时，调机与车列的前后顺序不会发生变化，但调机的作业方式会发生改变；当车列经过奇数次环线时，调机与车列的顺序会发生变化，但作业方式不发生改变。

2.3.4　调车作业不确定性在时空状态网络中的表达

为了使调车进路在时空状态网中的表达更精确，采用G=\left(E,V\right)来表达时空状态网络，其中V表示网络节点，节点属性包含<编号，类型，附属信号设备，时刻，走行方式>5个部分；E表示网络中的边，表示时长信息。定义\left(v_{\mathrm{1}},v_{\mathrm{2}}\right)\in E为网络中某一边，则该式表示自时刻t_{\mathrm{1}}到t_{\mathrm{2}}这段时间内，作业车列在空间上从节点v_{\mathrm{1}}运行至v_{\mathrm{2}}。

将车站作业持续消耗时间的概率分布离散化，可以得出作业在该时间范围内完成的概率，进而可以得到基于概率分布的作业完成时间时空状态网络示意图如图6所示。此时，由网络的一个节点指向另一个节点的边表示的含义为在该段时间内作业可以按时完成的概率。

2.4　基于多阶段最小费用流问题的车站进路不确定规划建模思路

调车作业的实质是将一列有长度的车列从一个有容车长度限制的地点移动到另一地点并进行车列长度的增减，这些特性与运输问题相吻合，因此所研究的问题可以采用最小费用流模型进行描述。一个调车作业包含多个连贯的调车钩作业，若将一个调车钩作业视作一个阶段性过程，则整个调车作业就可以看作一个多阶段问题，进路规划问题就可以被抽象成为多阶段最小费用流问题。以多阶段最小费用流为基础，进行车列摘挂钩的地点可以被抽象成为每一阶段的起点或终点，进路规划问题就是寻找各阶段起终点之间的最小费用路径，并选择合适时机开放进路。因此，该问题可以通过建立车站网络并对每一钩作业生成合适的走行进路，最终生成全部钩作业的进路序列来解决。由于车站内同时存在多个各种类型的作业，作业进路间可能产生时空上的交叉重叠，即进路间的冲突，需要在以空间网络为基础的最小费用流网络上加入时间维度。前文对调车作业的不确定性进行了阐述，为解决包含调车作业的进路规划问题，需要采用不确定规划。由以上分析可以总结得出，本研究在时空状态网络的基础上构建基于多阶段最小费用流的不确定规划模型以解决车站进路规划问题。

由于直接进行时空状态网络的建模和计算较为复杂，为更好地解决上述问题，将分两步进行问题的研究。首先在不考虑时间维度的情况下于车站空间状态网络上对每一个已知起始点的钩作业进行K短路搜索，对于每一作业进路给出可能发生的空间走行路径，将走行距离作为费用变量，使K短路问题转化为寻找K条最小走行距离进路的问题，使用最小费用流模型对该问题进行描述。第二步综合站内各项作业，对作业间的冲突进行检测，以作业总延误时间最少为目标，选择发生冲突概率最小、执行可能性最大的进路，对作业进路的选择和触发时机进行综合性规划。这一步中冲突最小化约束涉及到站内多项同时进行的作业，是车站进路不确定规划问题的重点和难点，研究将采用上文提到的不确定性在时空状态网络中的表达方法对问题进行描述，进行站内冲突的疏解。总之，分两步进行研究即在空间状态网络给出的进路备选集基础上，添加时间维度，综合车站各项作业，以最小作业延误时间为最终目标从进路备选集中选出最合适的走行路径。

3　车站进路不确定规划模型的构建及求解算法

3.1　调车进路备选集模型

该模型的含义是以一个调车作业的任一调车钩作业为对象，为其提供K条走行距离最短的进路备选集。因此模型应以进路的广义费用Z最小为目标，目标函数如式⑴所示。

Z=\mathrm{m}\mathrm{i}\mathrm{n}\sum _{h\in H}\sum _{ij\in A}{c}_{ij}{x}_{ij}^h⑴

式中：H为调车作业计划，h\in H为每一调车钩作业；c_ij 为边\left(i,j\right)的使用费用，可为长度或走行时间，此处，使用广义长度，即表示线路的边使用实际的长度，而表示方向转换的边则使用转换方向消耗的时间对应的一定调车速度下走行的距离；x_{ij}^h表示第h钩调车车列走行路径是否经过边\left(i,j\right)的0-1整数变量，0表示不经过，1表示经过；A为车站空间状态网络的边集合，\left(i,j\right)\in A为车站空间状态网络的边。

调车进路备选集基于空间网络构建，因此约束中需要包含对网络的流平衡进行约束，保证除起始点外任一节点进入边和发出边数量相等。网络流平衡约束表示为式⑵、式⑶、式⑷。

\sum _{ij\in A}{x}_{ij}^h-\sum _{ij\in A}{x}_{ji}^h=\mathrm{1}\hspace{1em}\hspace{1em}\forall h,ij\in O^h⑵

\sum _{ij\in A}{x}_{ij}^h-\sum _{ij\in A}{x}_{ji}^h=-\mathrm{1}\hspace{1em}\hspace{1em}\forall h,ij\in S^h⑶

\sum _{ij\in A}{x}_{ij}^h-\sum _{ij\in A}{x}_{ji}^h=\mathrm{0}\hspace{1em}\hspace{1em}\forall h,ij\notin S^h\bigcup O^h⑷

式中：O^h表示第h钩的起点边集合；S^h表示第h钩的终点边集合。

根据2.3.3对调机和车列顺序的分析，可以得出调车作业经过折返弧次数与作业方式变化的关系。这一关系可以用约束来表示，如式⑸所示。

D_h^o+z^h=D_h^s\hspace{1em}\hspace{1em}\forall h⑸

式中：D_h^o表示第h钩的车列在初始位置时调机和车列的位置关系，0表示调机在车列的下行方向侧，1表示调机在车列的上行方向侧；D_h^s表示第h钩的车列在目标位置时调机和车列的位置关系，0表示调机在车列的下行方向侧，1表示调机在车列的上行方向侧；z^h表示第h钩车列使用折返线的次数，奇数次时为1，偶数次时为0。

结合前文对转向弧应包含属性的分析，约束中还应包含转向弧容车长度和进行折返或停留的车列长度的关系约束，其表达如式⑹所示。

y_k^h{L}^h\le L^k\hspace{1em}\hspace{1em}\forall h,k⑹

式中：y_k^h表示第h钩车列是否使用转向弧k的0-1变量，0表示不使用，1表示使用；L^h表示第h钩的车列长度，包含调机的长度；L^k表示转向弧k的容车长度。

3.2　基于时空状态网络的车站进路不确定规划模型

该模型是车站进路总体规划模型，目标函数的构建应以车站作业总体要求为指引。车站排列进路时首先要保证安全生产的同时能够按图行车，避免产生计划之外的等待现象，特别是列车晚点情况的发生。因此，采用列车作业与计划偏离程度小、调车作业比规定结束时间晚点少为模型的综合目标。目标I₁可表示为式⑺。

I_{\mathrm{1}}=\mathrm{m}\mathrm{i}\mathrm{n}(\sum _{f\in F^{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{n}}}{\omega }_f\sum _k\left|{\lambda }_k^f{e}_k^f-{\overline{e}}^f\right|+\sum _{f\in F^{\mathrm{s}\mathrm{h}\mathrm{u}\mathrm{n}\mathrm{t}}}{\omega }_f\sum _k{\lambda }_k^f{e}_k^f-{\overline{e}}^f)⑺

式中：F^{\mathrm{t}\mathrm{r}\mathrm{a}\mathrm{i}\mathrm{n}},F^{\mathrm{s}\mathrm{h}\mathrm{u}\mathrm{n}\mathrm{t}}\subset F分别为列车作业对象集合和调车作业对象集合，一个调车作业对象对应一个调车作业计划单；{\omega }_f为作业对象f的权重，以作业对象的作业紧迫性、作业内容、作业类型为目标综合考虑各作业对象的权重，其中，列车的权重等级高于调车车列；{\lambda }_k^f表示作业对象f的第k条备选路径作为最终要开放的进路的0-1变量，0表示未选中该段路径，1表示选中；e_k^f和{\overline{e}}^f分别表示作业对象f的第k条路径结束的时刻和计划规定的结束作业最晚时刻。

一条长调车进路由若干短调车进路构成，车站可以选择开放短进路的方式。若同时开放所有短进路，可能干扰其他作业进行，导致其余作业的延时；若一次开放的进路过短，会使重复性作业增多，加大车站工作人员劳动强度，启停车次数过多影响工作效率。因此，合理的进路开放次数也对调车作业效率有较大影响。将进路开放次数这一影响因素转化成目标函数I₂如式⑻所示。

I_{\mathrm{2}}=\mathrm{m}\mathrm{i}\mathrm{n}(\sum _{f\in F^{\mathrm{s}\mathrm{h}\mathrm{u}\mathrm{n}\mathrm{t}}}\sum _k\sum _l{\lambda }_k^{f}Q(p_{k,l}^f))⑻

式中：p_k^f\subset P^f表示作业对象f的第k条备选时空路径，一条时空路径对应一个调车作业计划单中的进路序列，是一系列相互衔接的边的集合；p^f为f的所有可能的路径集合，即备选路径集；p_{k,l}^f\subset p_k^f表示p_k^f中的第l段的路径，该段路径为相邻2个作业地点之间的走行路径；Q(p_{k,l}^f)为p_{k,l}^f中进路开放的阶段数量，即在整个走行过程中，进路是分几次开放的。

式⑻的意义是寻找进路开放的最小次数，但如果同时开放的进路过长，可能导致影响其他作业的效率，使I_{\mathrm{1}}值劣化，因此需要综合I_{\mathrm{1}}和I_{\mathrm{2}}对目标函数进行阐述。综合上述分析，得到解决该不确定性规划的模型——车站进路组织问题模型(Model for Station Routing Operation Problem，MSROP)，如式⑼、式⑽、式⑾所示。

I={\alpha }_{\mathrm{1}}{I}_{\mathrm{1}}+{\alpha }_{\mathrm{2}}{I}_{\mathrm{2}}⑼

\sum _k{\lambda }_k^f=\mathrm{1}\hspace{1em}\hspace{1em}\forall f⑽

\sum _k{\lambda }_k^f+\sum _{f\mathrm{\text{'}}\in F_r\wedge f\mathrm{\text{'}}\ne f}\sum _{k\mathrm{\text{'}}}{\lambda }_{k\mathrm{\text{'}}}^{f\mathrm{\text{'}}}{\phi }_r^{ff\mathrm{\text{'}}}\le \mathrm{1}+{\mathrm{\Omega }}^r\hspace{1em}\hspace{1em}\forall r,\forall f\in F_r⑾

式中：r\subset R代表车站的时空资源；{\varphi }_r^{f{f}^{\mathrm{\text{'}}}}表示车列作业f和f^{\text{'}}占用时空资源的可能性；{\mathrm{\Omega }}^r表示资源r的冲突的容忍度，为0~1间的实数；{\alpha }_{\mathrm{1}}和{\alpha }_{\mathrm{2}}表示2个影响因素的影响因子，可以经过多次实验选取最优值。

式⑽的含义是在进路备选集里为每个作业对象f选择一条备选路径。式⑾表示作业对象f经过的所有时空资源发生冲突的概率小于设定的冲突容忍度。由于该模型需要在备选集的基础上进行路径的选择和优化，因此还需要为每个作业对象在车站网络上寻找进路备选集。进路备选集模型 (Model for Path Generation，MPG)为建立的进路备选集模型，如式⑿、式⒀所示。

\underset{f}{\mathrm{m}\mathrm{i}\mathrm{n}}\sum _{a\in A}(c_a+{\pi }_{r(a)}^f)x_a^f⑿

\sum _{a\in A}{x}_a^f-\sum _{a\in A}{x}_a^f=i_n^f\hspace{1em}\hspace{1em}\forall n\in N,\forall f\in F⒀

MPG模型基于3.1节的备选集模型构建，保证从作业对象f的起点位置至终点位置搜索形成时空状态网络上的连续路径。其目标函数分为2个部分，一部分为f使用边a\subset A的固定费用c_a，与作业时间长短有关；另一部分表示边所关联的资源r的价格{\pi }_{r\left(a\right)}^f，其数值来源于MSROP中式⑾的影子价格。

3.3　车站进路不确定规划模型求解算法

列生成算法适用于约束条件的数目有限，但是变量的数目会随着问题规模的增长而产生爆炸式的增长的模型，其求解思想是将原线性规划问题分解为限制性线性主问题(RMP)和价格子问题(PP)，构建目标函数为线性主问题模型检验数的价格子问题模型，以判断原问题是否达到最优解。PP需要根据RMP的对偶变量，通过主问题的对偶问题求解最优解，即约束的影子价格，生成检验数为负的可以加入时空进路备选集的进路，向RMP中添加满足最小化问题中检验数<0的新列，对变量和系数矩阵进行更新，并重新求解RMP模型。2个问题从逻辑上连接，进行数据的交互，逐渐生成限制性线性主问题的最优解，即原线性规划问题的最优解。本研究模型涉及到的时空路径较多，有2个相互影响的模型，与列生成算法的特性相吻合。因此，选择列生成算法并以MGP作为MSROP的价格子问题进行求解。算法具体步骤如下。

步骤1：输入数据。包含车站时空状态网络节点信息、弧信息，车站设备资源信息和车站作业信息。

步骤2：初始化信息。初始化时空状态网络信息、时空资源信息、作业对象信息等，令初始进路备选集\omega =\mathrm{0}。

步骤3：为每个作业对象f在时空状态网络上生成一条备选路径以成为备选路径集的初始元素，得出每个作业对象f的进路备选集\omega，以启发列生成算法。

步骤4：调用列生成算法对模型进行计算，得到MSROP模型的求解结果，得到价格子问题的影子价格{\pi }_{r(a)}^f。

步骤5：根据影子价格使用标号法为每个作业对象f求解MPG，计算得到子问题目标函数，若目标函数>0，则MPG为f生成一条新路径，转到步骤6，否则转到步骤7。

步骤6：在当前进路备选集上计算得到MSROP的最优解，若得到整数解，则转到步骤8，否则转到步骤7。

步骤7：调用启发式算法以资源的影子价格为作业对象f的权重，结合时间顺序依次获得作业对象可行路径。

步骤8：将当前最优整数解转化为车站进路规划方案输出，算法结束。

综上所述，基于列生成的进路规划模型求解框架如图7所示。

4　算例验证

算例以普速铁路某车站B站作为研究对象。B站为区段站，连接4个方向，站内共有16条股道，其中正线2条。为便于后续车站网络和进路规划模型的构建，忽略了车站中与研究内容无关的固定设备，构建了车站网络结构示意图，并对图中关键节点进行了重新标号。

B站拓扑结构图如图8所示。

算例采用B站某日7：00—8：00阶段计划中的部分车站作业数据进行分析。调车作业计划1如表1所示，调车作业计划2如表2所示，调车作业计划3如表3所示。除调车作业外，车站在该时段还存在2个通过作业A1和A2，其通过时间分别是7：24：00和7：43：00。研究设置从列车到达前2 min车站的进路开始锁闭；列车尾部出清轨道区段后车站需要5 s进行轨道空闲的确认，随后轨道区段显示空闲。

研究基于C#编程语言设计了实现基于车站时空状态网络的车站进路不确定规划模型的列生成算法。进路规划方案如表4所示。

研究最晚触发进路与实际作业结果相比提前了约8 min，证明了研究的适用性。

研究中模型的目标函数选取的是车站作业总延误时间。若选取以往研究普遍采用的作业总时长代替延误时间作为目标函数，不同目标函数的规划方案对比如表5所示，在此2个模型中，影响因子等变量均保持不变。

5　结束语

研究提取车站作业不确定性这一重点要素，在车站时空状态网上对调车作业进行解析，基于多阶段最小费用流问题构建了车站进路不确定规划模型。针对模型特点，设计了基于列生成的启发式求解算法对模型进行求解。算例结果表明，设计的模型和算法可以应用于中小型车站进路规划问题中，通过对车站时空状态网络的构建，可以更准确地刻画车站作业冲突，给出车站作业不确定性问题的确定性表达。添加进路开放次数取代过往研究中常用的使用列车总走行时间最小或总走行距离最短作为目标函数的研究方法，更符合现实作业情况。研究中的车站作业时间和作业优先级顺序是通过车站作业历史数据和国铁作业要求进行归纳得到的，同时研究只考虑了车站作业对于进路的选择影响，对于区间车辆运行故障、维修天窗等因素没有较深入地研究，因此还需进一步加强数据的普遍适用性。

参考文献

[1] 刘　俊. 普速铁路调度集中控制系统运用优化对策探讨[J]. 铁道运输与经济，2019，41(8)：1-5.

[2] LIU Jun. A Tentative Study on the Optimizing Countermeasures for the Application of Centralized Traffic Control System of Conventional Railway[J]. Railway Transport and Economy，2019，41(8)：1-5.

[3] 陈　彦. 铁路客运站列车过站径路与调机运用优化[D]. 长沙：中南大学，2010.

[4] 贾文峥. 大型铁路客运站的进路分配问题及缓冲时间研究[D]. 北京：北京交通大学，2010.

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

[6] JIA Wenzheng， MAO Baohua， HE Tianjian，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.

[7] BELL J E， MCMULLEN P R. Ant Colony Optimization Techniques for the Vehicle Routing Problem[J]. Advanced Engineering Informatics，2004，18(1)：41-48.

[8] RAY S S， BANDYOPADHYAY S， PAL S K. Genetic Operators for Combinatorial Optimization in TSP and Microarray Gene Ordering[J]. Applied Intelligence，2007，26(3)：183-195.

[9] DE LUCA CARDILLO D， MIONE N. K L-List λ Colouring of Graphs[J]. European Journal of Operational Research，1998，106(1)：160-164.

[10] 李 斌.企业铁路编组站的调度优化问题研究[D].兰州：兰州交通大学，2014.

[11] 王大鲁. 济西站CIPS设计中调车进路问题分析与思考[J]. 中小企业管理与科技(中旬刊)，2016(2)：243.

[12] 方力一，梁　亮，袁志明，等. 分散自律调度集中系统车站调车作业的研究[J]. 铁道通信信号，2013，49(S1)：27-30.

[13] 刘　涛. CTC条件下中间站列调车作业控制的优化方案[J]. 铁路通信信号工程技术，2012，9(5)：3-5.

[14] LIU Tao. Optimization Scheme of Train and Shunting Operation at Intermediate Station under CTC Control[J]. Railway Signalling & Communication Engineering，2012，9(5)：3-5.

[15] 赵如月，苗建瑞. 面向管控一体化的普速铁路CTC系统功能定位探讨[J]. 铁道运输与经济，2022，44(5)：131-137.

[16] ZHAO Ruyue， MIAO Jianrui. Discussion on Function Orientation of CTC System for Scheduling-Controlling Integration of Conventional Railway[J]. Railway Transport and Economy，2022，44(5)：131-137.

[17] 王振宏，崔炳谋，许广辉. 基于不确定理论和混合智能算法的调车机车运用研究[J]. 铁道运输与经济，2006，28(12)：87-89.

[18] WANG Zhenhong， CUI Bingmou， XU Guanghui. Study on Shunting Locomotive Operation Based on Uncertainty Theory and Hybrid Intelligent Algorithms[J]. Railway Transport and Economy，2006，28(12)：87-89.

[19] 刘　霆，何世伟，王保华，等. 编组站调度计划随机机会约束规划模型及算法研究[J]. 铁道学报，2007，29(4)：12-17.

[20] LIU Ting， HE Shiwei， WANG Baohua，et al. Stochastic Chance Constrained Programming Model and Solution of Marshalling Station Dispatching Plan[J]. Journal of the China Railway Society，2007，29(4)：12-17.

[21] 景　云，王慈光. 不确定条件下编组站动态配流模型及算法研究[J]. 铁道学报，2010，32(4)：8-12.

[22] JING Yun， WANG Ciguang. Model and Algorithm of Dynamic Wagon-Flow Allocating in a Marshalling Yard under Uncertaint Conditions[J]. Journal of the China Railway Society，2010，32(4)：8-12.

[23] 黎浩东. 铁路编组站鲁棒阶段计划编制及调整研究[D]. 北京：北京交通大学，2012.

[24] 刘宝碇.不确定规划及应用[M].北京：清华大学出版社，2006.

基金资助

北京市科技新星计划项目(Z211100002121098)

北京市自然科学基金-丰台轨道交通前沿研究联合基金项目(L221006)