专业文章|铁路货运最短车流径路算法与实现

注：本文为期刊公众号简版，完整版已发群内自取。

段嘉伟，广州东华职业学院

陈秋文，广州东华职业学院

孙佩，西安交通工程学院

0 引言

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

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

1 路网数学描述

根据我国《铁路技术管理规程》规定，路网中衔接3个及其以上方向的车站、技术站称为节点站，办理少量客货运业务或供列车会让及越行的车站皆为中间站，线路两端尽头处设置的车站皆为尽头站。节点站采用G=（V，E，W）表示，V是路网中节点站编号在所建网络中节点的集合，E为网络中边的集合，E=｛eij|路网中节点站i与j相连｝，W为网络中边的长度。我国铁路网共有中间站5600多个，中间站车站位置由该车站节点编号与两端节点站对应节点编号之间的里程所确定，支线上的尽头站位置由该车站节点编号距一端节点站节点编号之间的里程确定。综上所述，将节点站的节点编号编制形成路网文件，以表述两节点站之间的里程。路网上节点站、中间站、尽头站的车站名用下述数学描述形成站名文件，利用路网文件搭建铁路货运路网，借助站名文件搜索路网文件中节点编号对应的车站名，从而建立整个铁路计算机路网。

1.1 节点站路网文件 

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

步骤1：对路网货运节点站进行节点编号（见表1）。

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

1.2 站名文件建立 

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

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

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

2 算法描述

2.1 最短路径算法比选 

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

2.2 Dijkstr算法程序步骤

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

2.3 路网拆分与重构

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

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

由于德惠—地中新建线路的加入，原路网文件与站名文件需进行部分更新。路网文件中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算法程序得到最短车流径路。因此，从西安西站发一批货物至兰州北站，经由该最短车流径路，走形公里数为686km。

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

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

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

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

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

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

4 路网数据维护

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

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

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

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

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

5 结束语

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

来源：《中国铁路》编辑部