铁路编组站调车场股道运用回溯算法及其改进型的分析与比较
蒋继磊
摘 要： 通过改进型回溯算法的使用，结合铁路编组站调车场股道车流运行实际情况，基于动态配流的方式，建立变量取值动态排序的改进型回溯算法。研究结果证实，在铁路编组站调车场股道优化运用中采用改进型回溯算法可以提高算法的求解效率，并能够使同去向车流尽量集结于一条股道，降低铁路编组站内调车场股道其他车流集结对出发列车车流集结的影响。在铁路编组站调车场股道中，应用改进型回溯算法能够有效解决既有铁路编组站调车场股道车流不均衡、车流密集到达的情况，提升算法求解效率，避免在铁路编组站调车场股道中发生越区干扰与交叉干扰的情况，从而发挥积极的应用价值。
关键词： 铁路编组站； 改进型回溯算法； 股道运用； 动态配流
中图分类号： TN081?34 文献标识码： A 文章编号： 1004?373X（2017）07?0124?03
Analysis and comparison of backtracking algorithm used in switchyard track in
railway marshalling station with its improved one
JIANG Jilei
（Signal & Communication Research Institute， China Academy of Railway Sciences， Beijing 100081， China）
Abstract： The improved backtracking algorithm of the variable value dynamic sorting was established in combination with the practical traffic operation situation of the switchyard track in the railway marshalling station and dynamic traffic assignment method. The research results confirm that the improved backtracking algorithm used in the switchyard track optimization of the railway marshalling station can improve the solving efficiency of the algorithm， assemble the traffic of the same direction into a track， and reduce the effect of the traffic assembling of the switchyard track in the railway marshalling station on that of the departing trains. The improved backtracking algorithm can solve the situations of the unbalance traffic and dense traffic arrival of the switchyard track in railway marshalling station， improve the solving efficiency of the algorithm， and avoid the overshooting?area interference and cross?area interference existing in the switchyard track in the railway marshalling station， which plays a positive application value.
Keywords： railway marshalling station； improved backtracking algorithm； track utilization； dynamic traffic assignment
0 引 言
在铁路编组站的调车场股道管理方面，应用基本回溯算法不能满足处理调车场股道车流不均衡、密集到达的需求，降低算法计算效率，使铁路编组站调车场容易产生车流集结、交叉干扰的问题，影响铁路编组站调车场股道车流的正常运行[1?3]。在铁路编组站中，做好调车场股道管理工作，不仅是编组站办理改编作业的关键，也对通过车站的车流发挥“蓄洪”作用，提高解编调车作业效率，灵活运用调车场股道，在动态配流基础上活用铁路编组站中调车场股道，避免造成车站堵塞[4?6]。在实际研究中，能够在为编组站车场股道实现动态配流的基础上，还可综合考虑铁路编组站调车场的存车状态变化，以及调车场股道容量及股道车辆解编作业时序限制，能够设计“开口”算法，建立阶段时间内的铁路编组站调车场股道活用整数优化模型，实现车流随解编作业变化。
1 铁路编组站调车场股道车流变化情况
在既有铁路编组站内，其调车场股道车流是动态变化的，主要表现为调车场股道存车会随着到达车组解体以及出发车列编组而有所增减。因此在实际调车场股道管理中，为能够保障调度安全，可以采用双推单溜以及单推单溜的车辆解体方式，各车组调车系统溜放作业不会重叠，互不干扰。然而，由于在铁路编组站调车场股道中已经事先确定好车辆在调车场股道内的位置，而编尾可以同时编组几列出发车列，故此在编组站内也需要考虑编组作业对股道状态变化的影响。在传统的调车场股道管理中，应用的算法是以出发车流来源为调车场车流变化的依据，协同优化配流和调车场股道，将不同方向的车流尽量流入不同的股道，从而增加解体钩数与编组钩数；但是并没有充分考虑在车列中解编作业以及车辆的顺位还需完善算法。对此，亟待优化设计铁路编组站调车场股道的管理办法，运用改进型回溯算法计算分析调车场股道车流运行情况，从而在优化铁路编组站调车场股道中的车流运行方案中发挥积极影响。
2 设计基于铁路编组站调车场股道运用的改进型
回溯算法
2.1 算法原则
随着解编作业动态变化，综合考虑铁路编组站调车场车流变化，可以应用改进型回溯算法设计调车场股道活用整数优化模型，并在采取此算法時确保每次选择调车场内优先级最高的股道[7]。具体来说，也就是当调车场内没有股道可以容纳车组时回溯，在最终无解时进行车组二次分解，直到确保此铁路编组站内所有的车组都可以有集结股道并达到最优。
2.2 设计变量取值动态改进型排序
对于车组[SZDik，]如果在调车场股道当前时刻[t∈TE]满足调车场股道换长限制约束（式1），也满足调车场股道重量限制（式2），则可行活用股道集表示为[Yikt，]为能够进一步使任何时刻铁路编组站调车场股道混乱度最小（式3），及任何时刻车组选择股道优先级最大（式4）的需求，可以在实际中，根据现场成熟经验对车组[SZDik]集结股道变量[htDik]取值进行改进型排序。
调车场股道重量限制约束：
[cqeDik≤rqeYht Dikt，?k=1，2，…，hZi，?i=1，2，…，h，?t∈TE] （1）
式中：[cqeDik]表示铁路编组站某一时刻的股道；[rqeYht]表示在铁路编组站调车场股道的剩余重量。
调车场股道换长限制：
[cVeDik≤rVeYmt Dikt，?k=1，2，…，hZi，?i=1，2，…，h，?t∈TE] （2）
式中：[cVeDik]表示某一时刻的股道；[rVeYmt]表示调车场股道剩余换长。
任何时刻铁路编组站调车场股道混乱度最小：
[maxr1=t∈TEn=1lTZYnt] （3）
任何时刻车组选择股道优先级最大：
[maxr2=i=1mj=1mZipriDjk] （4）
2.3 运用基本回溯算法分解调车场股道车组
在铁路编组站调车场股道管理运用中采用基本回溯算法，若没有股道能够容纳某一车组，则需要回溯。在动态改进型排序计算无解时，可以对这一车组进行二次分解，并记录之前车组的调度决策，具体方法如下：
（1） 获取调车场股道内等级最高的股道集。
（2） 在股道集中选择出剩余容量最大的股道，并将其组成新的股道集；若新的股道集大于1，则在铁路编组站调车场内可以选取随机股道运用，继续转入下一步。
（3） 可以在调车场内根据车辆顺位，依次累加铁路编组站内车辆的换长与轴重。
2.4 改进型回溯算法
（1） 在铁路编组站调车场股道管理运用中，针对所有到达车列进行基于“开口”划分车组，得到车列集合，从而可以获取触发后的调车场车流初始状态。
（2） 如果在调车场股道车辆调度达到求解时间上限，则返回调车场股道运用方案，计算出各车组集结股道及目标函数的最优值。
（3） 依次选择到达车列的某个车组的特征，通过回溯触发获取铁路编组站调车场股道车流减少的状态。
（4） 可以对集结股道变量进行实例化，触发获取铁路编组站内调车场股道车流的增加状态。
（5） 记录前面车组股道集结方案，并依次进行回溯计算，若无解，可以按照改进型算法对车组进行二次分解，再按照部分解继续进行搜索计算。
3 算法应用实例及其比较分析
3.1 实际案例
在某路网型编组站调车场[n]小时股道运用期间，基于铁路编组站内车列以及车组顺位编组的内容，在到达车列顺位编组中，使得最左边的车辆可以最靠近驼峰，而在调车场股道顺位编组中，使得最右边车辆最靠近驼峰。其实际的股道被固定使用，而对于其各活用股道的属性，以及各阶段开始时刻的存车情况见表1。
在此路网型编组站[n]小时调车场计划到达和出发列车数据，见表2。
在此路网型编组站内[n]小时期间货物列车编组计划，如表3所示。
3.2 改进型回溯算法与基本回溯算法计算过程数据比较
在此路网型铁路编组站调车场股道运用中，可以通过计算机程序求解，充分考虑当前调车场股道内所有车组集结后对后续车组的影响，计算分析所有车组可行股道的最优解。两种类型回溯算法的求解过程，如表4所示。
通过对表4中的数据比较分析可得，改进型回溯算法的求解时间效率是基本回溯算法求解时间效率的100倍左右，并且在此情况下，改进型回溯算法调车场股道混乱度之和也比基本回溯算法调车场股道混乱度之和减少100左右。在既有铁路编组站调车场股道管理中，可以运用改进型回溯算法计算分析调车场股道的车流运行情况，从而优化铁路编组站调车场股道中的车辆运行方案，活用调车场股道，使其产生积极应用价值。
4 结 论
综上所述，在我国目前的铁路编组站调车场股道运用管理中，可以积极采用改进型回溯算法，使之有效应对既有铁路编组站调车场股道车流不均衡、车流密集到达的情况，有效解决传统回溯算法应用铁路编组站调车场管理中的车流集结、交叉干扰的问题，提升改进型回溯算法的求解效率，避免发生越区干扰与交叉干扰的情况，提升编组站调车场股道的综合运用效率。
参考文献
[1] 马亮，张晓霞，郭进，等.基于启发式回溯算法的铁路编组站调车场股道活用研究[J].铁道学报，2016，38（8）：16?22.
[2] 马亮，郭进，陈光伟，等.基于约束程序累积调度的编组站静态配流模型研究[J].铁道学报，2014，36（1）：8?15.
[3] 曾鸣.铁路集装箱中心站物流系统资源调配优化与仿真研究[D].成都：西南交通大学，2015.
[4] 马亮，郭进，陈光伟，等.编组站静态配流的约束传播和启发式回溯算法[J].西南交通大学学报，2014，49（6）：1116?1122.
[5] 邦佳.编组站阶段计划编制问题研究[D].北京：北京交通大学，2012.
[6] 刘引涛.基于回溯算法的计算机机箱线路板排列问题的分析研究[J].现代电子技术，2014，37（18）：84?85.
[7] 戴圣法，魏庆国，魏中海.基于回溯搜索算法的导联选择脑机接口研究[J].现代电子技术，2016，39（13）：10?14.
摘 要： 通过改进型回溯算法的使用，结合铁路编组站调车场股道车流运行实际情况，基于动态配流的方式，建立变量取值动态排序的改进型回溯算法。研究结果证实，在铁路编组站调车场股道优化运用中采用改进型回溯算法可以提高算法的求解效率，并能够使同去向车流尽量集结于一条股道，降低铁路编组站内调车场股道其他车流集结对出发列车车流集结的影响。在铁路编组站调车场股道中，应用改进型回溯算法能够有效解决既有铁路编组站调车场股道车流不均衡、车流密集到达的情况，提升算法求解效率，避免在铁路编组站调车场股道中发生越区干扰与交叉干扰的情况，从而发挥积极的应用价值。
关键词： 铁路编组站； 改进型回溯算法； 股道运用； 动态配流
中图分类号： TN081?34 文献标识码： A 文章编号： 1004?373X（2017）07?0124?03
Analysis and comparison of backtracking algorithm used in switchyard track in
railway marshalling station with its improved one
JIANG Jilei
（Signal & Communication Research Institute， China Academy of Railway Sciences， Beijing 100081， China）
Abstract： The improved backtracking algorithm of the variable value dynamic sorting was established in combination with the practical traffic operation situation of the switchyard track in the railway marshalling station and dynamic traffic assignment method. The research results confirm that the improved backtracking algorithm used in the switchyard track optimization of the railway marshalling station can improve the solving efficiency of the algorithm， assemble the traffic of the same direction into a track， and reduce the effect of the traffic assembling of the switchyard track in the railway marshalling station on that of the departing trains. The improved backtracking algorithm can solve the situations of the unbalance traffic and dense traffic arrival of the switchyard track in railway marshalling station， improve the solving efficiency of the algorithm， and avoid the overshooting?area interference and cross?area interference existing in the switchyard track in the railway marshalling station， which plays a positive application value.
Keywords： railway marshalling station； improved backtracking algorithm； track utilization； dynamic traffic assignment
0 引 言
在铁路编组站的调车场股道管理方面，应用基本回溯算法不能满足处理调车场股道车流不均衡、密集到达的需求，降低算法计算效率，使铁路编组站调车场容易产生车流集结、交叉干扰的问题，影响铁路编组站调车场股道车流的正常运行[1?3]。在铁路编组站中，做好调车场股道管理工作，不仅是编组站办理改编作业的关键，也对通过车站的车流发挥“蓄洪”作用，提高解编调车作业效率，灵活运用调车场股道，在动态配流基础上活用铁路编组站中调车场股道，避免造成车站堵塞[4?6]。在实际研究中，能够在为编组站车场股道实现动态配流的基础上，还可综合考虑铁路编组站调车场的存车状态变化，以及调车场股道容量及股道车辆解编作业时序限制，能够设计“开口”算法，建立阶段时间内的铁路编组站调车场股道活用整数优化模型，实现车流随解编作业变化。
1 铁路编组站调车场股道车流变化情况
在既有铁路编组站内，其调车场股道车流是动态变化的，主要表现为调车场股道存车会随着到达车组解体以及出发车列编组而有所增减。因此在实际调车场股道管理中，为能够保障调度安全，可以采用双推单溜以及单推单溜的车辆解体方式，各车组调车系统溜放作业不会重叠，互不干扰。然而，由于在铁路编组站调车场股道中已经事先确定好车辆在调车场股道内的位置，而编尾可以同时编组几列出发车列，故此在编组站内也需要考虑编组作业对股道状态变化的影响。在传统的调车场股道管理中，应用的算法是以出发车流来源为调车场车流变化的依据，协同优化配流和调车场股道，将不同方向的车流尽量流入不同的股道，从而增加解体钩数与编组钩数；但是并没有充分考虑在车列中解编作业以及车辆的顺位还需完善算法。对此，亟待优化设计铁路编组站调车场股道的管理办法，运用改进型回溯算法计算分析调车场股道车流运行情况，从而在优化铁路编组站调车场股道中的车流运行方案中发挥积极影响。
2 设计基于铁路编组站调车场股道运用的改进型
回溯算法
2.1 算法原则
随着解编作业动态变化，综合考虑铁路编组站调车场车流变化，可以应用改进型回溯算法设计调车场股道活用整数优化模型，并在采取此算法時确保每次选择调车场内优先级最高的股道[7]。具体来说，也就是当调车场内没有股道可以容纳车组时回溯，在最终无解时进行车组二次分解，直到确保此铁路编组站内所有的车组都可以有集结股道并达到最优。
2.2 设计变量取值动态改进型排序
对于车组[SZDik，]如果在调车场股道当前时刻[t∈TE]满足调车场股道换长限制约束（式1），也满足调车场股道重量限制（式2），则可行活用股道集表示为[Yikt，]为能够进一步使任何时刻铁路编组站调车场股道混乱度最小（式3），及任何时刻车组选择股道优先级最大（式4）的需求，可以在实际中，根据现场成熟经验对车组[SZDik]集结股道变量[htDik]取值进行改进型排序。
调车场股道重量限制约束：
[cqeDik≤rqeYht Dikt，?k=1，2，…，hZi，?i=1，2，…，h，?t∈TE] （1）
式中：[cqeDik]表示铁路编组站某一时刻的股道；[rqeYht]表示在铁路编组站调车场股道的剩余重量。
调车场股道换长限制：
[cVeDik≤rVeYmt Dikt，?k=1，2，…，hZi，?i=1，2，…，h，?t∈TE] （2）
式中：[cVeDik]表示某一时刻的股道；[rVeYmt]表示调车场股道剩余换长。
任何时刻铁路编组站调车场股道混乱度最小：
[maxr1=t∈TEn=1lTZYnt] （3）
任何时刻车组选择股道优先级最大：
[maxr2=i=1mj=1mZipriDjk] （4）
2.3 运用基本回溯算法分解调车场股道车组
在铁路编组站调车场股道管理运用中采用基本回溯算法，若没有股道能够容纳某一车组，则需要回溯。在动态改进型排序计算无解时，可以对这一车组进行二次分解，并记录之前车组的调度决策，具体方法如下：
（1） 获取调车场股道内等级最高的股道集。
（2） 在股道集中选择出剩余容量最大的股道，并将其组成新的股道集；若新的股道集大于1，则在铁路编组站调车场内可以选取随机股道运用，继续转入下一步。
（3） 可以在调车场内根据车辆顺位，依次累加铁路编组站内车辆的换长与轴重。
2.4 改进型回溯算法
（1） 在铁路编组站调车场股道管理运用中，针对所有到达车列进行基于“开口”划分车组，得到车列集合，从而可以获取触发后的调车场车流初始状态。
（2） 如果在调车场股道车辆调度达到求解时间上限，则返回调车场股道运用方案，计算出各车组集结股道及目标函数的最优值。
（3） 依次选择到达车列的某个车组的特征，通过回溯触发获取铁路编组站调车场股道车流减少的状态。
（4） 可以对集结股道变量进行实例化，触发获取铁路编组站内调车场股道车流的增加状态。
（5） 记录前面车组股道集结方案，并依次进行回溯计算，若无解，可以按照改进型算法对车组进行二次分解，再按照部分解继续进行搜索计算。
3 算法应用实例及其比较分析
3.1 实际案例
在某路网型编组站调车场[n]小时股道运用期间，基于铁路编组站内车列以及车组顺位编组的内容，在到达车列顺位编组中，使得最左边的车辆可以最靠近驼峰，而在调车场股道顺位编组中，使得最右边车辆最靠近驼峰。其实际的股道被固定使用，而对于其各活用股道的属性，以及各阶段开始时刻的存车情况见表1。
在此路网型编组站[n]小时调车场计划到达和出发列车数据，见表2。
在此路网型编组站内[n]小时期间货物列车编组计划，如表3所示。
3.2 改进型回溯算法与基本回溯算法计算过程数据比较
在此路网型铁路编组站调车场股道运用中，可以通过计算机程序求解，充分考虑当前调车场股道内所有车组集结后对后续车组的影响，计算分析所有车组可行股道的最优解。两种类型回溯算法的求解过程，如表4所示。
通过对表4中的数据比较分析可得，改进型回溯算法的求解时间效率是基本回溯算法求解时间效率的100倍左右，并且在此情况下，改进型回溯算法调车场股道混乱度之和也比基本回溯算法调车场股道混乱度之和减少100左右。在既有铁路编组站调车场股道管理中，可以运用改进型回溯算法计算分析调车场股道的车流运行情况，从而优化铁路编组站调车场股道中的车辆运行方案，活用调车场股道，使其产生积极应用价值。
4 结 论
综上所述，在我国目前的铁路编组站调车场股道运用管理中，可以积极采用改进型回溯算法，使之有效应对既有铁路编组站调车场股道车流不均衡、车流密集到达的情况，有效解决传统回溯算法应用铁路编组站调车场管理中的车流集结、交叉干扰的问题，提升改进型回溯算法的求解效率，避免发生越区干扰与交叉干扰的情况，提升编组站调车场股道的综合运用效率。
参考文献
[1] 马亮，张晓霞，郭进，等.基于启发式回溯算法的铁路编组站调车场股道活用研究[J].铁道学报，2016，38（8）：16?22.
[2] 马亮，郭进，陈光伟，等.基于约束程序累积调度的编组站静态配流模型研究[J].铁道学报，2014，36（1）：8?15.
[3] 曾鸣.铁路集装箱中心站物流系统资源调配优化与仿真研究[D].成都：西南交通大学，2015.
[4] 马亮，郭进，陈光伟，等.编组站静态配流的约束传播和启发式回溯算法[J].西南交通大学学报，2014，49（6）：1116?1122.
[5] 邦佳.编组站阶段计划编制问题研究[D].北京：北京交通大学，2012.
[6] 刘引涛.基于回溯算法的计算机机箱线路板排列问题的分析研究[J].现代电子技术，2014，37（18）：84?85.
[7] 戴圣法，魏庆国，魏中海.基于回溯搜索算法的导联选择脑机接口研究[J].现代电子技术，2016，39（13）：10?14.
