进路处理是计算机联锁系统的核心功能，进路搜索的主要目的是便于进路处理。目前，已有多种进路搜索研究方法，如广度优先^[1]、改进深度优先^[2]及其它启发式算法^[3]等。Dijkstra算法是一种较为成熟的最短路径算法，其典型应用是解决距离最短、时间最少和花费最低的问题^[4]。但传统Dijkstra算法求解最短路径会耗费大量存储空间和计算时间，易陷入局部最优^[5]的问题。为减少搜索深度，本文提出一种基于改进Dijkstra算法的进路搜索算法。改进后的Dijkstra算法效率高，且简单易读。

本文建立车站站场图简化模型，采用有向图描述站场拓扑结构；在数据存储结构和优先级队列2个方面，对传统Dijkstra算法进行改进，采用广度优先的搜索方式，并编制仿真程序验证将改进Dijkstra算法用于进路搜索的有效性。

1   站场拓扑结构的有向图建模

有向图由顶点集和连接任意2个顶点之间的边集组成，顶点集表示数据元素的集合，边集为连接2个顶点之间的指向关系^[6]。将铁路站场图抽象为有向图，站场进路搜索问题即可转化为有向图的遍历问题^[7]。

站场进路搜索具有方向性。在搜索过程中，先确定好进路起始和终止信号机，从起始信号机到终止信号机之间经过的路径称为搜索进路，一条完整进路包含进路类型、方向和道岔信息等相关内容^[8]。完成进路搜索后，将搜索结果保存为文件，以便于进路处理。

图1为某铁路站场平面布置图。由图可知，铁路车站信号设备之间有前后连接关系。为了建立站场模型，对站场设备进行简化，抽象定义为不同属性的信号设备，主要考虑轨道电路、道岔和信号机3种设备。道岔和信号机作为顶点，轨道电路作为边，尽头线和安全线则以相连的道岔或信号机设备作为顶点，整个站场设备的拓扑结构可抽象为一个网状结构^[8]。

建立一个如图2所示的有向图模型：${{G}}'=\left\{{{E}}'{,N}\right\}$，并设定边统一指向左，边表示为${{E}}'=\left\{{{e}}_{\rm{1}}'{,}{{e}}_{\rm{2}}'{,\cdots ,}{{e}}_{{n}}'\right\}$。

图  1  某铁路站场平面布置

下载: 全尺寸图片 幻灯片

图  2  某铁路站场局部有向图模型

下载: 全尺寸图片 幻灯片

2   Dijkstra算法的改进

2.1   传统Dijkstra算法

Dijkstra算法是经典的最短路径算法，用于计算正权图的单源最短路径，即对于给定源节点，可求解自起始节点到其它所有节点的最短路径^[9]。最短路径不仅指传统意义上的距离最短，也可定义为代价最低，主要用于路网规划、旅行商问题、公交车线路规划以及社会能源分配等方面^[10]。

最短路径模型可以描述为：${D}\left({s,t}\right)= \left\{{{V}}_{{s}}\cdots {{V}}_{{i}}\cdots {{V}}_{{j}}\cdots {{V}}_{{t}}\right\}$。$ {D}\left({s,t}\right) $表示s到t的最短路径；其中，i与j表示s到t这条路径上的中间节点；$ {D}\left({i,j}\right) $表示i到j的最短路径。

在实际应用中，传统Dijkstra算法主要存在3个不足之处^[11]：（1）若数据存储采用邻接矩阵，对于大型稀疏矩阵会造成空间浪费，计算时间代价也高；（2）在算法迭代过程中，若节点所在链表或数组是无序的，每次搜索都将遍历全部节点，会影响搜索效率；（3）不适用于解决节点数目庞大的问题。

2.2   优化方法

针对传统Dijkstra算法存在的不足，结合铁路站场结构特点，从数据存储结构和队列结构2个方面改进Dijkstra算法。

2.2.1   存储结构优化

Dijkstra算法有2种应用广泛的数据存储结构：邻接表和邻接矩阵。其中，邻接矩阵会浪费大量存储空间，时间复杂度更高，而邻接表可有效节省存储空间^[11]。邻接表通常采用链表存储，而站场图拓扑结构较为简单，每个节点的相邻节点一般仅为1~3个。若采用链表实现，程序设计相对复杂，因此使用数组存储。程序设计中用2维数组来实现，数组每1个元素均为global_Node_Adj类型，数据结构定义如表1所示。

表  1  邻接表数据结构定义

vector<vector<global_Node_Adj>>m_vec_adj邻接表
		第0列	第1列	第2列
第0行m_vec_adj[0]	m_num	0	1
	m_name	“24”	“X3”
	m_id	2	1
	m_distance
第1行m_vec_adj[1]	m_num	1
	m_name	“X3”
	m_id	1
	m_distance	INF
...	...	...	...	...
第23行m_vec_adj[23]	m_num	23	24
	m_name	“D18”	“20”
	m_id	1	2
	m_distance	INF	3
第24行m_vec_adj[24]	m_num	24	25	26
	m_name0	“20”	“X4”	“X6”
	m_id	2	1	1
	m_distance	INF	59	59

下载: 导出CSV 

| 显示表格

2.2.2   队列结构优化

对于传统的Dijkstra算法，依次在节点集中查找未遍历过的节点、寻求最优解的过程会极大地影响算法效率。为减少这种影响，采用优先队列(priority_queue)对节点集进行有效排序，使插入或修改数据后，节点集仍能保持有序性。

优化队列结构采用堆栈，以优化每次查找离起始节点最近的节点的时间复杂度，而邻接表能够有效改善邻接矩阵占用过多空间的问题，减少存储空间的占用。

3   算法设计

3.1   进路搜索策略

对于进路搜索问题，确定好进路的起始节点和终止节点后，如何快速有效地选择一条最优路径是关键。当遇到对向道岔节点时，结合站场有向图拓扑结构的特点，若能避免迂回进路，则可以大幅提高运行效率^[12]。搜索策略主要有广度优先搜索和深度优先搜索；深度优选搜索是根据节点查找其邻接节点的过程，而广度优先搜索则是根据边查找其邻接点的过程。根据改进Dijkstra算法的特点，需要优先确认边的信息，故采用广度优先搜索更为方便。

除考虑距离因素外，本文设计的进路搜索算法还考虑了路径经过的道岔数目。理论上，搜索进路时存在多种遍历选择，因此会产生多条搜索路径。为尽量少占用轨道设备资源，少搜索分支，设置一个关键条件—搜索路径上道岔节点数量较少；同时，在道岔节点数量一致的情况下，选择列车进路作业用时最少的路径，即最短路径。改进Dijkstra算法中，对边进行松弛操作是根据目标函数值，目标函数值为：

其中，α、β为权重系数，两者之和为1；C是常量，其目的是考虑到道岔数与距离存在数量级差，故在将道岔数目放大一定比例的基础上，合理分配权重。

3.2   变量及数据结构定义

改进Dijkstra算法使用广度优先搜索解决赋权有向图单源最短路径问题，最终得到一棵最短路径树。在Visual Studio 2019 IDE中，采用C++编程语言实现进路搜索算法，将生成进路的相关数据存放于AllPathForRead.csv文件。建立Matlab GUI界面，通过MEX文件实现C++与Matlab的接口，在起点和终点文本框中输入相应节点时，Matlab GUI通过回调函数自动遍历找到搜索路径。

自定义的站场图数据格式如表2所示，存储为CSV格式文件，包含起点字符串、起点类型、终点字符串、终点类型、距离。其中，起点、终点字符串为信号设备名称，类型为自定义，默认信号灯类型为1，道岔节点类型为2。

表  2  站场图CSV数据格式

起点字符串	起点类型	终点字符串	终点类型	距离
24	2	X3	1	3
SF	1	D6	1	241
D6	1	6	2	3
6	2	8	2	88
6	2	D8	1	68
D8	1	18	2	207
18	2	D20	1	27
D20	1	22	2	3
...	...	...	...	...
20	2	X6	1	59

下载: 导出CSV 

| 显示表格

表3是根据输入CSV重新生成的边数组，在表2基础上,每个节点增加了数字索引，便于程序读取。

表  3  站场图边数组格式

起点数字	起点字符串	起点类型	终点数字	终点字符串	终点类型	距离
0	24	2	1	X3	1	3
2	SF	1	3	D6	1	241
3	D6	1	4	6	2	3
4	6	2	5	8	2	88
4	6	2	6	D8	1	68
...	...	...	...	...	...	...
20	D4	1	21	D14	1	230

下载: 导出CSV 

| 显示表格

定义一个Dijkstra_Node结构体数组，其代码框架如图3所示。该结构体包含当前点m_cur_node、父节点m_parrent_node、是否访问m_is_visited、距离m_ditance、访问标志、距离、道岔数、目标函数值。

其中，访问标志用于判断当前节点是否已被访问，若该节点已被访问则退出，进入下一循环；若未访问，则需要先将此节点的访问标志设置为已访问，再去访问该节点的邻接点。m_distance为源节点到当前节点的距离，m_turnout_node_num为源节点到当前节点所经过的道岔数，m_f_weight_sum为源节点到当前节点的目标函数值。

图  3  代码框架结构

下载: 全尺寸图片 幻灯片

当前节点m_cur_node是指能够与源节点连通的节点，而m_parrent_node就是每条路径对应节点的父节点。在初始化时，父节点的m_name被初始化为“NOT”，代表当前节点还没有父节点。是否访问标志m_is_visited用于确定该节点是否能被确定为最佳目标值。在结构体中，对m_f_weight_sum进行友元重载，其目的是后面优先队列出列时，以最小值为最高优先级，因为C++的优先队列默认是最大值先出列。

3.3   算法搜索流程

改进Dijkstra算法中进路搜索的具体流程为：

（1）定义元素为Dijkstra_Node的优先队列，初始化Dijkstra_Node数组信息；

（2）将源节点的目标值设置为0，并将该节点压入优先队列，判断队列信息是否为空；若为空，跳至（6）；

（3）队列信息不为空，则保存源节点信息，并根据边的指向，搜索下一个节点（即源节点的邻节点）；

（4）获得源节点到邻节点的距离和道岔数，计算目标值并进行判断，将目标值较小的邻接节点设置为目标节点；

（5）依据判断结果保存目标节点信息，更新Dijkstra_Node数组，将目标节点作为源节点搜索下一节点，返回（3）；

（6）结束遍历，返回初始化Dijkstra_Node数组信息。

4   实例仿真分析

进路按结构特点可分为有环和无环2类，无环进路为单路径直股搜索，有环进路又可分为多路径直股搜索和弯股搜索。

采用改进Dijkstra算法，对3种类型进路进行搜索验证，并利用MATLAB GUI实现路径搜索结果的可视化。

4.1   单路径直股搜索

以D14—D28进路为例，这条路径不包含八字道岔，不存在迂回进路，即有且只有1种路径选择。结果显示进路X—SI搜索到的最优路径为：D14—14—D16—D22—26—D28，路径长度为335 m，道岔节点数为3，目标值为328，如图4及图5所示。

图  4  D14—D28进路搜索设置与结果显示界面

下载: 全尺寸图片 幻灯片

图  5  D14—D28进路搜索路径

下载: 全尺寸图片 幻灯片

4.2   多路径直股搜索

以SF—XI进路为例，其起始和终止信号机均在同一股道上，但这2条进路均包含八字道岔，在搜寻过程中可有多条路径选择。以SF为始端，XI为终端，可有2种路径选择：

（1）SF—D6—6—D8—18—D20—22—XI

（2）SF—D6—6—8—D10/D12—10—16—18—D20—22—XI

其中，路径（1）搜索到的道岔节点为3，路径（2）搜索到的道岔节点为5，路径（1）上道岔点节更少，且其长度小于路径（2），因此路径（1）为最优选择。采用改进Dijkstra算法,搜索到的最优进路为路径（1），路径长度为664 m，道岔节点数为3，目标值为575.2，结果如图6及图7所示。

图  6  SF—XI进路搜索设置与结果显示界面

下载: 全尺寸图片 幻灯片

图  7  SF—XI进路搜索路径

下载: 全尺寸图片 幻灯片

4.3   弯股搜索

以D2—D34为例，对于多路径选择的情况，先考虑少搜索分支，比较搜索路径上道岔节点数目。若道岔节点数目相同，再考虑路径最短的进路，使用改进Dijkstra算法进行进路搜索，以寻找最优路径。结果如图8及图9所示。

图  8  D2—D34进路搜索设置与结果显示界面

下载: 全尺寸图片 幻灯片

图  9  D2—D34进路搜索控制台

下载: 全尺寸图片 幻灯片

以D2为始端，D34为终端，其路径选择有：

（1）D2—2—D4—D14—14—12—D18—20—X6—D32—3—D34

（2）D2—2—D4—D14—D16—D22—26—28—D28—D30—30—D32—32—D34

（3）D2—2—4—8—D12—D10—10—12—D18—20—X6—D32—32—D34

其中，路径（1）搜索到5个道岔节点，路径（2）搜索到5个道岔节点，路径（3）搜索到7个道岔节点；因此，路径3被剔除。剩下的路径（1）和路径（2）考虑最短路径，搜索结果为：Path= D2—2—D4—D14—D16—D22—26—28—D28—D30—30—D32—32—D34，路径长度为959 m，道岔节点数为5，目标值为867.2；结果如图8及图9所示。

以上3种类别进路搜索的实验结果表明：改进Dijkstra算法可高效、正确地完成多种类别进路搜索，效果较为满意。

5   结束语

提出改进Dijkstra算法，采用邻接表和优先队列的数据结构，以Viusal Studio 2019为开发平台，在Matlab GUI中通过接口进行调用，实现铁路站场进路搜索不重复、不遗留。该算法应用于进路搜索的优点主要有2个方面：（1）算法程序与站场数据相互独立，遍历不同的站场图只需修改站场数据即可，程序可移植性强；（2）算法设计提高了内存空间利用率，缩短了搜索时间，提高了站场图遍历效率。