基于解体顺序的编组站到解作业计划自动化编制研究

赵金观，朱志国

(西南交通大学 交通运输与物流学院，四川 成都 610031)



基于解体顺序的编组站到解作业计划自动化编制研究

赵金观，朱志国

(西南交通大学 交通运输与物流学院，四川 成都 610031)

摘要:以阶段内正点出发列车数最多为目标，构建考虑列车解体顺序和配流问题的广义动态配流问题模型;设计按照先到先服务的原则和贪婪思想为每一列车分配车流的启发式算法，并确定到解列车的解体顺序。在解体顺序的基础上，运用已编制好的编组站到解作业计划自动化编制系统确定到解列车到发线和调机运用。研究结果表明：构建的模型和编制的系统较好地实现编组站到解作业计划的自动编制，能为编组站实际工作中作业安排提供决策支持。

关键词：编组站；阶段计划；广义动态配流；启发式算法；到解作业

阶段计划是编组站调度计划的核心部分，它既是实现日班计划的分阶段部署，又是编制调车作业计划的主要依据，包括配流、调车机车运用和到发线运用3个子计划。到解列车解体顺序是确定占用到发线时间和调机运用的关键因素，王世军等[1-5]分别针对到发线和调机运用进行了研究，赵金观等[6]对到发线和调机运用进行了协同研究，并考虑咽喉区行调车进路约束，建立到发线和调机运用模型,但没有给出解体顺序的确定方法；到解列车解体顺序与配流计划密切相关，王慈光等[7]构建了动态配流的树状模型，提出相应的回溯算法搜索有利方案，解决了解体方案的选择问题，但回溯算法在复杂情况下的搜索时间较长，影响算法的实用性，王正彬等[8-9]基于列车解编顺序对阶段计划配流进行研究，并分别采用混合遗传算法和和声搜索算法进行求解，王明慧等[10]设计了启发式算法求解，彭其渊等[11]构建了考虑列车解体顺序与配流的广义动态配流模型，设计了启发式算法对模型进行求解，但给出的算例结果有待商榷。本文在文献[6]的基础上，通过构建考虑解体顺序和配流计划的广义动态配流模型确定到解列车的解体顺序，同时运用已编制好的编组站到解作业计划自动化编制系统确定到解列车到发线和调机运用，并通过算例验证了算法和系统的实用性，为全面实现编组站阶段计划自动编制打下基础。

1模型构造和求解

1.1　模型说明

本文以纵列式编组站、解体配置2台调机进行作业、驼峰采用双推单溜的形式为例进行研究。

1.2　配流模型

1.2.1模型构造

Ts和Te分别为本阶段开始和结束时刻,这里以调机开始作业时刻为阶段开始时刻。

以该阶段正点出发列车数最大化为目标，可以等价于被正点出发列车吸收的车组最多，目标函数为：

列车解体顺序安排中，第p+1时段列车解体开始时刻必须在第p时段列车解体结束之后；第p时段列车解体开始时刻必须在该时段解体列车的最早可能解体时刻之后；且同一时段只能解体1列列车，同一列车只在1个时段解体，满足约束如下：

(1)

(2)

(3)

(4)

到达列车中的车组最多被一列出发列车吸收：

(5)

被出发列车吸收的车组必须满足编组计划的要求：

xi,k,j≤fj,bvi,k,b,

∀i∈ND,k∈K(i),b∈B,j∈NF

(6)

被出发列车吸收的车组应满足车流接续时间的要求：

xi,k,j≤σi,j,∀i∈ND,k∈K(i),j∈NF

(7)

(8)

出发列车应满足换算长度的要求

(9)

变量约束条件如下：

σi,j∈{0,1},∀i∈ND, j∈NF

(10)

1.2.2算法求解

上述模型在不考虑列车解体顺序的约束(1)~(4)下其已属于NP-C[1]，而单纯的解体顺序排序共有m种情况，整个问题复杂性进一步提升，对于该问题的求解，很难找到好的精确算法。本文为了便于编程实现，假设同一编组去向的车组换长都相同，且以列车满足换长的要求作为列车开行标准，设计针对上述模型的启发式算法，设计思路为：以配流为主线按照先到先服务的原则为每1列出发列车分配车流，直到该列出发列车最大程度地满足换长的要求或因接续车流不足而停运，最后统计出发列车数，并确定到解列车的解体顺序。算法每次只考虑1列出发列车，属于基于贪婪思想的启发式算法。在文献[4]的算法基础上加以改进，具体步骤为如下。

步骤2：引入0-1变量φj和δi，当出发列车j已满轴或停运时，取值为1，否则为0，当到达列车i已解体时，δi取值为1，否则为0。引入变量si，代表到达列车i的解体结束时间，其中s0=Ts。令当前出发列车集为J=NF和φj=0，∀j∈J，到达列车集I=ND，δ0=1和δi=0,i=2,…,n，并转入下一步。

步骤3：若J≠φ，转入下一步，否则转步骤10。

步骤6：若φj*=0，转下一步，否则，J=J{j*}，转步骤3。

若Ck≥Cj*，按下面2步进行分析。

2)判断需要解体的列数，在满足解体距离[7]条件下能配流成功，则，φj*=1，对相关列决策变量进行赋值，并更新δi，si，否则j*停运，令φj*=1，xi,b,j*=0,∀i∈I,b∈B′,k∈K(i)，转步骤6。

步骤10:统计出发列车数，并确定到解列车的解体顺序。算法结束。

2算例

以某纵列式编组站，驼峰采用双推单溜作业为例，对某车站作业进行安排。该编组站下行到达场咽喉区的示意图如图1所示，该到达场衔接了2个方向，有12条股道，其中，1道为正线，只用于接发通过列车，咽喉区共分为了10个道岔组；2台调机负责解体，1调负责2，3，4，5，6，7道列车解体，2调负责6，7，8，9，10，11，12道列车解体。列车解体作业时间标准为20 min，编组作业时间标准中远程直达、直通、区段列车均为25 min、摘挂、小运转列车为30 min; 列车到达和出发技术作业时间标准均为25 min；按照换长要求列车编组为35辆，摘挂列车允许欠轴开行；阶段初调车场没有现在车。

图1　某编组站下行到达场咽喉区示意图Fig.1 Layout of turnouts in the throat of arrival yard in a marshalling station

到达和出发列车信息数据分别见表1和表2。

系统生成的配流方案和到达列车解体顺序见表3和表4。

表1　列达列车信息

表2　出发列车信息

表3　出发列车配流方案

注：编组内容中，数字分别代表车辆来源、去向组号和辆数。

从生成结果可以看出，配流方案中除22212次出发列车因其接续车流不足而被停运外，其他出发列车都符合编制要求开行。

表4　到达列车解体顺序

设该编组站接车进路占用咽喉时间为5 min，调车进路占用咽喉时间为3 min，解体预推时间为5 min。根据表4中得解体顺序，系统求得到发线运用和调机运用具体方案见图2，对应进路咽喉道岔组占用情况见图3。

图2　到发线和调机运用方案Fig.2 Using of up-and-down lines and locomotive

图3　各进路咽喉道岔组占用情况Fig.3 Occupation of throat turnouts by each route

到发线和调机使用方案比较均衡，各个道岔组间没有交叉干扰，是可行的排列方案。

3结论

1)完善了阶段计划中配流计划和解体顺序的确定方法，设计的启发式算法能较快得到可行解，并通过算例验证了模型和系统的可行性；

2)编组站到解作业计划自动编制是编组站阶段计划自动编制的一部分，缺省了出发场股道安排和峰尾调机运用方案，可以作为下一步完善方案，争取全面实现编组站阶段计划自动化编制，为编组站实际工作提供辅助决策。

参考文献：

[1] 王世东，郑力，张智海，等.编组站阶段计划自动编制的数学模型及算法[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].China Railway Science,2008,29(2):120-125.

[2] 张英贵，雷定猷,刘明翔.铁路车站股道运用排序模型与算法[J].中国铁道科学,2010,31(2):97-100.

ZHANG Yinggui, LEI Dingyou, LIU Mingxiang.Scheduling model and algorithm for track application in railway station [J].China Railway Science,2010,31(2):97-100.

[3] 李文权,王炜,程世辉.铁路编组站到发线运用的排序模型和算法[J].系统工程理论与实践,2000,20(6):75-78.

LI Wenquan,WANG Wei,CHEN Gshihui.Scheduling modeland algorithm of using up-and down lineson railway mar shalling sation[J].Systems Engineering-Theory & Practice,2000,20(6):75-78.

[4] 王世东,郑力,张智海,等.蚁群算法在调机运用计划中的应用[J].中国铁道科学,2007,28(3):104-109.

WANG Shidong, ZHENG Li, ZHANG Zhihai,et al.Solving the scheduling problem of hump locomotive with ant colony optimization[J].China Railway Science,2007,28(3):104-109.

[5] 李文权,王炜,杜文,等.铁路技术站调机运用模型及算法[J].系统工程学报,2000,15(1):38-43.

LI Wenquan,WANG Wei,DU Wen,et al.The model and algorithm of using shunting engines for railroad technical service station[J].Journal of Systems Engineering,2000,15(1):38-43.

[6] 赵金观，朱志国.编组站到解作业计划自动化编制研究[J].铁道科学与工程学报，2015,12(4):71-75.

ZHAO Jinguan, ZHU Zhiguo.A study on the plan of using up-and-Down lines and locomotives in marshalling station[J].Journal of Railway Science and Engineering, 2015,12(4):71-75.

[7] 王慈光.编组站动态配流模型与算法研究[J].铁道学报,2004,26(1) :1-6.

WANG Ciguang.Research on the model and algorithm of dynamic wagon-flow allocating in a marshalling station[J].Journal of the China Railway Society,2004,26(1):1-6.

[8] 王正彬，杜文，吴柏青，等.基于解编顺序的阶段计划车流推算模型及算法[J].西南交通大学学报，2008，43(1) :91-95.

WANG Zhengbin, DU Wen, WU Baiqing, et al.Model and algorithm for estimation of wagon flow of stage operating plan based on break-up and make-up sequences[J].Journal of Southwest Jiaotong University,2008,43(1):91-95.

[9] 黎浩东,宋瑞,何世伟,等.基于列车解编作业时间估算的编组站阶段计划配流优化[J].中南大学学报(自然科学版),2014,45(1): 317-326.

LI Haodong, SONG Rui, HE Shiwei, et al.Wagonflow allocation of stage plan for marshaling station based on time estimation of breakup and makeup of trains[J].Journal of Central South University(Science and Technology), 2014,45(1):317-326.

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

WANG Minghui, ZHAO Qiang.Optimal model and algorithmof stage plan of intelligent dispatching system for marshalling stations[J].Journal of the China Railway Society, 2005, 27(6):1-9.

[11] 彭其渊，赵军，韩雪松.技术站广义配流问题模型与算法[J].中国铁道科学，2010，31(2) :108-114.

PENG Qiyuan,ZHAO Jun,HAN Xuesong.Model and algorithm for the generalized wagon-flow allocation problem of railway technical station[J].China Railway Science,2010, 31(2):108-114.

[12] Kroonl L G, Romeijn H E,Zwaneveld P J.Routing trains through railway stations: complexity issues[J].European Journal of Operational Reseach,1997,98(3):485-498.

[13] Zwaneveld P J, Dauzere PERES S, Hoesel C P M V, et al.Routing trains through railway stations: model figuretion and algorithms[J].Transportation Science,1996,30(3):181-194.

[14] Zwaneveld P J,Kroon L G, Hoesel C P M V.Routing trains through a railway station based on a node packing model[J].European Journal of Operational Research,2001(128):14-33.

[15] Crarey M, Crarville S.Scheduling and platforming trains at busy complex stations[J].Transportation Research, Part A, Policy and Practice,2003,37(A3):195-224.

(编辑阳丽霞)

Research on the utilizing of up-and-down lines and locomotives inmarshalling station based on the disassembling sequences

ZHAO Jinguan, ZHU Zhiguo

(School of Transportation and Logistics, Southwest Jiaotong University, Chengdu 610031, China)

Abstract：Aiming at maximizing the number of punctual outbounding trains, the paper establishes the generalized dynamic wagon-flow allocation model considering the train disassembling sequence and wagon-flow allocation problems.The heuristic algorithm according to the principle of first come first service and greedy thought allocating wagon-flow for each train was designed, and the disassembling sequences of the disassembled trains was then determined.Finally, based on the disassembling sequences, the utilizing of up-and-down lines and locomotives are made with the application of automatic operation arrangement system for disassembled trains.The numerical experiments show that the models and system can well accomplish auto-scheduling of operation planning in a stage , and provide decision support for marshaling station in practical work assignments.

Key words：marshaling station; stage plan; generalized dynamic wagon-flow allocation; heuristic algorithm; disassembled trains

通讯作者：朱志国(1963-)，男，辽宁锦州人，副教授，从事轨道交通规划与设计研究；E-mail:zhuzhiguo@home.swjtu.edu.cn

收稿日期：2015-06-15

中图分类号：U291

文献标志码：A

文章编号：1672-7029(2015)06-1507-06