铁路货运最短车流径路算法与实现

段嘉伟， 陈秋文， 孙佩

（1.广州东华职业学院 管理学院，广东 广州 510000；2.西安交通工程学院 交通运输学院，陕西 西安 710300）

0 引言

我国从上世纪90 年代开始运用优化算法研究车流径路问题，铁路车流径路选取对铁路行车运输组织十分重要，也是铁路运输部门高效衔接组织生产的有利基础。车流径路问题贯穿于列车运行图、货物列车运输计划、车站作业阶段计划等运输计划编制过程中，为充分利用路网有限资源，应合理有效选取车流径路［1］。最短车流径路算法目前比较成熟，其中赵娟［2］根据车流组织模式对铁路车流径路进行优化，建立线性0-1 规划模型；高明瑶等［3］以车流总走行费用最小为目标函数，构建基于改进点-弧模型的铁路网车辆径路优化模型，采用Lingo 软件求解；温旭红［4］以多商品网络流理论为基础，构建铁路网车流分配与树状径路综合问题的混合整数规划模型。

综上分析，既有文献对铁路最短车流径路的研究，多聚焦于部分路网中指定两站的最短车流径路求解，求解结果具有一定局限性，且路网简单导致算法优势体现不明显。因此编制全路任意发到站的最短车流径路算法具有一定实践意义。通过对既有最短径路算法进行比较，确定采用Dijkstra 算法来实现铁路货运节点站间最短车流径路、非节点站间最短车流径路、支线上尽头站间最短车流径路、多重站点最短车流径路，并提供路网数据维护功能。

1 路网数学描述

根据我国《铁路技术管理规程》规定，路网中衔接3个及其以上方向的车站、技术站称为节点站，办理少量客货运业务或供列车会让及越行的车站皆为中间站，线路两端尽头处设置的车站皆为尽头站。节点站采用G=（V，E，W）表示，V是路网中节点站编号在所建网络中节点的集合，E为网络中边的集合，E=｛eij|路网中节点站i与j相连｝，W为网络中边的长度［5］。我国铁路网共有中间站5 600 多个，中间站车站位置由该车站节点编号与两端节点站对应节点编号之间的里程所确定，支线上的尽头站位置由该车站节点编号距一端节点站节点编号之间的里程确定。

综上所述，将节点站的节点编号编制形成路网文件，以表述两节点站之间的里程。路网上节点站、中间站、尽头站的车站名用下述数学描述形成站名文件，利用路网文件搭建铁路货运路网，借助站名文件搜索路网文件中节点编号对应的车站名，从而建立整个铁路计算机路网。

1.1 节点站路网文件

以“2020 全国铁路货运营业站示意图”为基本路网结构，该铁路网结构图G是1个连通图，顶点数量繁多，大部分的顶点度数相对来说比较小，以二度顶点数目居多［6］。由于繁多的顶点数在利用计算机求解最短车流径路时所消耗的时间过长，因此采用节点站作为路网骨架，由此可见节点站在路网中占据重要地位。选取商丘—南京东的部分路网（见图1）并对节点站进行节点编号，形成路网文件步骤如下：

图1 商丘—南京东部分路网图

步骤1：对路网货运节点站进行节点编号（见表1）。步骤2：对节点站进行命名（见表2），所有节点站通过节点编号命名方法形成路网文件（见图2）。

图2 路网文件生成程序截图

表1 货运站节点编号

表2 路网文件

1.2 站名文件建立

在路网中，站名文件是通过赋予节点站、尽头站特殊站名命名规则，并根据中间站基于距该条线路两端节点站的距离来确定并建立。站名文件建立见表3。

表3 站名文件建立

根据站点在路网中的所处位置以及对应的站点命名方式对所有站点进行命名，形成站名文件，站名文件生成程序截图见图3。

图3 站名文件生成程序截图

基于上述2种文件，通过输入输出流读文件的方式建立路网，如建立从商丘—南京东的路网图（见图4）。

图4 商丘—南京东路网图

2 算法描述

2.1 最短路径算法比选

目前简单路网中常用的2 类算法是Dijkstra 和Floyd算法（见表4），其中Floyd 算法在求解最短车流径路时，需构造数据矩阵，计算复杂，不适用于复杂路网计算；Dijkstra 较Floyd 算法求解时间快，且精确度高。我国铁路网具有节点站基数大、路网构造复杂且路权没有负值等特点，计算复杂度较高，因此宜选择Dijkstra 算法用于求解全路任意两货运站之间的最短车流径路。

表4 算法比选

2.2 Dijkstr算法程序步骤

Dijkstra算法基本思想是：设定2个标号，一个P标号，一个T标号，P标号为点标号，是永久性标号，P（Vi）表示起点到该点的最短路权值。T标号为边标号，是临时性标号，初始定义一个最大邻接标号值∞，表示起点到该点的路权为∞，最终目标是将边∞不断缩小，最终达到所有的T标号改为P标号［7］。

数学描述如下：

用Wij表示Vi-Vj之间的路权，两站相邻，路权为实际里程，两点不相邻时，路权Wij=∞，步骤如下：

步骤1：给起点V1标上永久性标号，记为P（V1）=0，其余节点初始化为∞，记为T（Vj）=∞，若起点与该点直接相邻，T（Vj）=Wij，否则等于∞。

步骤2：所有T标号中选择最小的，更新为P标号，判断表达式T（Vj）=min｛T（Vj），T（Vj）+Wij｝，更新T标号。

步骤3：在所有的T标号中选择最小的T标号作为P标号继续勘测，直到所有的标号全部为P标号。

步骤4：由最终得到的T标号点起，从后往前搜索最短车流径路。

2.3 路网拆分与重构

在2 条干线之间新建1 条线路，属于路网中间站之间的1条铁路新线，对原有路网进行拆分和重构，将新建线路融入既有铁路路网中，形成新路网。例如：现需在路网中的牡丹江—下城子、牡丹江—林口2条线路之间新建1条德惠—地中的铁路线路（见图5）。

图5 新建线路网络图

从图5可知，路网文件中格式为：节点编号19→牡丹江，节点编号20→下城子，节点编号31→林口。牡丹江距离下城子98 km，牡丹江距离林口110 km。假设从施工队可知，德惠距离牡丹江48 km，距离下城子50 km。地中距离牡丹江50 km，距离林口60 km。因为路网中最大节点编号为2400，因此德惠与地中2节点站的编号分别为2401、2402。德惠—地中之间有1个中间站为天中，天中距离德惠70 km，天中距离地中60 km。

由于德惠—地中新建线路的加入，原路网文件与站名文件需进行部分更新。路网文件中19→20→98 与19→20→110这2条线路数据删除，新增4条线路，19→2401→48 与2401→30→50， 19→2402→50 与2402→31→60。站名文件增加1 个车站的命名为2401→70→2402→60天中。

3 算法实现

3.1 节点站间最短车流径路求解

铁路网中，选取发站西安西，到站兰州北，调用Dijkstr 算法程序得到最短车流径路（见图6）。因此，从西安西站发一批货物至兰州北站，经由该最短车流径路，走形公里数为686 km。

图6 西安西—兰州北最短车流径路

3.2 非节点站间最短车流径路求解

通过对所建网络得到的数据文件进行处理，可得路网中共有站点6 241 个，其中节点站673 个（中间站与尽头站共5 568个），节点站最大节点编号为2400。

3.2.1 不同区间中间站最短车流径路求解

最短车流径路算法程序中，路网节点站因在路网文件中具有其对应的节点编号，因此可以得到任意两节点站之间的最短车流径路。但如果中间站没有节点编号，在求不同区段内两中间站之间的最短车流径路时，则需要将中间站添至路网，中间站到路网两端节点站的里程与站名文件中该站节点编号至两端节点编号的里程等价。

假设需要求解黄土店—安定的最短车流径路，通过站名文件搜索可知，黄土店是位于沙河—双桥两节点站之间车流径路上的中间站；安定是位于黄村—汉沟镇两节点站之间车流径路上的中间站。求解思路是将黄土店与安定变为节点站，节点编号分别为2407、2408（见图7）。通过调用Dijkstr 算法程序，黄土店—安定最短车流径路在中间站被添加至路网前后的最短车流径路分别见图8（a）、图8（b）。

图7 不同区间中间站未添至路网前的最短车流径路

图8 最短车流径路生成程序截图

3.2.2 同一区间内中间站求解最短车流径路

通过搜索站名文件发现水治与安阳西属于石涧—安阳两节点站之间的中间站，在站名文件中，两中间站与路网中两节点站的站点信息格式为：899→900→25→石涧至安阳；899→7→900→18→水冶；899→18→900→7→安阳西。水治—安阳西最短车流径路见图9，水治—安阳西最短车流径路里程为11 km。

图9 水治—安阳西最短车流径路

3.3 支线上尽头站间最短车流径路

尽头站点路网见图10，在站名文件中对图10 中车站名进行检索可知，该路网中所有站点归中国铁路武汉局集团有限公司管辖。胡家营、厉山、西斋在站名文件中为节点站，部营、丹江、宜昌在站名文件中为尽头站。其中，丹江表示格式为“834 46 -1 0”，含义是丹江距834 号节点站老河口东46 km，属于胡家营、厉山两节点站之间干线上的一条支线。宜昌车站表示格式为“844 37 -1 0”，含义是宜昌距844 号节点站鸦鹊岭37 km，属于荆门、西斋两节点站之间干线上的一条支线。通过调用Dijkstr 算法程序，得到丹江—宜昌两尽头站间最短车流径路和最短里程（见图11）。

图11 尽头站最短车流径路

3.4 多重站点最短车流径路求解

通过站名文件发现某些货运站点在路网中重复出现，比如三民村货运站。在图12 中，从户县发一批货物至三民村或者从咸阳发一批货物至三民村，确定最短径路为走行径路的方法为：新建一个三民村1 节点站，节点编号2405，将图中2 个三民村与三民村1 相连，里程设置为0，此时便可保证从咸阳或者户县发一批货物至三民村，走行径路为最短径路，经由的三民村是最短径路上的三民村，生成程序截图见图13、图14。

图12 多重站点搭建最短径路

图13 咸阳—三民村1最短路径生成程序截图

图14 户县—三民村1最短径路生成程序截图

4 路网数据维护

“2020全国铁路货运营业站示意图”是一个动态网络图，随着路网规模的不断扩大，数据文件也随之不断更新。例如：遂渝线上的遂宁—北碚新线（见图15）是后期投入所建，数据文件中并没有该条线路信息。

图15 遂宁—北碚新线

将该条线路作为添加对象添加至数据文件中，其他新建线路添加方法相同，添加思路如下：

（1）通过对现有中国铁路成都局集团有限公司路网及原有站名文件进行检查发现，遂渝线上遂宁东接蓬溪中间站，西接遂宁西中间站；北碚北接磨心坡，南接团结村；遂宁—北碚之间所有的站点在站名文件中均无记录，因此将遂宁—北碚线作为新线加入路网文件与站名文件中。

（2）路网文件标注方法：新增1条线路，起点为遂宁，节点编号为2401，终点为北碚，节点编号为2402。路网文件标注格式为：“2401 2402 151”，新建线路站名文件标注见表5。

表5 新建线路站名文件标注

（3）在路网文件与站名文件中完成新线标注，运行最短车流径路算法程序，得到最短里程151 km，经由径路为：遂宁→遂宁南→三星→潼南→下太和→渭沱→合川→石子山→北碚（见图16）。

图16 新加线路生成最短径路程序截图

5 结束语

通过介绍路网中节点站、中间站、尽头站在数据文件中的命名方法，在计算机内建立铁路货运路网，应用Dijkstr 算法编制铁路货运最短车流径路算法程序，分析了多种情况下的发站、到站最短车流径路求解思路。但仅分析了铁路货运最短车流径路，而没有考虑铁路货运最短车流径路是否满足超限货物运输需求。得到的最短车流径路如果加入货车在沿途技术站的解编时间，列车是否按照求得的最短车流径路继续走行等问题，还需进一步开展相关研究。