基于状态转移的编组站列车调度优化模型

1、文章编号:100124098(20090720060205基于状态转移的编组站列车调度优化模型张林1,廖天俊1,刘英2(1.国防科学技术大学信息系统与管理学院,湖南长沙410073;2.重庆通信学院数学教研室,重庆400035摘要:编组站是铁路枢纽的核心,使车辆在编组站停留时间最短是解决编组站编组计划问题的关键。针对双向编组站列车调度问题,提出编组站系统状态转移关系模型,并由此生成约束条件,设计以中时最小为优化的目标函数,建立了基于状态转移的列车调度优化模型。以郑州北站数据进行实证分析,验证了模型的有效性和通用性。关键词:系统优化;编组站;编组计划;状态转移;非线性规划中图分类号:N945;U

2、292文献标识码:A1引言编组站的主要任务是根据列车编组计划要求,办理各种货物列车的解编作业,按照列车运行图规定的时刻正点接发列车。在铁路运输管理中,列车编组计划起着对铁路货物车流的组织作用,对车站的设备和能力进行统筹规划和综合使用1。目前的研究主要使用遗传算法、神经网络和模拟退火方法等解决列车编组计划问题2-6。文献7基于给定路网环境参数参考服务系统选址的增量算法,建立变量规模数为n3-n的寻找有利编组去向的数学模型。文献8考虑车站编组能力、解体能力等影响因素,以技术站车辆集结消耗、改编消耗整体最小以及改编能力均衡利用为目标函数,构建协同优化的多目标021规划模型。文献9以是否开行分组列车所

3、产生的技术效益最大化为目标,在引入阶跃函数的前提下,提出技术站分组列车编组计划的021规划模型。文献10研究双向编组站调度优化问题,以列车编成辆数、编组内容和作业能力等为约束条件,以列车的走行距离和产生的交换车数为综合优化的目标,构造列车调度调整的非线性优化模型。上述模型主要以费用、距离、能力等因素作为优化的目标来解决编组调度问题,对时间因素的重视程度不够,不能完全解决调度问题。据统计,列车一次全周转时间中,在编组站作业和停留的时间约占70%,因此提高作业效率,缩短车辆的周转时间对提高铁路运输能力具有重大意义。本文对编组站系统进行分析,提出了状态转移关系模型,根据此模型生成约束条件,并以中时最

4、小,即车辆在编组站的平均停留时间最短为目标函数进行优化,得到编组站列车调度的优化模型,模型的解反映了编组站各子系统的状态,可以更好地对调度作业进行实时控制。2模型符号约定定义符号和参数如下:k为阶段,定义为一列车的解体过程;q i表示到达场列车i的长度;at i为到达场列车i 的到达时刻;K为时段的集合;N为到达编组站列车的集合;R为到达场到驼峰区的轨道集合;Q i为列车i分解成的车辆集合;D A为驼峰区到编组场轨道的集合;D C,D S 分别为换向和不换向的轨道集合,且D A=D CD S; L m in,L m ax为列车的最小长度和最大长度;W m in,W m ax为列车的最小重量和最

5、大重量;t k为k阶段解体的开始时刻; T k是从初始到k阶段车辆停留时间的总和;T w为列车不换向直接转发的时间;T z为列车换向转发的时间;T h为车辆驼峰区解体到编组场集结的时间;T f为车辆从编组场到出发场的时间;b为021变量,表示车辆的类型,1表示重车,0表示空车。定义逻辑变量如下:J ij(k为021变量,如果列车i的第27卷第7期(总第187期系统工程V ol.27,N o.7 2009年7月Syste m s Engineering July.,2009收稿日期:2009205220基金项目:国家自然科学基金资助项目(60172012;国防科学技术大学优秀研究生创新资助项目(

6、S080501作者简介:张林(19852,男,四川彭山人,国防科学技术大学信息系统与管理学院研究生,研究方向:信息资源管理,系统优化;廖天俊(19852,男,重庆人,国防科学技术大学信息系统与管理学院博士研究生,研究方向:系统优化与综合集成;刘英(19562,女,重庆人,重庆通信学院数学教研室副教授,研究方向:数理统计,运筹学。第j 辆车在k 阶段解体则取1,否则取0;W b ijd(k 为021变量,如果到达场列车i 的第j 辆车对应第d 个目的地则取1,否则取0;Hb jd r(k 为021变量,如果驼峰区轨道r 上第j 辆车对应第d 个目的地则取1,否则取0;F b jd(k ,SD b

7、 jd (k ,CD bjd (k 为021变量,分别表示如果编组场、同向出发场、换向出发场第j 辆车对应第d 个目的地则取1,否则取0。3数学模型本文以双向列车编组站为研究对象, 编组站系统包括到达场、驼峰区、编组场、转发场、出发场等子系统。到达场用于临时停靠到达编组站的列车,驼峰区对列车进行解体得到的车辆,编组场根据车辆去向和目的地将车辆重新编组成新的列车,转发场是将编组后的新列车驶向出发场等待出发。本文把上行线和下行线统一看待,根据编组列车的不同去向,将转发场进一步细分为两种:列车继续保持行进方向的同向出发场;列车需要从上(下行方向转换为下(上行方向的换向出发场。中时的定义是车辆在编组站

8、的平均停留时间,衡量了编组站的效率。对编组站系统进行抽象,引入状态转移的思想提出编组站状态转移关系模型。状态转移关系的过程描述如下:对于上行线和下行线的各方向经过编组站的每一列列车分别驶入到达场内停靠,然后判断列车是否需要解体,如果不需要解体则根据列车去向驶入同向出发场或换向出发场待发,如果需要解体则根据每一辆车的去向通过驼峰解体,分别向各自的编组场不同轨道线集结,从而编组成一列新的发往某一个方向的列车,最后转往上行线或下行线的出发场待发。状态转移关系模型考虑了编组站各系统的状态以及各子系统的状态转移关系,是优化模型的基础。第k 阶段时编组站系统的状态和状态转移关系见图1。图1第k 阶段车站系

9、统状态图根据提出的状态转移关系模型生成约束条件,以中时最小为优化的目标函数,建立了编组站列车调度的优化模型。3.1约束条件(1到达场的状态j Q i d D A b 0,1Jij(k W bijd (k =q i ,i =1,n (1式(1表示将第k 阶段到达场列车i 解体成去向和类型不同的车辆,是状态守恒关系。(2驼峰区的状态r RHbjd r (k =i N(1-i (k W bijd (k ,b 0,1,d D A ,j Q i(2L m in q i L m ax Wm inWlj Q i d D A b =0Jij(k Wb ijd (k +Whj Q i d D A b =1Jij

10、(k W bijd(k W m ax,i =1,n(3式(2表示k 阶段驼峰区的车辆是由出发场部分列车分解的得来的。式(3用于判定列车是否需要解体,如果满足则i (k 取1表示不需要解体,否则取0。其中,W l 是一辆空车的重量;Wh是一辆重车的重量。(3编组场的状态F bjd (k +1=r R Hb jd r (k ,b 0,1,d D A ,j Q i(4j Q iFbjd (k +1=j Q iFbjd(k +j Q i r RHb jd r(k ,b 0,1,d D A ,j Q i(5L m in j Q i b 0,1Fbjd(k L m ax ,d D A(6Wm inWlj

11、Q i b =0Fbjd(k +Whj Q i b =1Fbjd (k W m ax,d D A (7式(4表示k 阶段驼峰区的车辆转移成为k +1阶段编组场同类型的车辆;式(5表示k 阶段解体的车辆到达第d 条轨道上,形成新列车的递推关系;式(6和式(7分别表示k 阶段新列车长度和重量限制关系。(4同向出发场的状态d D SSDbjd (k +1=i N d D SWbijd (k i (k +d D SFbjd (k ,b 0,1,j Q i(8式(8表示第k +1阶段同向出发场的列车对应第k 阶段到达场和编组场不需换向的列车。(5换向出发场的状态d D CCDbjd (k +1=i N

12、d D CWbijd (k i (k +d D CFbjd (k ,b 0,1,j Q i(9式(9表示第k +1阶段换向出发场列车是第k 阶段转发场和编组场需要换向的列车。16第7期张林,廖天俊等:基于状态转移的编组站列车调度优化模型(6接续时间与到达时刻的约束t k +1-t k T hi N j Q iJij(k (10t k i N j Q iat i Jij(k (11式(10表示列车的解体过程是连续的;式(11表示列车的到达时刻有先后的次序。(7逻辑约束i N j Q i Jij(k =1(12k K j Q iJij(k =1,i =1,n(13式(12表示一个阶段内只能有一列车

13、进行编组;式(13表示一列车只能编组一次。3.2目标函数m in G =Ti Nqi(14式(14表示优化的目标是一个班次的列车中时即平均中转停留时间最小。其中T 是一个周期从开始到结束时车辆在编组站停留的总时间,可由式(15计算得到。系统从第k 阶段变化到第k +1阶段,车站系统各个场地的状态转化需要一定的时间,包括k 阶段的四项时间变化增量:车辆在到达场停留的时间;驼峰区列车解体成车辆到达编组场的时间;编组场新列车驶向同向出发场的时间;编组场新列车驶向换向出发场的时间。车辆停留总时间的递推关系式为:T k +1-T k=(t k +1-t k i N j Q i d D A b BJij(

14、k W b ijd (k +T h j Q i d D A r R b BHbjd r(k +T z i N j Q i d D S b BWbijd(k i (k +T z j Q i d D S b BF b jd (k +T w i N j Q i d D C b BWbijd (k i (k +T f j Q i d D C b BF b jd (k (153.3编组调度优化模型综上所述,得到基于状态转移的双向编组站列车调度优化模型为:m in G =Ti Nqis .t .j Q i d D A b 0,1Jij(k W b ijd (k =q i ,i =1,nr R Hbjd r

15、(k =i N(1-i (k W bijd (k ,b 0,1,d D A ,j Q iF bjd (k +1=r RHb jd r (k ,b 0,1,d D A ,j Q ij Q iFbjd (k +1=j Q i Fb jd (k +j Q i r RHbjd r (k ,b 0,1,d D A ,j Q iL m in j Q i b 0,1Fb jd(k L m ax ,d D A Wm inWlj Q i b =0Fbjd(k +Whj Q i b =1Fbjd (k Wm ax,d D Ad D SSD bjd (k +1=i N d D SWbijd (k i (k +d D

16、 SFbjd (k ,b 0,1,j Q id D CCDb jd(k +1=i N d D CWbijd (k i (k +d D CFbjd (k ,b 0,1,j Q it k +1-t k T hi N j Q i Jij(k t k i N j Q iat iJij(k i N j Q iJij(k =1k K j Q iJij(k =1,i =1,n其中,k K .4算例4.1数据和求解结果以郑州北站为例,采用双向纵列式三级六场机械化驼峰编组站站型,利用上述模型确定列车调度的编组计划。模型参数为:N =100列,R =2条,D A =29条,D C =13条,D S =16条,L

17、m in =40辆,L m ax =70辆,Wm in=3000吨,Wm ax=4800吨,T w =15分,T z =20分,T h =10分,T f =5分,W h=80吨,W l =20吨。编组车流去向代码和开始时编组站残存的各去向的车流流量见表1;编组计划期间6:0018:00到达列车的部分信息见表2。模型的求解结果是计划期间的中时为147分钟,经过编组后新列车的出发信息见表3。26系统工程2009年表1编组车流去向代码和揩始时编组站残存的各去向的车流流量衔接方向编组车流去向代码 车流量(辆向东方向E1 19,E2 14,E3 14,E4以南 33,E4以北 9,E5以远 13,E5以

18、近 5,E6 8,E7 9,E8 7向南方向S1 17,S2以远 13,S3以西及以远 14,S3与S4间 6,S4与S5间 14,S6 17向西方向W1 41,W2 41,W3 30,W4 22,W5 25,W6以远 25,W6以近 31,W7 16向北方向N1 35,N2 35,N2与N3间 30,N3与N4间 32,N5 22表2编组计划期间到达列车信息车次编号到达时刻方向车辆数列车编组内容S0016:20上行59W2 59S0036:35上行62W1 24,W2 1,W3 2,W4 7,W5 16,W6以远 2,W6以近 3,W7 1,N2 2, N2与N3间 4S0056:52上行5

19、9E2 2,E3 1,E4以南 1,S2以远 10,S3以西及以远 1,W2 6,W3 24,W4 8, W5 1S0077:10上行54W1 3,W2 10,W4 7,W5 8,W6以远 2,W6以近 12,W7 2,N2与N3间 10 S0097:40上行56W2 5,N1 22,N2 19,N2与N3间 2,N3与N4间 8X0026:05下行61W2 61X0046:15下行53E2 10,E4以南 43X0066:30下行57E2 3,E6 3,E7 8,S1 14,S3以西及以远 1,W2 1,W4 3,W5 8,N1 1X0086:45下行50E1 4,E3 1,E4以南 15,

20、E4以北 10,S2以远 7,N1 2,N2 2,N3与N4间 9, N5 1X0106:55下行44E1 7,E4以南 4,W1 1,W2 24,W3 4,W4 4表3编组出发列车信息车次编号出发时刻方向车辆数编组内容车次编号出发时刻方向车辆数编组内容X0018:31下行69W2 69X0038:46下行62E4以南 44,E4以北18S0028:57上行68W2 68X0059:18下行49S3以西及以远 16,S3与S4间 33 S0049:33上行57S2 以远 65X0079:39下行65W5 57X0099:50下行61N1 61S0069:58上行63N2 41,N2与N3间 2

21、0X001110:11下行59W1 59S00810:22上行67E2 674.2灵敏度分析提高“瓶颈”硬件设施能力能提高编组能力,考虑2个因素:到达场到驼峰区的牵引轨道条数;编组场到出发场的牵引时间。保持其它条件不变,分别改变这2个因素,形成对照“实验”,进行灵敏度分析,驼峰区轨道数量因素的影响见表4,牵引时间因素的影响见表5。表4驼峰区轨道数量对中时的影响驼峰区轨道数(条牵引时间(分钟中时(分钟 15393251474510636第7期张林,廖天俊等:基于状态转移的编组站列车调度优化模型从表中可以看出,在其他因素不变的时,当驼峰区轨道减少到1条,中时增加到393分钟,当驼峰区轨道增加到4条

22、,中时减少到106分钟。表5牵引时间对中时的影响驼峰区轨道数(条牵引时间(分钟中时(分钟2311325147210284从表中可以看出,在其他因素不变的时,当牵引时间缩短到3分钟,中时减少到113分钟,当牵引时间增加到10分钟,中时增加到284分钟。综合来看,驼峰区轨道因素对中时影响最为明显,在实际中应该努力提高相应的人员和设施的效率,尽量减少这个“瓶颈”的限制,考虑适当增加驼峰区轨道的数量。5结束语本文提出的基于状态转移的编组优化模型,通过以中时最小为目标,减少列车的等待时间,从而解决了列车调度优化问题,提高了铁路系统效率。基于状态转移的建模思想具有通用性,适用于各种编组站站型。该调度优化模

23、型的解反应了编组站各子系统的状态,有利用对编组作业的实时控制,对编组站具有重要的实用价值。我们下一步研究工作将考虑满轴发车等兼顾多个目标建立多目标规划模型,解决更加复杂的编组调度优化问题。参考文献:1李致中等.铁道运输管理的数学模型及算法M.武汉:华中理工大学出版社,1995.2林柏梁,朱松年.优化编组计划的非线性021规划模型及模拟退火算法J.铁道学报,1999,21(2:31 66.3A r m acost A.M odeling railroad ter m inal operati onssupporting realti m e network p lanning and contr

24、olD.Cam bridge,1995.4M artinelli D R,T eng H.Op ti m izati on of rail w ayoperati ons using neural network sJ.T rans portati onR esearch,1996,4(1:3349.5R avindra K A,K rishna C J,L iu J.Solving real2liferailroad bl ock ing p roble m sJ.Infor m s,2007,37(5:404419.6李映红,吴世贵,彭其渊.货物列车编组计划网络模型的建立及算法J.西南交通

25、大学学报,2002,37(1:6871.7查伟雄,秦作睿.路网上列车编组计划的有利去向模型及其网络流算法J.铁道学报,1998,20(2:12 19.8许红等.技术站单组列车编组方案模型与计算方法的研究J.铁道学报,2006,28(3:1217.9梁栋,林柏梁.技术站分组列车编组计划的优化理论及模型研究J.铁道学报,2006,28(3:15. 10牛惠民.双向编组站列车调度调整的优化模型及算法J.中国铁道科学,2007,28(6:102107.An Opti m i za ti on M odel for Tra i n Schedul i n g of M arsha ll i n g St a ti onBa sed on the St a te Tran sfor ma ti onZHAN G L in1,L I A O T ian2jun1,L I U Ying2(1.School of Infor m ati on Syste m s and M anage m ent,N ati onalU niversity of D efense T echno