高速铁路车站咽喉区与到发线综合运用优化

刘 杰，殷 勇*，甘志良

(1.西南交通大学交通与物流学院，成都610031；2.综合交通运输智能化国家地方联合工程实验室，成都610031)

0 引言

高速铁路到发线和咽喉区作为车站完成技术作业的重要设备，其作业效率和运输组织直接影响着整个路网的输送能力.将两者进行综合运用研究对优化车站作业组织、提高作业效率具有重要意义.

近年来，国内外学者在该领域的研究重心逐渐转移到高速铁路车站.文献[1]将到发线分配问题看成时间上具有限制的排序问题，并说明到发线运用属于NP-hard问题.文献[2]用点包装问题描述到发线运用问题，建立了0-1整数规划模型.文献[3-4]以作业成本最小化为目标构建模型.文献[5]基于设备使用均衡和旅客服务质量分别建立到发线运用优化的多目标模型.文献[1-5]都构建了到发线运用优化模型，但均未考虑与咽喉区进路选择的协调优化且都只考虑了1个目标.文献[6]基于既有研究成果建立到发线和咽喉区使用均衡的优化模型，但未考虑列车接续时间问题.文献[7]基于到发线使用均衡和进路偏好最大建立综合运用优化模型，采用线性加权法求解，目标权重赋值主观性较强，仅能得到问题的局部最优解.文献[8]建立设备占用效用最大的过站径路模型，然而在求解时未考虑进路占用效用和到发线运用方案的稳定性.

上述研究在到发线与咽喉区运用整体性、求解算法适用性、作业计划稳定性等方面存在的不足，本文建立高速铁路车站到发线与咽喉区综合运用优化模型，基于改进的带精英策略的非支配排序遗传算(NSGA-II)对模型进行求解，得到的多种优化方案为车站日常作业组织提供一定的参考.

1 问题描述

到发线是为完成各类列车作业而专门设置的线路，咽喉区是提供由进站端接入至到发线和从到发线走行至出站端的通道.到发线使用规则决定了列车接入的到发线集合，接发列车对应多个接发车进路.如何在满足列车到发时刻、作业时间标准、到发线占用原则[9]及咽喉区进路占用原则[10]、动车组运用方案的前提下，确定所有接发列车的到发线及咽喉使用方案是研究的难点.

2 建立综合运用优化模型

2.1 模型基础及假设

已知车站站型、列车运行图、作业时间标准、到发线固定使用方案及动车组接续关系；具备接续关系的列车必须停靠在相同到发线；不考虑分段解锁，轨道电路的解锁时刻与所属咽喉区的完全解锁时刻相同；假设动车段的能力没有限制.

2.2 变量设置

假设某时段高速铁路车站接发列车数量为m，根据到站先后编号为i，列车集合为I={1 ,2,…,i,…,m} ；到发线数量为n，编号为j，到发线集合为J={1 ,2,…,j,…,n} ；列车i接入到发线j的进路集合为列车i接入到发线j的选用第k条进路列车i从到发线j出发的发车进路集合为列车i从到发线j的选用第k条发车进路，

决策变量有：

2.3 目标函数

(1)到发线占用与列车匹配最合理.

为保证作业安全有序，上下行列车分别接在上下行到发场.列车接入的到发线与列车停站时间、列车等级和列车在站作业方式等最大程度匹配.匹配性程度用到发线占用费用来体现.优化目标1表示为

式中：cij为列车i占用到发线j的费用.

目前多数学者的处理方法是为其赋予0、1、M共3种取值，无法体现不同种类列车占用到发线的费用差异[11].基于此，本文综合考虑列车运行方向、停站时间、在站作业方式和列车等级构建到发线占用费用矩阵.具体方法如下：

假设列车运行方向集合S=(1,2,∙∙∙,s)，列车分方向费用矩阵为某方向列车停靠在j到发线，j到发线越靠近正线费用值越低，列车遵循正接正发时费用越低；列车作业类型集合Y=(1,2,∙∙∙,y)，列车作业方式费用矩阵与列车进行的始发、终到、停站、通过相关，且与到发线固定作业方式匹配程度相关；列车种类集合G=(1,2,∙∙∙,g)，列车种类费用矩阵与列车的等级和接入到发线的匹配程度密切相关.定义算子⊕ ，若M=(h1,h2,∙∙∙,hn) ，N=(u1,u2,∙∙∙,un) ，则T=M⊕N=(max(h1,u1),∙∙∙,max(hn,un)).基于算子运算规则，列车i的费用矩阵为

列车费用矩阵构成了到发线占用费用矩阵C=(cij)，当cij=∞时，表示列车i不能接入到发线j；当cij≠∞时，表示列车i可以接入到发线j，所产生的费用为cij.

(2)提高车站作业计划稳定性.

增大占用同一到发线的相邻列车间的缓冲时间可有效提高车站作业计划的稳定性，同时兼顾到发线的均衡使用[12].假设列车i和i*接入同一到发线j，且列车i早于列车i*到达车站，则列车之间的缓冲时间表示为

因此，优化目标2表示为

(3)选择长度短、道岔少的进路完成接发车作业.

采用进路占用费用体现方案的优劣.目标函数3表示为

2.4 约束条件

优化模型应满足下列约束条件：

(1)列车只能选择1条到发线进行作业，约束为

(2)到发线有效满足列车接入条件，约束为

式中：Lj为编号为j的到发线的有效长度；li为编号为i的列车长度.

(3)列车只能选择1条接车进路和发车进路，约束为

(4)到达同一到发线的相邻列车作业之间须满足最小安全时间间隔，约束为

(5)具备动车组折返关系的2列列车必须安排在同一到发线上，约束为

式中：Mii*为0-1变量，依据列车方案确定，列车i与列车i*存在折返关系，取值为1；否则，为0.

(6)具有旅客换乘关系的列车必须停靠在同一站台的到发线上，约束为

式中：Gjj*为0-1变量，依据车站站型确定，若到发线j与j*临靠同一站台，取值为1，否则，取值为0；Fii*为0-1变量，若列车i与列车i*存在换乘关系，取值为1，否则为0.

(7)通过列车s*应安排在正线上，约束为

式中：L(j)为车站正线的集合；S*为通过列车集合.

(8)占用接发车作业进路的交叉干扰疏解，约束为

(9)变量取值约束为

3 基于多目标遗传算法求解综合运用优化问题

上述模型是1个多目标0-1规划模型，此类问题通常不能得到唯一解使各个目标都达到最优，只能得到Pareto最优解集.针对该类问题，一些学者求解的思想在于将多目标问题转化为单目标问题求解，但转化过程中权重等参数难以确定且受人为影响较大.部分学者采用启发式算法对模型求解，但如何快速全面的找到具有收敛性的Pareto最优解集是求解问题的难点.本文采用改进的带精英策略的非支配排序遗传算法(NSGA-II)对模型求解.算法在保存优秀个体和降低计算复杂度2个方面作了改进.

(1)染色体编码和解码：采用整数编码的方式，列车数量为m，到发线数量为n，以列车占用的到发线作为编码数值，编码方式如图1所示.对图1的编码子串进行解码，列车1占用到发线2，列车2占用到发线5，依次解码不再赘述.

(2)种群快速非支配排序：使用快速非支配排序对种群进行排序，为种群中的每个个体返回2列，分别是排序等级和拥挤距离.

(3)选择算子：采用二进制锦标赛选择，选择过程中，随机比较2个个体的排序等级，选择排序等级低的个体，如果等级相同，则比较拥挤距离，选择拥挤距离大的个体.

(4)交叉和变异：2个染色体之间的交叉如图2所示，设交叉概率为pm，变异概率为pc，两者可发生在编码的任意位置.染色体1和2的交叉如图2所示.

(5)精英策略：保留父代中的优良个体，直接进入子代，降低计算复杂度，同时保证精英个体不被遗漏.算法流程如图3所示.

图1 染色体编码Fig.1 Chromosome coding

4 算例分析

4.1 算例求解

以某高速铁路车站为例，如图4所示，接发A、C、E共3个方向的列车.动车段1、2分别与下、上行到发场连通.采用模型及算法，对车站8:00-16:00接发的84列列车安排相应股道及咽喉区进路.列车技术作业时间标准按表1取值，到发线占用费用矩阵如表所示2所示.

图2 染色体交叉示意图Fig.2 Chromosome cross diagram

图3 算法流程Fig.3 Algorithm steps

表1 作业时间标准Table 1 Operating time standard

图4 某高速铁路车站平面站型Fig.4 Layout of a high-speed railway station plane

表2 到发线占用费用矩阵Table 2 Occupancy cost matrix of arrival and departure line

列车从不同方向接入各到发线和从各到发线发出的最优接发车进路是确定的，例如从A端接入列车到股道1的最优接车进路经过的股道为：9,11,19,21,35,37,39,41.因此可以确定各到发线对应的最优接发车进路费用如表3所示.

表3 各股道最优接发车进路的占用费用Table 3 The cost of the optimal access route and departure route to the track

利用Matlab编程求解，参数为：初始种群100，最大进化代数200，交叉概率0.9，变异概率0.1.计算得到上行列车作业方案最优边界如图5所示.下行列车作业方案最优边界如图6所示.

图5 上行列车作业方案最优边界Fig.5 The optimal boundary of down train

图6 下行列车作业方案最优边界Fig.6 The optimal boundary of up train operation

4.2 结果分析

根据模型优化结果可知，有多种作业方案可供选择.不同目标函数对应的最优值对应图5和图6的边界点.选择解集中的一个方案，将其结果与原始方案进行对比分析，验证方案的合理性.

分析表4，得出如下结论：

(1)列车占用到发线匹配性.优化方案所有列车均采用“正接正发”的方式进行作业；接入临近正线的股道的列车数量较原始方案增多，列车接入与列车停站时间、列车等级和列车在站作业方式匹配度更高，占用总费用减少10.因此，到发线与列车匹配度更合理.

表4 优化前后车站作业方案的对比分析Table 4 Comparison and analysis of station operation schemes before and after optimization

(2)车站作业计划稳定性.优化后车站作业计划稳定性评价函数值减少225，说明优化方案稳定性更强；优化方案的股道平均缓冲时间和相邻两次占用股道的平均缓冲时间都有所增加，列车接入到发线的缓冲时间越大，车站抗干扰能力越强.

(3)接发车进路条件好.优化后车站接发列车占用总费用相比优化前减少475，列车接发的进路条件好.

(4)轨道利用均衡性.优化方案股道占用次数方差更小，到发线的使用越均衡.

5 结论

本文建立满足列车到发占用到发线匹配性最大、作业计划稳定性最强和接发车进路偏好性最好的优化模型.以某高速铁路车站为例，采用基于改进的带精英策略的非支配排序遗传算法(NSGA-II)编程求解，选择Pareto解集中一个方案与原有方案对比发现新的方案在列车与到发线的匹配性，车站作业计划的稳定性，接发车进路条件，轨道利用均衡性都较原方案优，验证了模型和算法的有效性，为车站日常接发车作业组织提供一定的参考.

[1]KANG L J,WU J J,SUN H J.Using simulated annealing in a bottleneck optimization model at railway station[J].Journal of Transportation Engineering,2012,138(11):1396-1402.

[2]ZWANEVELD P,KROON L G,HOESEL S P M V.Routing trains through a railway station based on a node packing model[J].European Journal of Operational Research,1997,128(1):14-33.

[3]CRAREY M,CRARVILLE S.Scheduling and plat forming trains at busy complex stations[J].Transportation Research,Part A,Policy and Practice,2003,37(A3):195-224.

[4]ZWANEVELD P J,KROON L G,HOESEL P M V.Routing trains through a railway station based on a node packing model[J].European Journal of Operational Research,2001,128(1):14-33.

[5]李琦.高速铁路大型客运站到发线运用优化研究[D].成都:西南交通大学,2012.[LI Q.Study on the optimization of the development of large-scale passenger station in high-speed railway[D].Chengdu:Southwest Jiaotong University,2012.]

[6]赵鹏,宋文波,陈霞,等.大型铁路客运站到发线与咽喉区综合运用优化[J].北京交通大学学报,2015,39(6):1-7.[ZHAO P,SONG W B,CHENG X.Comprehensive utilization of large-scale railway passenger station to hairline and throat zone[J].Journal of Beijing Jiaotong University,2012.]

[7]乔瑞军.客运专线车站接发车进路选择与调整问题研究[D].北京:北京交通大学,2012.[QIAO R J.Study on route selection and adjustment of 6passenger dedicated line[D].Beijing:Beijing Jiaotong University,2012.]

[8]陈彦.铁路客运站列车过站径路与调机运用优化[D].长沙:中南大学,2010.[CHEN Y.Optimization of trains and trunking of railway passenger station[D].Changsha:Central South University,2010.]

[9]王克豹.客运专线与既有线衔接站到发线运用优化研究[D].成都:西南交通大学,2011.[WANG K B.Study on optimization of passenger dedicated line and existing line connection station[D].Chengdu:Southwest Jiaotong University,2011.]

[10]陈建鑫.客运专线车站作业计划协同优化方法研究[D].北京:北京交通大学,2007.[CHEN J X.Research on cooperative optimization method of passenger dedicated line station operation plan[D].Beijing:Beijing Jiaotong University,2007.]

[11]江秀,倪少权,陈钉均.客运站到发线运用优化研究综述[J].铁道运输与经济,2014,36(11)：14-18.[JIANG X,NI S Q,CHEN D J.A summary of optimization research on the application of passenger terminal[J].Railway Transport and Economy,2014,36(11):14-18.]

[12]贾文峥.大型铁路客运站的进路分配问题及缓冲时间研究[D].北京:北京交通大学,2010.[JIA W Z.Research on route assignment and buffer time of large railway passenger station[D].Beijing:Beijing Jiaotong University,2010.]

[13]刁训娣.基于多目标遗传算法的项目调度及其仿真研究[D].上海:上海交通大学,2010.[DIAO X D.Research on project scheduling and simulation based on multi-objective genetic algorithm[D].Shanghai:Shanghai Jiaotong University,2010.]