基于Dijkstra算法铁路运输径路的研究

张 锐，邓桂星 ，李世春 ，金福才

（1.兰州铁路局集团有限公司 信息处，兰州 730000；2.中国铁道科学研究院集团有限公司 电子计算技术研究所，北京 100081）

近年来大规模铁路建设，铁路网规模快速扩大，路网结构不断优化，运输能力有了显著提升，如何利用好路网资源，使铁路运力资源的配置更加符合市场需求，是我国铁路走向市场过程中需要深入研究的一个重大课题。铁路货物运输径路的制定是提升路网整体通过能力的重要技术手段。高效率的铁路货物运输径路计算对于支撑货物运到时限用时计算、货物及列车运行轨迹准确追踪、铁路运输效益评价都具有重要意义。目前，我国铁路在用的径路系统[1]，已经解决了由于路网复杂性和运输方式特殊性而产生的技术难题。但是，随着铁路货物运输业务改革的深化，径路系统在智能化程度、运算效率和平台扩展上都需要进一步提升。本文从数据结构、图论和业务逻辑的角度出发，重点解决当前存在的问题。

1 铁路路网数据结构的建立

路网数据结构是径路系统的骨骼，直接关系到径路运算效率的高低和存储空间的大小。本文采用邻接表的方式存储路网结构[2]，在这种存储方式中，对路网中每一个节点建立一个链表，在路网中可以称之为节点的车站，从图论的角度上讲，就是度＞2的节点，我们将度＞2的车站、铁路局分界站、线路属性临界站和编组站均视为路网节点，大约有1 200个节点。空间复杂度为O（n^m）。

2 最短径路算法的实现

铁路最短径路算法一直是铁路各科研院校的重点课题，也是铁路运输径路判定的基础。Dijkstra（迪杰斯特拉）最短径路算法是由荷兰计算机科学家迪杰斯特拉于1959年提出的，是从一个顶点到其余各顶点的最短径路算法，解决的是有向图中最短径路问题。Dijkstra（迪杰斯特拉）算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止[2]。

2.1 经典Dijkstra算法

Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第1组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 ,就将该终点加入到集合S中，直到全部顶点都加入到S中，算法就结束了）。第2组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第2组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度；U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

算法具体步骤：

（1）初始时，S只包含源点，即S=v，v到v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）为∞(若u不是v的出边邻接点）。

（2）从U中选取一个距离v最小的顶点k，把k加入S中（该选定的距离就是v到k的最短路径长度）。

（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u∈U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值为顶点k的距离加上边上的权。

（4）重复步骤（2）和（3）直到所有顶点都包含在S中。至此，源点到其余顶点的最短径路都以得出。

每次以一个顶点为源点，重复执行Dijkstra算法n次（图中共有n个顶点），便可求的每一对定点之间的最短径路。总的执行时间为O(n^3)[3]。

2.2 算法的实现

算法实现的第一要务是运算速度，是平台扩展和空间利用。在综合分析当前各种计算机语言特性的基础之上，采用C++语言[4]实现Dijkstra算法。当前全路共有近7 000个车站，最短径路运算速度在10万条／s以上。

2.3 算法运用的关键点

最短径路算法是径路系统的灵魂，是能否支撑特定径路算法的核心之所在。最短径路计算关键在于特殊情况的处理。在我国铁路路网中有个别线路仅限本线各站发到货物使用，如齐晏线、沟海线等线，如表1所示，该类型线路不纳入最短径路计算，不能有通过济南—晏城北或晏城北—济南的最短径路出现，其本线里程仅供本线各车站到发使用。

表1 济晏线 济南-晏城北（国铁）

又如文献[5]中规定“太中线北中段、榆北线、定银线、包西线、神大线店塔-大保当段、甘钟线办理互为最短径路的本线到发。”那意味着该几条线路组成了一个局部的网络。车站之间相互到发可以使用网络中的线路里程，车站与网络外车站相互间的到发可以使用网络中的线路里程。

随着我国合资和地方铁路数量的增加，以上两种类型线路在路网中的比重在逐年增加，在算法设计时需要重点考虑[6]。

3 特定径路参数语言设计

特定径路参数语言设计是径路系统能否满足业务逻辑的关键之所在。假如全路的车流径路都按照最短径路来运输，那势必会造成在路网中比较短的线路上车流拥堵，而在路网中较长的线路上却没有车流，运力资源不能有效发挥，所以中国铁路国家集团有限公司会综合分析最短径路、线路流量、编组计划和货物运价等因素[7]，制定特定径路，使路网整体通过能力达到最优。那么，特定径路就必须由计算机参数语言去实现，当前全国铁路执行特定径路的OD流已占到了全路车流的65%，可见特定径路比重之高。并且随着近年来路网复杂度的增加，特定径路的复杂度也随之提升，特定径路参数语言的设计要求：既要满足复杂的业务需求，又要考虑径路运算的效率，还需兼顾系统参数维护的复杂度。本文将特定径路业务逻辑分为3类：集结类、改变经由类和修改里程类。

3.1 集结类

集结类是特定径路中最重要的一种类型，简单来讲就是将车流集结到某一个编组站，再执行该编组站对应的径路条文，该编组站发往某个组号范围的有可能根据特定径路再集结到下一个编组站，也有可能根据最短径路或特定径路到达到站。如文献[5]中第十二条上海、南昌局相关线中规定“（十）上海局袁寨及其以南、炉桥以西、三十里铺以北各站与上海局南京及其以东、裕溪口以南、靖江南以南各站相互间装的重车，按合肥东支点运输。”此条文规定车流集结到合肥东编组站；“（十一）凡经由合肥东（芜湖东）支点（含水蚌线、宁芜线塔桥-马鞍山各站）与上海局宣城以东、无锡西以南、黄渡以东各站相互间装的重车，经皖赣线、宣杭线运输。”此条文规定了合肥东编组站装到南翔以远的重车集结到乔司编组站。

通过集结类的设计便可实现特定径路，层层递归的业务逻辑。

3.2 改变经由类

改变经由类是特定径路中最为常见的一种类型，按照业务逻辑不同可分为两小类：原经由改变经由类、发到域改变经由类，下面举例说明。

文献[5]中第十二条上海、南昌相关线中规定“（四）凡经向塘西支点装到成都局（广汉-广元间各站除外）的重车，均经沪昆线、按株洲北支点运输。”此条是最为普通的原经由改变经由类，条文中并没有规定具体有哪些发站是经由向塘西支点的，发站是要经过最短径路和特定径路计算来判定的，每一个到站都有可能对应着不同的发区域。

文件中第十三条进出西南相关线中规定“（三十三）成都局成昆线各站装到南宁局黎塘以南各站重车，均经攀枝花分界站运输。”。此条为典型的发到域改变经由类，条文中明确地说明了发到域的范围，在此不再赘述。

3.3 修改里程类

修改里程类是径路里程统计中较为特殊的一种类型，主要用于计费里程的修改。如货物运价里程表中对淮南线的规定“裕溪口至芜湖东间按50 km计费”，但实际里程只有20 km，所以在计算路网最短径路时按照20 km计，而在里程统计时，上海铁路局里程加30 km、计费里程加30 km、基金里程加30 km、电气化里程加30 km。类似这样的实例，路网中还存在多处，需要在算法设计中特殊对待。

特定径路参数语言的设计诸如此类，但在参数语言编译算法上仍是一个非常复杂的工程，区域的定义、特定径路的对接、执行的效率和图形的展示需要设计者精心设计，并且最为关键的是对业务逻辑必须有最全面的掌握。

3.4 实例与结论分析

以铁路《货物运价里程表》[8]为路网基础信息，进行路网数据结构的搭建，以第2节中的最短径路算法进行程序设计，所得最短径路和里程全部符合《货物运价电子里程表信息系统》中环状径路的判断结果，如兰州北到广州西站的最短径路为兰州北-天水-新筑-商南-襄阳北-益阳东-捞刀河-广州西，里程为2 611 km。再以文献[5]为特定径路依据，进行特定径路参数语言的编写，所得特定径路的经由和里程完全符合《全路车流径路查询系统》的查询结果，如武威南到榆次站的径路为武威南-迎水桥-定边-绥德-榆次，里程为982 km，并且径路计算速度在Win 32环境下达到5万条／s以上。

4 结束语

本文的研究方法提升了径路系统的智能化程度，提高了运行效率，解决了平台扩展的问题，满足了当前业务逻辑的需求，但是在寻找最优径路和辅助决策方面还有一定的不足。下一步，我们将一如既往地进行理论算法[9]的深层次研究，并探索A*[10]、次短径路、佛洛依德（Floyd）和其他经典理论算法[11]在铁路运输径路中的实现方法，为中国铁路货物运输向现代化物流转型贡献技术力量。