大型铁路客运站列车进路优化模型与算法研究

武晋飞，王炜炜

(中国铁道科学研究院 电子计算技术研究所，北京 100081)

大型铁路客运站列车进路优化模型与算法研究

武晋飞，王炜炜

(中国铁道科学研究院 电子计算技术研究所，北京 100081)

以提高车站行车技术作业效率，保证车站行车作业安全，尽可能减少旅客站内走行距离和时间，保证发车时间相近的两列始发或通过列车尽量不停靠同一站台，提高车站既有行车设备利用率为优化目标，建立大型铁路客运站进路优化的多目标规划模型。运用层次分析法求出各子目标的权重，并构建启发式算法进行模型求解。通过对算法进行实例验证，得到了较优的列车进路安排方案。

客运站；进路选择；多目标规划；启发式算法

我国铁路客运站正处于大规模的建设阶段。大型客运站要求衔接干线铁路、城际铁路、高速铁路等线路以及机车车辆检修基地来满足作业需求，加之车站结构复杂，作业繁多，必然导致列车进路交叉干扰增多。因此，对大型铁路客运站车站接发车作业的进路分配问题进行研究，并建立接发车进路优化问题和相应算法，最终获得高质量接发车方案，对铁路客运站旅客运输至关重要。

当前，国内外不少学者对车站进路安排问题进行了深入研究，文献[1]提出了咽喉区最大平行进路方法和最大概率进路紧侧方法。文献[2]通过详细分析客运站技术作业，将到发线运用目标分为3个子目标，分别建立优化模型并用分枝定界法进行求解。文献[3]用二次0—1规划法进行求解列车进路安排。文献[4]用k-顶点图着色法进行求解。文献[5]用固定工件排序法进行求解。研究发现，上述研究在列车进路安排问题中，大多数仅局限于某项作业单独优化，使得结果的优化、实用性并未达到极致，在建立模型时存在模型实用性和合理性问题，在模型求解时存在算法的有效性问题。

1 模型建立

1.1 问题描述

在车站作业中，列车（或车列）在使用到发线时，需要满足一定的原则：对于车站的某一条到发线，它可以对一定方向一定种类的列车（或车列）进行接发车作业；而对于一列旅客列车（或车列）来说，它只能被一定类型的到发线中的一条接发，该原则成为唯一性原则[2]；此外，列车（或车列）使用到发线还须满足到发线运用的其他约束条件，如满足最小安全时间间隔等[2]。

1.2 变量及约束条件

记到发线集为W ，到发线个数为d，根据车站行车技术作业性质要求以及列车运行方向要求以及偏好和其他方面作业等要求，将车站到发线分为l类，对应的到发线集W分为不同的集合Wl，对于每一类到发线集合Wl，对应的股道数目为Dt(t=1, 2, …, l)，计到发列车集为H，列车总数为n，将到发列车按上述要求分为相应的l类，即将到发列车集H分为不同的集合Ht，则每一类的列车数为Nk(k=1, 2, …, l)，上述映射关系可以形式化地表示为：φ∶H→W，且有。根据车站作业安全及规定，车站接发列车应满足以下约束：

（1） 根据列车的去向、上下行和个人偏好等情况，将列车i分到对应的到发线集合Wi中进行接发。

当xij=1时，i列车由j股道接发，否则，xij=0，表示i列车不是由j股道接发。

（3）在一定的时间区间内，一条到发线只能有一列车占用，记列车i占用到发线j的时间为，在该时间内股道j不能被其他的占用，表示第k类列车中第i列是否由第t类到发线中的第j条接发，其取值为0、1变量，tj表示股道j被占用的时间；为列车i出发时刻起至该线路全部腾空且可以接入下一列车的时刻；为列车i预备进路到j股道的时刻。

（4） 进路的冲突有2种形式：a. 时间上的冲突；b. 空间上的冲突。在为两列旅客列车安排到发线时，应该避免产生交叉的两个条件同时出现，即：为旅客列车i安排到j到发线时，与旅客列车k安排在l到发线时，是否产生道岔组交叉的0、1决策变量；为旅客列车i安排到j到发线时，与旅客列车k安排在l到发线时，是否产生时间交叉的0、1决策变量；xij、xkl均为0、1变量。

（5）同一到发线连续接车应满足时间间隔要求，假定相继停在股道j的3列车依次为：i_1、i、i+1，则它们在车站的时间间隔约束应满足：站作业最小间隔时间。

1.3 建立目标函数

本文选定以下4个优化目标，建立多目标规划问题对大型客运站列车进路安排进行优化。考虑到影响进路安排的各个目标重要程度并不相同，本文针对每个目标分别建立模型，每个模型描述一个问题，引进权值Wi，且然后通过层次分析法确定其权值大小，从而确定最终目标函数。

（1）有利于提高车站行车技术作业效率，保证车站行车作业安全。

引进权值αkitj，对其取值做如下约定：若第 k类列车中第i列由第t类到发线中的第j条接发并且符合运用方案，则αkitj=0；若第k类列车中第i列由第t类到发线中的第j条接发但不符合运用方案，则αkitj=1；若第 k类列车中第i列不由第t类到发线中的第j条接发，则αkitj=M，其中i∈(1,2,…,Nk)，j∈ (1,2,…,Dt)，M 为一个任意大的数。用xkitj表示第k类列车中第i列是否由第t类到发线中的第j条接发，其取值为0、1变量，若是，则 xkitj=1，否则xkitj=0。该优化目标表示为：

（2） 尽可能地方便旅客乘降。

引进一个惩罚值βij用以表示用第j条到发线接发第i列车时在不方便旅客乘降方面的惩罚值，βij值越大则说明该到发线接发该列车越不方便，βij可表示为：

其中，i=1,2,…,n ；j=1,2,…,d。 Ai表示在研究时段内车站接发的n列旅客列车中，第i列列车在该站到发旅客的平均数；Sj表示第j条到发线在接发列车时，旅客在车站内的平均走行路程。引进一个权值wij用以表示由第j条到发线接发第i列列车时的权值，若由第j条到发线接发第 i列列车且符合到发线分类使用方案，则该权值为0，即wij=0；若由第j条到发线接发第i列列车但不符合到发线分类使用方案，则该权值为1，即wij=1；若不由第j条到发线接发第i 列列车，则该权值为一个任意大的数M，即wij=M。可将方便旅客乘降问题转换为一个指派问题，表示如下：

（3）发车时间相近的两列始发（或通过）列车尽量不停靠在同一站台。

假定存在两列先后出发的列车i,I在同一站台出发，如果i列车运用到发线j的结束时间比u列车占用到发线v的开始时间晚，但不足20 min，且j、v两条到发线为同一站台，则列车 i、u就形成了一个相交时间区，即其占用到发线的时区存在时间交叉。引进权值γijuv，若i列车运用到发线j的结束时间比u列车占用到发线v的开始时间晚，但不足20 min，则γijuv=M，其中 M为一个任意大的数；若i列车运用到发线j的结束时间比u列车占用到发线v的开始时间晚，但超过20 min，则γijuv=0。引进权值δijuv，若i=j，u=v即两列车为同一列车或占用同一到发线，则δijuv=0 ,否则，δijuv=1，其中，i、u∈ (1,2,…,Nk)，j、v ∈ (1,2,…,Dt)。得到本文模型 3，表示为：

（4） 提高车站既有行车设备利用率，实现到发线均衡使用。

列车占用到发线时间可表示为tij=tSi+tLi+tEi。其中，tij为第i列旅客列车从接发到到发线j的总时间；tLi为第i列旅客列车占用到发线的时间；tSi为第i列旅客列车的出发作业时间；tEi为第i列旅客列车的到达作业时间。则各股道被占用时间均匀的目标函数，即本文目标函数4，可表示为：

假设Sij表示第j股道分配给两个相邻列车中间的空闲时间，即表示前一列车的离开时间与后一列车到达时间的差。设股道空闲时间均匀的目标函数即本文目标函数5，可表示为：

综上，本文建立的大型铁路客运站列车进路优化模型为：

目标函数中的wi代表5个子目标所占用的比重，本文采取了层次分析法确定， ∑ wi= 1。

运用层次分析法求得模型到指标权重为：

2 算例分析

某大型客运站为全路44个较大客运站中的一个以客运为主、客货运兼营的综合性一等车站，每日有开往北京、上海等各站的始发旅客列车39列，到达39列，通过列车12列共90列。其中，特快列车7对，均为直通特快车，快速列车为2对，均为直通快速旅客列车，普通旅客列车34对。跨3个铁路局及其以上为3对，跨2个铁路局9对，管内5对，普通旅客慢车直通1对，管内8对。该客运站站内共有4个站台，设有上下行正线，旅客列车到发线7条、货物列车到发线、机车走行线。日均办理旅客乘降4万余人，办理行包1万余件，年发送旅客约470万人。车站平面简图如图1所示。

图1 某客运站平面布置简图

2.1 数据预处理

2.1.1 对到发线的线束进行划分

将上行旅客列车尽量安排在1，3，4到发线，下行旅客列车安排在6，7，8，9道，可以很好地减少站场咽喉区交叉干扰，提高到发线运用能力。

2.1.2 划分到发线等级

根据到发线距离站房的远近，所临靠站台的等级，可对到发线进行划分。得到车站线路信息表如表1所示。

表1 算例客运站线路信息表

2.1.3 划分列车等级

根据列车的种类（特快、快速、普通等）等对列车进行分类。比如特快列车以及进京、沪、广列车定为1级，一般快速列车定为2级，普通旅客快车定为3级，普通旅客慢车定为4级。根据划分原则将算例车站的列车做如下划分：N201～N276为1级，K237～K374为2级，1485～1578为3级，其它列车定为4级。

2.1.4 确定列车-到发线权值矩阵cij

对于任意的列车i，都有i∈Hl, Hl=(H1, H2,…,Hl)；同理，对于到发线j，有j∈Wl, Wl=(W1, W2,…, Wl) 。权值矩阵cij表示列车接入线路的等级权值。根据算例客运站情况，做出其对应的列车-到发线权值矩阵，如表2、表3所示。

表2 列车-到发线权值矩阵（上行）

表3 列车-到发线权值矩阵（下行）

2.1.5 确定列车占用到发线时区

j列车占用到发线时间与列车的到发时间、列车类型等有关。列车占用时间包括车底接入时间、列车停站时间和列车出站时间，具体时间标准在站细中有明确规定。对于算例中客运站，始发列车占用时间总计为48 min，其中停站时间40 min，车底转入时间为2 min，列车出站时间为3 min。如果该始发列车的出发时刻为19：28，则它占用到发线的（[]）为（18：39，19：31）。终 到旅客列车占用时间为41 min，其中列车进站时间为6 min，车底转出时间为3 min，停站时间为31 min，如果终到列车的到达时刻为19：28，则它占用到发线的（[]）为（19：22，20： 03）。通过列车（）可以根据列车出站和进站时间得出。

2.2 列车进路优化方案计算

本文用C#语言编制了WinForm程序进行模型求解，其中，进路优化方案求解界面如图2所示。

图2 列车进路分配方案求解

在本文模型及参数设定下，程序运行282.850 s，即4.7 min，考虑计算数据量即处理流程，与预期结果基本吻合。将得到的到发线运用方案整理，如表4所示。

表4 列车到发线安排顺序

表4数据表明：上行旅客列车大多安排在上行场1、3、4道，下行旅客列车大多安排在下行场6、7、8、9道，以尽量减少咽喉区的进路交叉。N、K字头的始发或终到旅客列车（列车等级高，上、下旅客多，行包量大）大多安排在1道或离基本站台近的股道，说明子目标函数2、3在起作用；7条到发线的占用时间基本上均等，说明是子函数4和5在起作用。例如，2023次列车和4527次列车为在一个时区的始发列车，分别安排到了7道和9道，2023次列车旅客在3站台上车，4527次列车旅客在4站台上车。这样就避免了一个站台旅客人数较多的情况。说明子函数3在起作用。

2.3 方案评价

表5 某站近期到发线固定使用方案

表5为算例客运站近期实际站调编制的到发线运用计划。其进入上行场的下行列车相对较多，即进路横切正线情况较多。而一些行包量较大的列车没有接发在靠近基本站台的1道。例如，7163次列车和6041次列车属于同一时区的始发列车却分别安排到了9道和8道，那么必然会有4站台同时有较多的旅客上车，有可能会造成客运站工作组织的混乱。而在本文模型求解的方案表中（表4），子目标函数2很好地发挥了作用，将7163次列车和6041次列车分别安排在了7道和8道，使两列车的旅客分别从3站台和4站台上车，这样有利于有序的组织旅客按时上车，避免一些旅客上错车的现象，同时也避免了同一站台旅客人数多、压力大的情况。表4和表5比较说明，算法生成的到发线运用计划优化效果明显。

3 结束语

大型铁路客运站列车进路安排是一个繁琐而复杂的过程。论文综合考虑保证列车的进出站作业完成、发车时间相近的两列始发（或通过）列车尽量不停靠在同一站台、线路使用均衡和减少旅客站内的走行距离4个优化目标，建立了基于多目标非线性整数规划的高速铁路到发线运用模型，并以某大型铁路客运站为实际背景，采用C#对算法进行了实现，得到了到发线运用方案。结果表明，所建模型很好地体现了到发线运用的各种要求，得到了比较均衡的、方便旅客乘降的到发线运用方案，与传统的手工经验计算编制方法相比更优化、更高效，为优化列车进路，实现自动编制到发线运用计划提供了技术手段。

[1] 史 峰，谢楚农，于桂芳. 铁路车站咽喉区进路排列优化方法[J] ．铁道学报，2004，26 （4）：5-9．

[2] 谢楚农，黎新华. 铁路客运站到发线运用优化研究[J]．中国铁道科学，2004，25（5）：130-133．

[3] 龙建成，高自友，马建军，等. 铁路车站进路选择优化模型及求解算法的研究[J]．铁道学报，2007，29 （5）：7-14．

[4] D. D.L. Cardillo, M. Nicola. K L-list coloring of graphs [J].European Journal of Operational Research, 1998, 106(1): 160-164.

[5] 徐 杰，杜 文，李宗平，等. 基于模拟退火算法和图着色的调车机车安排研究[J]．铁道学报，2003，25（3）：24-30．

[6] 高世蕊. 客运专线车站通过能力计算方法的研究[J]．铁道运输与经济，2005，27（10）：92-94．

[7] 张惟皎，史天运，陈 彦. 动车运用所存车线运用方案优化模型与算法[J]．中国铁道科学，2013， 34（1）：21-125．

责任编辑 杨利明

Research on optimizing model and algorithm of train route for large-scale railway passenger station

WU Jinfei, WANG Weiwei
( Institute of Computing Technologies, China Academy of Railway Sciences, Beijing 100081, China )

The paper built the multi-goal programming model of utilization of arrival and departure track at the large-sized railway passenger station by taking utilization of arrival and departure track and safety assurance for both train operation and technical operation as the target which included reducing the running distance and time for passengers to go into the station or get out of the station, any two departure or nonstop trains whose departure times were close won’t stay in the same platform as possible as they could, and effective utilization of the existed technical equipment for train operation at station such as balance the occupied and free time of every track. It was obtained each weight by ahp to optimization objective of model. The Heuristic Algorithm was selected to solve the model in this paper. The better application scheme of arriving-departure tracks was obtained under the real-life case of a large-sized railway passenger station.

passenger station； selection of train route；multi-objective planning；Heuristic Algorithm

U291.6∶TP39

A

1005-8451（2014）05-0001-05

2013-12-06

武晋飞，研究实习员；王炜炜，助理研究员。