一种基于Dijkstra算法的动态进路规划方法

金 云，周 苗，黄仁欢，虞乾俪

（通号万全信号设备有限公司，杭州 310000）

工业铁路通常由多个不同功能的站场组成，设置公司级调度和站级调度的两级调度模式来对公司内专用铁路进行调度指挥。分散的调度权将一个完整的生产作业过程分割开来，影响企业的生产作业效率。随着自动化、信息化技术的进步，繁琐的企业内部铁路运输可以通过技术手段整合。采用集中调度模式，只在公司级设置一级调度，同时提供调度系统的自动化、智能化，减少调度人员，提高生产效率。

进路搜索是工业铁路智能调度管理系统的基本功能，其运行效率以及所得目标进路直接关系到企业运输计划的高效性和准确性。本文通过对站场数据的组织，将站场图抽象为无向带权连通图，建立静态网络拓扑图，在此基础上通过道岔、区段的实时状态，动态调整无向网络拓扑图中各个边的权重，基于图论中的最短路径算法模型，完成起始无岔区段到目标无岔区段的路径规划，再与系统中的基本进路进行进路中最多元素的模糊匹配，自动生成进路列表，以供系统做自动进路的触发。

1 最短路径算法介绍

对于带权图G=（V,E），从图中任意一点vi到图中任意一点vj的边的权值定义为路径所包含的所有元素权值的总和，而不是边所包含的所有元素个数的总和。最短路径求解问题可以分成两个不同的子问题，即单源最短路径问题和所有顶点对之间的最短路径问题。前者是找出某一顶点出发到图中所有其他顶点的最短路径，主要的算法有迪杰斯特拉（Dijkstra）算法、贝尔曼-福特（Bellman-ford）算法等；后者是求解图中的每一对顶点之间的最短路径，主要算法有弗洛伊德（Floyd）算法。现有的使用场景为计算指定的两个点之间的最短路径，故首先选择单源最短路径问题所对应的算法。

Dijkstra算法是贪心算法的一种，按照路径长度递增的次序产生最短路径的算法，无法处理带有负权值的图。但是该算法的稳定性很强。基础算法时间复杂度为O(V2)，对于稀疏图(边的数量远小于顶点数的平方)，该算法的时间复杂度可以提高至O(ELgV)。Bellman-ford算法能够处理带有负权值的图，但是该算法的稳定性不如Dijkstra算法，基础算法的时间复杂度为O(V×E)。其中E为图中的边数，V为图中顶点个数。

本文所涉及的静态网络拓扑图中边的权值全都是非负值，而且该图是一张稀疏图。故选择Dijkstra算法作为最短路径的求解比较适合本应用场景。

2 静态拓扑图生成

系统内的道岔全都定义为单动道岔，如果是双动道岔，则通过内部逻辑的聚合，按照一个道岔数据对外提供，但是在系统内都按照独立运算。根据道岔和无岔区段的链接关系数据，自动创建一张无向带权的网络拓扑图。生成的静态网络拓扑图则由点的集合V(G)={vi}和边的集合E(G)={eij(i

点集V(G)中的点ei代表站场图中的第i个无岔区段。边集E(G)中的边eij(i

3 最短路径生成算法

对于图G={V(G),E(G)}，假设需要求无岔区段s到无岔区段e的最短路径。

1）权值初始化，根据站场中的道岔、区段、信号机的实时状态，动态修改该设备所在边的权值。例如道岔封锁，则设置包含该道岔的边的权值为∞，代表该边不可达，道岔单锁在指定位置，则设置包含该道岔相反位置的边为不可达边。区段占压、封锁等，则设置该区段所在边的权值为∞，代表该边不可达。信号机封锁、断丝等，则设置该信号机的防护区段所在边的权值为∞，代表该边不可达。

2）设顶点集Vc(G)=Ø和边集Ec(G)=Ø，从图G中的顶点集V(G)中取出开始区段s所对应的点vs,把vs放入顶点集Vc(G)中。此时Vc(G)={vs},V(G)=V(G)-Vc(G)。

3）从图G中的边集E(G)中取出一个临时边集Et(G)={eij,…|(vi∈Vc(G)&&vj∈V(G)) ||(vi∈V(G)&&vj∈Vc(G)) }，

即对于Et(G)集合中的任意边eij，其中eij的两个端点分别属于两个不同的顶点集合V(G)和Vc(G)。

如果Et(G)为空集或者Et(G)中所有边的权值都是∞，则无法找到最短路径，算法退出。

如果Et(G)中存在可达边，设eij∈Et(G)为集合中权值最小的边，则把边eij添加到集合Ec(G)中。

4）在vj中标记父节点为vi，并且把点vj添加到集合Vc(G)中。

如果vj就是无岔区段e所对应的点，则找到该最短路径。算法退出。

如果vj不是无岔区段e所对应的点，则把Et(G)中两个顶点都在Vc(G)中的边从该集合中删除Et(G)= {eij,…|(vi∈V(G)&&vj∈V(G)} 。把Et(G)中的剩余边全都放回集合E(G)中。

5）重复从步骤3）开始执行，直到顶点集合V(G)中不再包含任何顶点为止。

4 进路转换

按照结束顶点中包含的父节点信息以及边中道岔的先后顺序(边的双下标和点的顺序一致，则边中的道岔按照正序输出。边的双下标和点的顺序相反，则边中的道岔按照逆序输出)，把Dijkstra算法生成的路径转化为站场中的各个基本元素。由于站场中的基本进路有些只包含一个道岔区段，可能会出现匹配到的进路方向和规划路径的方向相反，故针对进路中只有一个道岔区段的，则自动把该道岔区段后面的元素临时添加到该基本进路中。对于相同始端的进路，在进路都覆盖最短路径元素的前提下，保留进路中包含元素多的进路作为临时候补进路，同时记录该进路匹配开始的元素在最短路径元素中的位置。当所有进路匹配完毕后，按照记录的起始位置进路排序，按照进路的开始位置和结束位置，删除中间有交叉的进路。当最短路径中的道岔元素匹配完毕，则最短路径转化为进路成功。

例如按照如图1所示，假设列车需要由4G运行到3G。

1）按照Dijkstra算法计算出最短路径:4G→9/19WG→3G。

2）由路径转化为基础元素为: 4G→19→9/19WG → (19) → (21) → 27 → 3G。

3）基本进路匹配的临时候选进路如表1所示(其中S4→D11，D23→S3只包含一个道岔区段，故匹配时增加一个后续连接区段)。

表1 进路匹配Tab.1 Route matching

4）临时候补进路的匹配开始位置和匹配结束位置没有出现交错的情况，全都转化为候补进路。如果临时候补进路的匹配位置出现交错，则把匹配开始位置大的进路从临时候补进路中剔除掉。

5）把路径基础元素列表中的元素按照候补进路中的道岔区段元素进行比较，去除掉相同元素。进路基础元素列表变为：4G、9/19WG，3G。

6）除去道岔区段后的路径基础元素列表中如果不包含道岔区段，则最短路径转化为基本进路成功。如果包含道岔区段，那么最短路径转化为联锁进路失败。

5 结束语

工业铁路运输调度的主要任务就是列车把货物从一个股道拉到另一个股道，并且掺杂着一些装车、卸车等标准作业内容。而从一个股道到达另一个股道就需要调度员根据自己对站场的认识，一步一步的人工排列联锁进路来指导火车运行。基于本算法的进路动态规划方法，系统只需要输入目标股道信息，即可自动计算、选择出最优的联锁进路组合，根据列车的实时位置，自动执行计划进路，实现运动过程的自动化。而且针对联锁站场的实时变化，自动进路也不一定百分之百办理。当出现进路自动触发失败的情况，系统可以通过列车当前位置和目的地信息，自动重新规划，更新进路表，保证列车以最优的路线抵达目标股道进行标准作业。Dijkstra算法的实现，大大减少信号调度人员的工作量，保证调度工作的准确完成，中间的全自动过程为后期实现全面无人驾驶打下了坚实的基础。