高铁站到发线运用模型与算法

刘 源，牛慧兰，张 鑫，董海隆

（1.兰州交通大学 交通运输学院，甘肃 兰州 730070；2.郑州警察学院 交通管理工程系，河南 郑州 450000）

高铁站到发线运用模型与算法

刘 源1，牛慧兰1，张 鑫1，董海隆2

（1.兰州交通大学 交通运输学院，甘肃 兰州 730070；2.郑州警察学院 交通管理工程系，河南 郑州 450000）

为高效使用高铁站到发线，建立多目标整数规划模型，以到发线均衡使用和旅客站内走行距离最近为优化目标；以禁止反接到发线、满足最小时间间隔、使用单一到发线为约束。使用遗传算法求解，建立列车冲突矩阵与可用到发线集，确保初始、交叉与变异种群有效可行。结果表明：模型描述准确，算法效率较高，能够有效解决到发线运用问题。关键词：高铁站；列车冲突矩阵；遗传算法；到发线运用；多目标优化

高铁站接发的列车具有开行密度大、速度快等特点，旅客对其服务质量、列车正点率等有较高要求。到发线运用作为车站作业计划的一部分，对提高高铁站作业效率有着重要意义。

我国研究人员对到发线的运用做了相关研究，徐杰等［1］将到发线运用问题转化为k-顶点着色问题，并用遗传算法求解；张英贵等［2］利用现代排序论，以总费用最小和股道均衡使用为目标函数，建立多目标窗时排序模型；王保山等［3］根据车站拓扑结构建立优化模型，提出诱导变异，避免变异产生病态个体；何林等［4］以均衡使用到发线为优化目标，构建到发线占用权值；吕红霞等［5］提出时间片的概念，建立技术站到发线运用的二次0-1规划模型，并将模型分解为2个简单的0-1规划模型；Billionnet［6］以线性整数规划表示图着色模型，并用启发式算法求解。

从研究目标来看，多数文献主要考虑单个目标对于到发线运用优化的影响，对于多目标优化则没有提及。本文建立起多目标优化模型，研究在具有到发线均衡使用与旅客站内走行距离最近两个相互矛盾目标情况下的到发线运用问题。

1　问题描述

高铁站到发线运用计划根据列车运行计划、动车组运用计划与车站作业计划进行编制。到发线的使用应当遵循以下条件：

（1）每列列车从头部跨过进站信号机直至从到发线出发、尾部跨过出站信号机为止，期间只占用一条到发线；

（2）每条到发线在同一时间只能接发一列列车；

（3）为减少交叉干扰，禁止列车反接到发线。

条件（1）、（2）为到发线使用的硬性约束；条件（3）是在我国高速铁路的快速发展、列车开行密度逐步增大这一背景下提出的柔性约束。到发线的反接会造成接发列车作业时切割正线，产生大量敌对进路，影响车站作业效率。

以双线高铁站下行列车反接为例，下行列车到达进路接入上行列车到发场，与上行通过列车产生交叉干扰，并与上行列车出发进路产生交叉干扰；下行列车由上行到发场出发与上行列车到达进路产生交叉干扰。以上3种交叉均为行行交叉，会对高铁站作业效率造成较大影响。

2　建立到发线运用模型

设高铁站高峰时间段内顺序到达列车的集合为S，S=｛s1，s2，…，si，…，sn｝，i∈［1，n］，i为高峰时间段内到站的第i列列车，n为到站列车总数；高铁站到发线总数的集合为T，T=｛t1，t2，…，tj，…，tm｝，j∈［1，m］，j为高铁站第j条到发线，m为到发线总数［7］。

2.1列车信息集合

设高铁站顺序到达第i辆列车si包含以下信息：

在到发线运用问题中，高铁站可用到发线与空闲时间是一种有限资源，在时空条件的约束下，可建立矩阵Q用于存放到发列车的冲突情况。列车冲突包含3种情况如下：

（1）顺序到达的列车相同时间使用了不同的到发线；

（2）顺序到达的列车不同时间使用同一条到发线；

（3）顺序到达的列车在同一时间使用同一条到发线。

由于列车运用计划是固定的，在列车到站时间固定的情况下，时间冲突避免转变为时空冲突就显得尤为重要，建立列车冲突矩阵Q的目的就是为了避免情况（3） 的发生。

式中：qij表示列车i与列车j的时空冲突情况，qij∈Q，若两列车时间冲突则qij=1，否则qij=0。

2.2高铁站到发线运用模型

分别以到发线均衡使用和旅客站内走行距离最近为优化目标，建立到发线运用多目标整数规划模型，如式（3）、式（4）所示。

式中：t附加为接发车附加时间，包括为列车安排进路的时间，列车头部跨过进站信号机走行至到发线的时间，开放出站信号后列车尾部跨过出站信号机的时间。xij表示列车i是否占用到发线j，xij=1表示列车i占用到发线j，xij=0表示列车i不占用到发线j。

式中：C为列车停靠站台的权益矩阵，cij表示当第i列列车停靠在第j条到发线所在站台时的权值，cij=0表示G字头列车停靠在基本站台，cij=1表示反接站台。

旅客站内走行距离指的是旅客以高铁站进站口为起点，途经候车区直至列车停靠站台所经过的距离。一部分高铁站候车区布局与既有客站类似，如新乡东站。但另一部分高铁站候车区直接与站台对接，旅客从进站口走行至对应列车候车区距离不同，但从对应候车区走行至站台距离相同，如郑州东站。旅客站内走行距离可以表示为：M=m1+m2，m1表示旅客从进站口至对应候车区的距离，m2表示旅客从对应候车区至列车停靠站台的距离。无论是哪一种候车区布局，旅客站内走行距离通常为基本站台最近，距离基本站台越远走行距离越远，因此，可以将旅客站内走行距离与停靠站台相关联。

建立矩阵L存储列车等级与接发站台的信息。k为列车的等级信息，依据其技术速度将其分为不同等级；w为列车停靠高铁站站台信息，依据其停靠的站台，从基本站台直至反接站台依次划分等级。

建立起矩阵C与矩阵L的映射，依据列车等级信息与占用站台信息，找出其映射关系，确定列车的权益值。

根据前文所述，到发线运用问题的约束条件表示为：

式（7）表示列车i只能占用一条到发线；式（8）表示列车使用同一到发线应满足最小时间间隔，为列车i占用到发线j的发车时刻，为列车i+1占用到发线j的停车时刻；式（9）表示上下行列车应接入各自到发场；R（a）为列车行车方向。

3　基于遗传算法的求解

到发线运用问题属于NP-Hard问题，解决这类问题，随机化搜索是一种有效可行的方法。遗传算法作为一种启发式搜索算法，可以较好地解决到发线运用问题。

3.1染色体编码

采用自然数编码，建立一个包含n个元素的集合X，用以存放顺序到达列车占用的到发线信息。

3.2初始种群的生成

在随机生成初始种群的过程中，往往会产生不符合约束的染色体——列车与到发线产生时空冲突，解决的方法之一为构建罚函数。本文以杜绝产生不符合约束染色体为核心，依据列车冲突集合Q与可用到发线集合K，保证产生的染色体全部可行。

设置种群规模为40，染色体内基因个数为接发列车总数s，构建40×s的二维矩阵A。

产生初始种群的过程如下：

（1）随机生成种群内各染色体的第一个基因Aq；

（2）依据列车冲突集合Q，确定冲突列车占用的到发线，计算出可用到发线集合Aq（Kih；

（3）依据可用到发线集合Aq（Kih，随机确定该列车占用的到发线。

Aq（s1

5h表示种群A中第q条染色体第1位基因占用的到发线；Aq（Kih表示种群A中第q条染色体第i位基因的可用到发线集合。

3.3适应度函数的选取

由于高铁站到发线运用问题具有在同一约束条件下存在两个相互矛盾优化目标的特点，根据两优化目标重要程度不同求解就成了问题的关键。在解决这一问题时需要考虑两点：

（1）在考虑到旅客站内走行距离最近的时候，并没有考虑咽喉区道岔的使用，若仅仅使用近距离站台，势必造成行车作业中产生大量敌对进路，这并不利于高铁站行车设备的使用；

（2）由于有到发线均衡度的限制，低等级列车接发站台应优先考虑外侧站台，以便于高等级列车接入基本站台。将两个优化目标分别记为：

由于f1和f2的单位度量值不同，故需要进行无纲量化处理。根据式（11）、（12），按照两个优化目标的重要程度，分别赋予系数λ1、λ2，构建单目标适应度函数：

目标函数f3的权重矩阵采用专家法确定。将到发线均衡使用和旅客站内走行距离最近的重要性调查问卷分别发送给铁路技术部门与调度等生产部门，然后将之回收汇总，根据专家给出的结果进行计算。

式中：λj为目标j的权重系数，N为专家人数。

3.4遗传算子设计

分别采用轮盘赌选择法，依照f3的适应度选择个体。采用单点交叉，完成交叉操作后，若新生成的与存在列车到发线使用冲突，依据初始种群生成的思路，进行改良。随机选取种群内某一染色体，对其某一基因进行实值变异。如图1所示。

图1　染色体单点交叉

4　算例分析

模拟构建一通过式高铁站Z，衔接BJ、GZ两个方向，共有7条到发线、2条正线。其中Ⅰ、Ⅱ道分别为连接GZ、BJ方向的正线，3、5、7、9道所在区域为连接GZ方向的下行到发场，2、4、6道所在区域为连接BJ方向的上行到发场。找出Z站作业计划最繁忙时段，优化到发线使用。15∶00～18∶00时段，Z站共接发动车组26列，其中上行动车组12列，下行动车组14列。G字头动车组20列，D字头动车组6列，接发列车数据如表1所示。

利用Matlab编程，种群规模为40，基因长度为26，最大遗传代数为300，交叉概率为0.75，变异概率为0.05。确定到发线均衡使用为重要目标，旅客站内走行距离为次要目标，分别赋予权值0.9和0.1。

表1　Z站高峰时段接发列车

利用遗传算法求解，得到目标函数f3的最优值。由于上下行动车组分别接入上下行到发场故在计算到发线均衡使用、旅客站内走行距离时可以分别求解。列车占用到发线的初始安排如表2所示，最优安排如表3所示［8］。

作为重要目标，到发线均衡使用是指在高峰时段内到发线使用的时间方差最小。不考虑列车密集到达时同一条到发线大量使用，而另一时段空闲，只需注意在总的时间段内均衡即可。在初始安排中上行到发线f1=44.67，下行到发线f1=108.76；在最优安排中上行到发线f1=0.67，下行到发线f1=4.76。最优安排与初始安排相比，上下行到发线使用均衡度均大幅提升。

作为次要目标，旅客站内走行距离最近可以看作在到发线均衡使用的前提下，高等级列车优先接入距离站房近的站台，低等级列车优先接入远距离站台。在初始安排中，BJ方向的D字头列车s7接入较近站台；GZ方向的D字头列车s21接入较近站台。在最优安排中6列D字头动车组都接入走行较远站台，BJ方向的D字头列车s7、s16、s23分别接入4、6、6道；GZ方向的D字头列车s3、s17、s21分别接入7、7、9道。最优安排与初始安排相比，高等级列车接入近距离站台次数更多。Z站高峰时段到发现线运用最优方案如图2所示。

表2　Z站初始到发线运用安排

表3　Z站最优到发线运用安排

图2　Z站高峰时段到发线运用最优方案

5　结语

本文对于高铁站到发线运用问题，构建了多目标非线性整数规划模型，利用遗传算法求解。通过建立列车冲突集与可用到发线集保证产生健康个体，提高算法效率。在优化了到发线均衡使用的同时，缩短了高等级动车组乘客的站内走行距离。

在高铁站实际作业过程中，每条到发线通常都有两条及以上接发车进路，两列使用不同到发线的动车组也会因为接发车进路不同而使用相同道岔，造成行车作业交叉干扰。高铁站接发车进路的分配问题还需进一步研究。

［1］ 徐杰，杜文，常军乾，等.基于遗传算法的区段站到发线运用优化安排［J］.中国铁道科学，2003（2）：112-117.

［2］ 张英贵，雷定猷，汤波，等.铁路客运站股道运用窗时排序模型与算法［J］.铁道学报，2011（1）：1-7.

［3］ 王保山，侯立新，刘海东.客运专线车站到发线运用优化方法［J］.交通运输系统工程与信息，2012（2）：105-110.

［4］ 何林，吕红霞.高速铁路车站到发线运用优化研究［J］.铁道运输与经济，2012（8）：47-50，66.

［5］ 吕红霞，倪少权，纪洪业.技术站调度决策支持系统的研究——到发线的合理使用［J］.西南交通大学学报，2000（3）: 255-258.

［6］ Biilionnet A.. Using Integer Programming to Solve the Train-Piatforming Problem ［J］.Transportation Science，2003，37（2）：213-222.

［7］ 张苏波，廖勇，邹健康，黄志彤.基于遗传算法的客运站到发线优化安排［J］. 铁道运输与经济，2007（11）：24-27.

［8］ 左大杰，王慈光，陈韬.铁路旅客列车开行方案问题的研究综述［J］. 铁道运输与经济，2010（1）：35-39.

Model and Algorithm for Arrival-departure Track Utilization at High-speed Railway Station

Liu Yuan1， Niu Huilan1， Zhang Xin1， Dong Hailong2
（1. School of Traffic and Transportation， Lanzhou Jiaotong University， Lanzhou 730070， China；2. Transportation Management Engineering Department， Henan Police College， Zhengzhou 450000， China）

In order to use the arrival and departure track of the high-speed rail station efficiently， this paper established the overall planning model based on multi-objective. The balanced use of arrival and departure track and shortest walking distance in passenger station was looked upon as the optimization objective. Prohibiting to link the arrival and departure tracks on the contrary， meeting the minimum time interval and using a single track were regarded as constraint. Baesd on genetic algorithm it established train conflict matrix and available arrival and departure track set to ensure the initial， crossover and mutation reproduction effective and feasible. The results showed that the model description was accurate and the algorithm efficiency was high， which could effectively utilize the arrival and departure track.

high-speed railway station；conflict matrix；genetic algorithm；arrival and departure track；multi-objective optimization

U293.2

A

1672-9889（2015）02-0069-05

2014-07-03）

刘源（1989-），男，河南郑州人，硕士研究生，研究方向为运输规划与管理。