直通货物列车运行线优化选择问题的网络图研究

余后伦，笪翔

(1.中国铁路设计集团有限公司,天津300251；2.西南交通大学 交通运输与物流学院,四川成都 610031)

0 引言

近年来铁路旅客运输稳步发展，而铁路货物运输因货物到达时间不能得到有效保证、货运周期长而饱受诟病[1-2]。列车运行图作为铁路行车组织中的核心技术文件之一，是联系铁路内部与社会外界的纽带，因此理论上可以通过优化货物列车运行图改善铁路货物运输现状[3-5]。在编制货物列车运行图时，一般遵循先直通后管内的原则，即优先安排直通货物列车的运行线，因此，直通货物列车运行线的选择对后续管内货物列车的运行线安排以及整个运行图的编制质量能产生显著影响[6-7]。一般而言，直通货物列车在技术站的中转停留时间是影响列车运行线优化选择的重要因素，因此压缩直通货物列车在技术站的中转停留时间是优化货物列车运行图的一个重要方向[8-9]。

直通货物列车从始发站到终到站的走行过程中在沿途技术站只进行无改编中转作业，不用考虑沿途技术站的货车集结时间。货车集结时间是指从直通货物列车到达技术站时起，进行无改编中转的技术作业后至列车出发时为止的列车在站停留时间[10-11]。因此在不影响其他列车运行线调整的情况下可通过压缩直通货物列车在沿途技术站的接续时间来使货物运到时间尽可能缩短，以此为原则优化选择直通货物列车运行线，可以确保运行图满足动态运输市场需求并顺利实施，同时保证货物运到期限要求[12]。

1 网络图模型的建立

在一个直线区段中，已知有e列无改编直通货物列车需要沿下行方向通过h个技术站，一般情况下，直通货物列车在任一技术站的停留时间不超过2 d，列车在沿途区段可以选择的运行线数量是相等的，直通货物列车等级相同(运行速度一样)，车站能力(工作人员和到发线等设备设施的数量)充足，任一列直通列车在某个技术站的出发时刻一旦确定，则它在下一个技术站的到达时刻也就已经确定(基本列车运行图中已经铺画出了各技术站之间的运行线)[13]。

图1 基本列车运行图中的运行线

假设在基本列车运行图中，任一技术站w(w为当前技术站编号且w=1,2,……，h)共有p个到达运行线(到达时刻对应的运行线)和q(p与q相等)个出发运行线(出发时刻对应的运行线)供列车选择(如图1所示)[14]。

(1)

式(1)表示对任一列直通列车在技术站的停留时间不得少于该技术站的标准接续时间，当出发运行线与到达运行线对应的时刻相减所得的时间小于标准接续时间，若依然保持到达和出发运行线不变，则这列直通列车就要在该站多停留1 d[17-18]。

直通货物列车运行线优化选择的问题实际就是在各个技术站挑选与直通列车数量相匹配且满足标准接续时间的列车到达运行线和出发运行线，使直通列车在沿途所有技术站进行接续时的总停站时间最小[19-20]。根据上述理论可构建对应的网络图如图2所示。

图2 直通列车运行线优化选择容量费用网络图

2 算法求解

该网络图模型是一个典型的流值一定的容量费用网络，当e=1时，问题变为求解网络图从源点到汇点最短路问题。受此启发，可结合实际问题考虑设计这样一种算法思路，先根据运筹学中经典的Dijkstra算法在网络图中算出一个从源点到汇点的最短路，将其记下并保存，然后将所得的最短路径在原网络图上删掉(或者屏蔽)，再开始在剩下的网络图上进行下一个从源点到汇点的最短路径的计算，这样每得到一个最短路，就将其记录下来后删掉或者屏蔽，最后一定能得到e个这样的路径，借鉴最小费用流问题中的连续最短路算法理论可知，这e个路径分别对应e列车的最优运行线选择方案。因此，算法设计步骤可总结如下：

1)首先将各列车时刻转化为相应的时间[0,1440]；

3)根据Dijkstra算法求解现有的网络图中从源点vs到汇点vt的最短路径并将其保存；

4)把3)所得最短路径对应的弧在网络图上进行屏蔽，得到新的网络图；

5)返回到3)并重复3)、4)直至所保存的最短路径数量与直通列车数e相等，根据得到的这e条路径即可按照网络图中各点对应关系得到这e列直通列车的运行线最优选择方案。

上述算法可在MATLAB软件中进行编程实现以解决实际问题。

3 算例

3.1 背景资料

图3 区段地理位置情况

已知某个直线区段在路网的情况如图3所示，A—E分别表示5个技术站(共4个区段)，车次号分别为24001、24003、24005、24007的4列直通货物列车需从A站无改编运行到E站，已知每个站的无改编中转列车的标准接续时间均为30 min，4列直通货物列车速度等级相同，各区段运行线的信息情况如表1所示。

表1 各区段列车运行线信息

3.2 算例求解

根据网络图模型的算法步骤在MATLAB软件中进行编程实现，可得到路径(各区间的运行线)结果如表2所示。根据各运行区段的运行线优选方案可得列车时刻表如表3所示，此时这4列直通货物列车在技术站的接续总时间最短，根据MATLAB软件求解结果可知这4列车的最小接续总时间为1 034 min。

4 结语

通过对直线区段的直通货物列车运行线优化选择的问题进行研究，建立了以直通列车在沿途技术站的接续总时间最短为目标的网络图模型，并通过实际算例进行了模型验证，得出对直通货物列车运行线进行优化选择的一种可行方法，旨在为货物列车运行图编制和优化提供参考，对铁路货物运输组织具有一定的参考。

表2运行区段运行线优选路径

列车车次运行线AB段BC段CD段DE段24001771022400322692400556912400710157

表3 列车时刻表