基于启发式回溯算法的铁路编组站调车场股道活用研究

马 亮，张晓霞，郭 进

(1.电子科技大学 光电信息学院，四川 成都 610054；2.西南交通大学 信息科学与技术学院，四川 成都 610031)

调车场是编组站办理改编作业的关键设施，对通过车站的车流起着“蓄洪”作用，如果调车场股道得不到灵活运用，可能会造成车站堵塞。为了提高解编调车作业效率和阶段计划配流方案的兑现率，需要在动态配流的基础上，实现调车场股道活用。

一般情况下车站调度员(站调)按照“定而不死、活而不乱”的指导思想对调车场股道分工灵活掌握，但是当列车不均衡、密集到达、车流方向远多于调车场股道数时，很难做到灵活使用股道。文献[1-3]研究调车场股道的固定使用，一般用来作为实际作业的基本准则。在以往阶段计划智能编制研究[4-7]中很少考虑调车场股道的活用对动态配流的影响，如果调车场股道得不到充分活用，可能会影响到发车流的接续关系和配流方案的实施。文献[8]研究了配流和调车场股道调整使用的协同优化，但是模型中将不同方向的车流尽量流入不同的股道，这样可能会增加解体钩数和编组钩数；同时，文献中只是以出发车流来源作为调车场车流变化的依据，没有考虑解编作业和车辆在车列中的顺位等因素，模型和算法还需完善。

本文在动态配流决策出解编作业起止时间和出发车列车流来源及编组内容[8]的基础上，综合考虑了调车场车流随着解编作业动态变化、调车场股道的容量和解编作业时序限制等，并设计“开口”算法将到达车列按照顺位、去向(车种)分为车组，以车组在调车场集结股道为变量，建立调车场股道活用整数优化模型。为了加快求解，在同去向车流尽量集结于一条股道、其他车流集结不影响编入出发车列的车流集结、减少越区作业和交叉干扰等规则的基础上，设计了变量取值动态排序(Value Ordering Heuristics， ValOH)[9，10]的启发式回溯算法(Heuristic Backtracking，HBT)[10]每次选择优先级最高的股道，当没有股道能够容纳此车组时回溯，最终无解时就二次分解车组，直到所有的车组都有集结股道并达到最优。

1 调车场股道活用问题描述及求解思路

调车场股道按照用途分为如下几类[11]：

(1)供列车编组计划规定的到站或去向的车辆解体、集结、编组用的线路，包括直达、直通、区段、摘挂以及小运转列车集结、解编用的线路和编发线；

(2)供空车解体、集结、编组用的线路；

(3)供本站作业车或交换车用的线路；

(4)供其他专门作业用的车辆停车的线路，主要指守车、待整车、倒装车、待修车、超限车或禁止过峰车以及危险品、易燃品车等的停留线。

定义1前三类股道中集结具有方向(车种)属性的有调车，可以统一称为活用股道集；站调在编制阶段计划时无法准确掌握扣修、禁溜和禁过峰等专用车辆，所以将第四类股道称为固定股道集。

定义2将到解车列编组顺序表中的车辆按照方向(车种)归类成形如“方向(车种)/辆数”称为编组内容；如果再考虑车辆在车列中的顺位，即相邻的且方向(车种)相同的车辆归为一类，称为顺位编组内容。

调车场存车状态的变化不仅和车辆的方向(车种)有关，还与车辆在车列中的顺位有直接关系，所以在为到解车列“开口”划分车组时应以车列的顺位编组内容为依据。

定义3为了解体照顾编组，将到解车列中顺位相邻且编入相同出发车列、包含在同一条列车编组计划或者相同方向(车种)的车辆归为一组，称为到达车组。如果车组被编入某出发车列，则车组特征为出发列车车次，否则为列车编组计划的到站或者为车流方向(车种)，且特征优先级依次降低。

在制定调车场股道活用方案时，应该尽量使得同特征的到达车组在一条股道上集结。而且低等级特征车组尽量不要影响高等级特征车组的集结。

定义4到解车列中顺位小的车辆靠近驼峰，优先解体；调车场股道中顺位大的靠近驼峰。如果某股道中只有一个车组，那么称为露头股道。将调车场股道中顺位最大车组的特征称为此股道的露头特征。如果选择露头特征与某车组特征相同的露头股道作为某车组的集结股道，称为露头原则。

在为车组选择集结股道时应优先考虑露头原则，其次再选择低级别的股道，这样既能降低股道的混用率，也能减少出发车列的编组调车钩数。

定义5由能够容纳某到达车组的活用股道构成的集合称为此车组的可行活用股道集。根据可行活用股道集中各股道的存车状态及到达车组特征按照股道活用规则划分为若干等级股道群。

调车场股道活用应充分体现解体照顾编组、当前解体照顾后续解体、减少交叉干扰、均衡资源(牵出线、解编调机)运用等原则。将可行活用股道集按照满足活用规则程度划分等级股道群，并为到达车组优先选择高等级股道群中股道。

定义6任何时刻每条股道包含不同顺位、不同特征的车组数称为此时股道的混乱度。

每条调车场股道应尽量集结同特征的车组，这样才能实现“一挂编组”，达到解体照顾编组的目的，所以任何时候都要使得股道混乱度最小。

编组站调车场股道活用是根据动态配流方案、车列顺位编组内容、阶段开始调车场现车及车流动态变化，为每个到达车组选择可行的集结股道，以提高阶段计划兑现率和降低调车作业成本(调车钩数、调车行程、调车时间等)[12]。由于确报和线路信息的不完整，目标函数可以由股道混乱度最小和集结股道优先级最大等价描述。调车场股道活用决策变量解空间随着之前车组的集结而动态产生，符合回溯算法特征。为了加快搜索速度使用启发式信息生成等级股道群，优先选择高等级股道达到剪枝目的。

2 调车场股道活用整数规划模型

2.1 常量

在编制调车场股道活用表之前可以通过列车编组计划、动态配流方案、确报和现车等车站管理信息子系统(SMIS)获得：阶段时间内到解车列溜放作业的起止时间和编组顺序表，出发车列编组作业的起止时间、车流来源和编组顺序表，货物列车编组计划，调车场股道的属性和阶段初始时刻各股道的存车状态等已知信息，定义常量如下：

2.2 到达车列“开口”划分车组及模型变量

到达车列并不是整列溜放，而是根据车辆的顺位、去向(车种)划分为车组。不同的划分方法会产生不同的调车场股道存车状态，最终会影响股道活用方案的优劣。为了达到解体照顾编组目的，应该尽量将编入同一出发车列的车辆划分为一组，剩余车辆再按照列车编组计划归为一组，最后再按照去向(车种)划分为一组。

(1)确定每个车辆的特征

(2)划分车组

(3)模型变量

2.3 调车场车流动态变化

调车场车流动态变化是指调车场股道存车随着到达车组的解体和出发车列的编组而增减。为了保障安全，目前大多数编组站还是采用双推单溜或者单推单溜的解体方式，即使采用双推双溜模式也是分为两个互不干扰的调车系统，因此，各车组溜放作业不会重叠，故车组对调车场股道车流变化的影响是确定的。编尾可以同时编组几列出发车列，但是由于车辆在调车场股道中的位置已经确定，因此编组作业对股道状态变化的影响也是确定的。

(1)调车场车流初始状态

调车场初始状态并不是阶段开始时刻调车场的现车状态，而是编组完毕时刻不晚于第一个到达车组溜放开始、车流来源都是编组场现车的出发车列编组完毕并转线而导致调车场车流减少的状态。

∀k=1，…，lh，∀j=1，…，n

( 1 )

式( 1 )中集合减“-”表示在相应股道的车辆集中剔除满足条件的车辆；“←”表示用剔除之后的车辆集替换之前的车辆集。

(2)调车场车流增加状态

∀i=1，…，m

( 2 )

(3)调车场车流减少状态

∀j=1，…，n

( 3 )

2.4 目标函数

调车场股道活用的目的是使得阶段计划密切联系实际调车作业，提高阶段计划的兑现率，加快调车作业效率。要想使得调车作业效率最高，应该尽量使得同种特征的车组在一条股道上集结。

( 4 )

式( 4 )表示任何时刻调车场股道的混乱度最小。

要想使得调车作业效率最高，除了要尽量满足露头原则，还要考虑实际作业中调机的分工、均衡牵出线负担、减少越区作业和交叉干扰等。所以每个车组应该优先选择最大化满足上述原则的股道，即优先选择高等级股道群中的股道。

( 5 )

2.5 约束条件

任何时刻车组集结都应该满足股道容量限制。

(1)调车场股道换长限制

( 6 )

(2)调车场股道重量限制

( 7 )

3 启发式回溯算法

为了提高基本回溯算法(Backtracking Algorithms，BT)[13]的求解效率，本文使用变量动态排序启发式(Variable Ordering Heuristics，VarOH)[14，15]算法对未实例化变量进行排序，为分支选择提供决策支持，使得较早检测出冲突。还可以引入变量取值动态排序启发式(Value Ordering Heuristics，ValOH)[9，10]对论域中的变量进行优先级排序，加快收敛速度。由于模型中变量顺序按照车组溜放时间和顺位唯一确定，所以采用ValOH技术，对每个车组可行股道集进行优先级排序，用优先级最高的股道实例化变量。

3.1 变量取值动态排序启发式

3.2 二次分解车组

3.3 启发式回溯算法

3.4 算法时间复杂度分析

4 算例分析

4.1 算例求解

假设2013年8月15日某编组站调车场12:00～15:00阶段内其他股道被固定使用，各活用股道的属性及阶段开始时刻的存车情况见表1，12:00～15:00之间的计划到达和出发车列数据见表2和表3，货物列车编组计划见表4。由于到发车列的编组顺序表和调车场车辆信息量比较大，文中不作详列，只给出车列或者车组的顺位编组内容，到达车列顺位编组中最左边车辆最靠近驼峰，调车场股道顺位编组中最右边车辆最靠近驼峰。

表1 调车场股道数据

表2 阶段内计划到达列车数据

表3 阶段内计划出发列车数据

表4 阶段内货物列车编组计划数据

本模型及算法在Inter Core i3-2310M 2.1 GHz & DRAM 2G & Windows XP& JDK1.6环境下的PC机上运行。由于本算例中所有车组都有可行股道，所以算法等同于贪心算法，但是由于在可行股道启发式排序算法中充分考虑了当前车组的集结对后续车组集结的影响等，所以结果接近于全局最优解。如图1所示为启发式回溯算法求解过程，总的求解时间为5.4 s，调车场股道混乱度之和最小为675，车组集结股道优先级之和最大为204，最后得到车组划分和调车场股道活用方案见表5。

图1 启发式回溯算法求解过程

4.2 结果分析

从表5可知，编入出发车列的车组基本上选择满足露头原则的股道，最大限度地实现了“一挂编组”，达到了解体照顾编组要求。其他特征的车组当不存在露头股道时，避免选择空闲或者露头特征为某出发列车的股道，确保高等级车组按照露头原则选择集结股道。譬如第8个车组溜放前各股道中没有去往保定方向的车组，最后决策此车组借用露头特征为丰台的BZ08，只有这样第9个车组才能按照露头原则集结。

表5 到达车组股道集结方案即股道活用方案

如果没有空闲且露头的股道时，车组借用一条混乱度最大且剩余容量最小的股道集结。譬如第5个车组借用BZ08后，后续的第8、13等车组都集结于此股道。降低了其他重要股道的混乱度，达到了当前解体照顾后续解体的目的。

4.3 与基本回溯算法比较

以式( 4 )为目标函数设计基本回溯算法，从图2可得当求解时间达到20 min时股道混乱度之和最少为740，所以基本回溯算法效率和质量远低于启发式回溯算法。

图2 基本回溯算法求解过程

5 结论

为了提高解编调车作业效率和阶段计划的兑现率，本文在动态配流的基础上，综合考虑了调车场存车随着解编作业动态变化、调车场股道的容量和解编作业时序限制等，建立编组站调车场股道活用整数规划模型。并结合现场实际，以同去向车流尽量集结于一条股道、其他车流集结尽量不影响出发列车源车流的集结、减少越区作业和交叉干扰等为原则，建立变量取值动态排序的启发式回溯算法，提高了算法求解效率。通过算例表明启发式回溯算法比基本回溯算法效率要高；调车场股道活用方案比固定使用方案更能适应车流不均衡、密集到达情况。在此基础上对动态配流方案进行调整，譬如延长部分到发车列解编作业时间和调整车流使用方案等，实现阶段计划的综合最优化。

参考文献：

[1]孙玉明,李红漩.编制编组站调车场线路固定使用方案的探讨[J].铁道运输与经济,2003,25(12):20-21.

SUN Yuming,LI Hongxuan.Discussion on Making Regular Utilization Plan of Shunting Yard Tracks in Marshalling Station[J].Railway Transpotr and Economy,2003,25(12):20-21.

[2]任勇.驼峰调车场线路固定使用方案的研究[J].太原科技,2003(5):24-26.

REN Yong.Research on the Scheme of Fixed Line Application at Hum PShunting Yard[J].Taiyuan Sci-Tech,2003(5):24-26.

[3]陈伯羽.铁路调车场线路固定使用方案优选方法研究[J].铁道科学与工程学报,2006,3(6):80-82.

CHEN Boyu.Studying of Optimization of Fixed Usage Plan for Railway Marshalling Yard Tracks[J].Journal of Railway Science and Engineering,2006,3(6):80-82.

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

[5]王琦.不确定环境下编组站阶段计划优化研究[D].北京:北京交通大学,2010.

[6]王明慧,赵强.编组站智能调度系统阶段计划优化模型及算法研究[J].铁道学报,2005,27(6):1-9.

WANG Minghui,ZHAO Qiang.Optimal Model and Algorithm of Stage Plan of Intelligent Dispatching System for Marshalling Stations[J].Journal of the China Railway Society,2005,27(6):1-9.

[7]王世东,郑力,张智海,等.编组站阶段计划自动编制的数学模型及算法[J].中国铁道科学,2008,29(2):120-125.

WANG Shidong,ZHENG Li,ZHANG Zhihai,et al.Mathematical Model and Algorithm for Automatically Programming the Stage Plan of Marshalling Station[J].Chinese Railway Science,2008,29(2):120-125.

[8]薛峰.编组站调度系统配流协同优化理论与方法研究[D].成都:西南交通大学,2009:91-105.

[9]HOOKER J N.Optimization and Constraint Programming[J].Informs Journal on Computing,2002,14(4):295-321.

[10]ROSSI F,et al.Handbook of Constraint Programming[M].Pisa:Elsevier,2006:103-109.

[11]刘其斌,马桂贞.铁路车站及枢纽[M].北京:中国铁道出版社,1999.

[12]胡思继.铁路行车组织[M].2版.北京:中国铁道出版社,2009:21-22.

[13]GOLOMB S W,BAUMERT L D.Backtrack Programming[J]. Journal of the ACM(JACM),1965,12(4):516-524.

[14]BACCHUS F,RUN P V.Dynamic Variable Ordering in CSPs[C]//Principles and Practice of Constraint Programming-CP′95.Springer Berlin Heidelberg,1995:258-275.

[15]HUANG J,DARWICHE A.A Structure-based Variable Ordering Heuristic for SAT[C]//IJCAI-03.Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence.United States:International Joint Conferences on Artificial Intelligence,2003:1 167-1 172.

[16]吕国英,任瑞整,钱宇华.算法设计与分析[M].北京:清华大学出版社,2006:211-226.

[17]赵端阳,左伍衡.算法分析与设计[M].北京:清华大学出版社,2012:207-247.