田志强,张小炳,郭倩倩
(西南交通大学 交通运输学院,四川 成都 610031)
在现阶段我国铁路列车运行图的编制工作中,货物列车运行线的铺画一般都是在旅客列车运行线编制完成后进行的,其始发终到时刻、区段内会让和待避旅客列车的情况、区段旅行时间等都受到旅客列车框架的影响。当直通货物列车运行线从始发站直接向终到站铺画时,不同的始发点选择将得到不同的运行线方案,且铺画过程中可能因为旅客列车框架的影响而导致货物列车在沿途车站停站时间过长。因此,按照区段铺画货物列车运行线,再根据需要将各区段的运行线接续为直通或直达货物列车运行线是一种较为常用的方法,且应用该方法时区段货物列车运行线的铺画能够在计算机编图软件的辅助下以较快的速度和较少的人机交互得到合理的方案[1]。由于货物列车运行线的编制基本上都是各铁路局各自进行的,因此从全路的角度来看,需要确定货物列车运行线接续方案的车站除各铁路局管内的技术站外,还包括相邻两铁路局的分界口车站。
直通货物列车运行线接续问题的目标一般是在满足各项约束条件的基础上使列车在技术站(分界口车站)的停留时间最短,同时在一定程度上保证各技术站上始发列车与直通列车的分布相对均衡,为车站工作创造良好的条件[2]。本文主要从接续时间的角度出发,对直通货物列车运行线在技术站接续方案的选择方法进行分析,以期为提高列车运行图编制水平、优化直通货物列车接续方案提供相应的理论与方法支持。
在文献[2]和[3]中,均是假定技术站已经给定,直通货物列车的到达时刻已知,因此其接续方案选择的实质就是从若干个货物列车出发时刻中选择相应的运行线与之匹配,使得所有直通货物列车在该技术站的总停留时间最短。若直通列车沿途经过多个技术站,则只需要从始发站开始,重复应用上述过程即可。
文献[2]和[3]中建立的模型(即模型1)可描述如下:
式中:Z 表示直通货物列车在技术站的总停留时间;nZ表示在技术站需要接续的直通列车的数目;nF表示从该技术站发出的运行线数目;xij为0-1变量,表示到达运行线i是否接续出发运行线 j,当两者接续时取1否则取0;tij为到达运行线i与出发运行线 j 相接续的时间;Fj表示该站第 j 条出发运行线的出发时刻;Di表示到达该站的第i条运行线的到达时刻;T技为直通货物列车在技术站的技术作业时间标准。
原模型中式⑷不能包含所有情况,考虑到列车到、发时刻是在一天之内,因此在一种较为极端的情况下(如到达列车时刻为23:59,出发列车时刻为0:05,技术作业时间标准为30 min时,计算得出的接续时间tij为6 min),该式计算出的接续时间并不能满足技术作业时间标准。因此本文将式⑷修改为:
从已有方法的应用过程可以看出,由于在每一个技术站选择出发运行线与到达的直通列车运行线相匹配时,没有考虑后续技术站运行线的接续情况,因此并不能保证所得出的接续方案能够使所有直通列车在各个技术站的接续时间总和最小,甚至不能保证该接续方案是各技术站所有到、发列车运行线间接续时间最短的方案。为此,本文对直通货物列车运行线在技术站的接续问题进行如下扩展(下文中所述的原方法指文献[2]和[3]中采用的方法)。
原方法无论对于上行列车还是下行列车,均是假设直通列车到达技术站的时刻确定、从技术站出发的时刻未定进行讨论。但实际上,以技术站直通车出发运行线确定而为其选择到达运行线也是一种可行的方法。其优化模型与模型1相差不大,在此不再赘述。
在某些情况下,由于受到某技术站设备、能力等条件的制约,需要优先考虑直通列车在该站的接续方案。因此,单纯应用上述接续方法无法解决该问题,此时需要首先在能力紧张的技术站从所有到达及出发列车集合中匹配出所需数量的直通列车运行线,使其接续方案满足直通车在该站接续时间最短。当该站的接续方案指定后,可向其终到方向和始发方向分别采用原方法及扩展1方法选择直通列车接续方案。
对于优先考虑的车站,其接续方案模型 2为:
式中:nD表示到达该技术站的运行线数目。
当需要优先考虑技术站的接续方案确定后,对该站以后的技术站采用原方法逐步向后确定接续关系,对该站以前的技术站采用扩展方法1逐步向前确定接续关系。
原方法及扩展1、2都是从局部出发设计直通列车在技术站的接续方案,并不能保证得到的方案在所有技术站的总接续时间最短。因此,若要得出在所有技术站接续时间最短的接续方案,就需要同时考虑所有技术站的接续情况。
在这种情况下,所有车站的接续情况被同时考虑,设所有直通列车共经过m个技术站(包含始发、终到站),由于在始发站只有始发运行线,在终到站只有终到运行线,从而不存在接续方案的选择,因此只需要考虑技术站2至技术站m-1的接续情况,其接续方案的优化模型3为:
其中:k为当前考虑的车站编号。
扩展方法3虽然以直通货物列车在所有技术站总的接续时间最小为目标进行优化,但由于各个区段内不同货物列车运行线的实际铺画情况不同,一般也具有不同的旅行时间。因此,若仅考虑直通货物列车在技术站的接续时间,则不能保证所得方案的总旅行时间最短。
当以直通货物列车旅行时间最短为目标时,上述的扩展方法仍不能满足需要。此时可以将货物列车在区段内的旅行时间也计入考虑范围,即同时考虑运行线的旅行时间及其在技术站的接续时间。优化模型4如下:
针对上述提出的各个扩展问题,讨论其相应的求解算法:
(1)扩展1。该问题实质上是原问题的逆向过程,因此同样可以采用最小费用最大流算法求解,由于始发站和终到站不需要考虑接续方案,则当车站总数为 m 时算法应用的次数为(m-2)。
(2)扩展2。该问题首先考虑中间某技术站的接续方案,由于到达该技术站的运行线数和从该技术站出发的运行线数一般都大于或等于直通货物列车的数量,因此不能再采用最小费用最大流算法求解,而应采用最小费用流算法求解,求解时流值即为直通货物列车的运行线数量m直。在需要优先考虑的技术站接续方案确定后,其余技术站采用最小费用最大流算法求解即可。因此总的算法应用次数为1次最小费用流算法和(m-3)次最小费用最大流算法。
(3)扩展3。该问题同时考虑直通列车在所有技术站的接续方案,采用1次最小费用流算法求解即可。
(4)扩展4。该问题与扩展3相比,只是增加了各相邻技术站之间各条货物列车运行线的旅行时间,在网络中则只是增加了区段内的运行线,因此也只需要采用1次最小费用流算法求解。
直观上看,上述4个扩展问题分别应用了最小费用最大流和最小费用流两种算法求解,但实质上,无论是采用最小费用最大流算法还是采用最小费用流算法,其流值均为m直,因此上述所有问题都可以归结为求流值为m直的最小费用流[4]。
为了说明本文所提出的各扩展方法在制定直通货物列车接续方案时的应用情况,本文设计了相关的数据进行计算。
设有如图1所示的运行区段需要确定直通货物列车在各技术站的接续方案。该图中共包含4个技术站,3个运行区段,在每个技术站到、发的货物列车运行线均为10条,列车在各个区段的发、到时刻及旅行时间如表1所示。所有区段内运行线编号都按照其始发时刻从18:00开始以升序排列,假设经过所有区段的直通货物列车为4列,在各技术站的技术作业时间标准均为30 min,现分别根据原方法及各扩展方法确定其在各技术站的接续方案。
图1 直通货物列车运行区段示意图
采用表1中的数据,首先按照扩展3方法及扩展4方法计算接续方案。然后采用扩展3方法对应区段1的4条运行线为B站的到达运行线,应用原方法向后(始发站—终到站方向)确定接续方案。再采用扩展3方法对应区段3的4条运行线为C站的出发运行线,应用扩展1方法向前(终到站—始发站方向)确定接续方案。最后应用扩展2方法分别以B站和C站为优先考虑对象计算接续方案,最终的接续方案及相关方案的接续和旅行时间统计如表2所示。
从最终的计算结果可以看出,对于同样的区段运行线分布,当采用不同方法求解时得出的接续方案可能是不同的。原方法及扩展1方法虽然应用简便,但从表2中可以看出,这两种方法并不能保证得到的接续方案总接续时间最短。扩展3及扩展4方法计算稍显繁琐,但能够确保得出相应的最优接续方案,如本文算例中的最小接续时间和为679 min,所有直通货物列车的最小总旅行时间和为4 217 min。扩展方法2仅适用于中间某技术站能力紧张的情况,本文分别以B站和C站作为能力紧张的车站计算了相应的接续方案,不难看出,虽然对于B站或C站而言,该方法能够得到最短的接续时间,但是该方法不能缩短而是显著增加了整个运行区段的接续时间。
表1 各区段列车到发时刻及旅行时间
表2 各方法接续方案
本文研究了铁路直通货物列车运行线在技术站的接续问题,分析了多种情况下的不同接续方法并建立了相应模型,在对各模型分析的基础上提出了采用最小费用流算法进行统一求解的思路。设计算例的结果表明,针对不同的优化目标及求解方法,其接续方案之间是存在差异的,且用本文提出的相关方法能够得出最优的接续方案。
文中设计的算例没有直接涉及铁路局分界口车站的接续情况,但实际上,对于分界口车站,只需要将技术作业时间标准改为合理的接续值即可。当各技术站技术作业时间标准不一致时,也只需要重新计算各车站对应的接续时间矩阵。另外,本文仅从接续时间的角度出发研究了接续方案的选择方法,当对直通货物列车的始发终到时刻有特殊要求时,其接续方案的优化仍需深入研究。
[1]倪少权,吕红霞,杨明伦. 全路列车运行图编制系统设计的研究[J].西南交通大学学报,2003,38(3):332-335.
[2]朱建梅. 基于实用的技术站直通列车接续方案计算方法研究[J]. 西南交通大学学报,1999,34(3):365-368.
[3]彭其渊,闫海峰,石子明. 计算机编制列车运行图的理论与方法[M]. 成都:西南交通大学出版社,2004.
[4]谢 政,李建平. 网络算法与复杂性理论[M]. 长沙:国防科技大学出版社,1995.