基于改进Dijkstra算法的进路搜索研究

杜文文; 杨扬

基于改进Dijkstra算法的进路搜索研究

杜文文,
杨扬

西南交通大学　信息科学与技术学院，成都　611756

基金项目: 中国铁路总公司科技研究开发计划重点课题（2017X011-A）

详细信息

作者简介:
杜文文，研究生

杨　扬，副教授

中图分类号: U284.48 : TP39
计量
- 文章访问数: 88
- HTML全文浏览量: 292
- PDF下载量: 28
出版历程
- 收稿日期: 2020-03-24
- 刊出日期: 2020-09-24

Research on route search based on improved Dijkstra algorithm

Southwest Jiaotong University, College of Information Science and Technology, Chengdu　611756, China

摘要

摘要: 进路搜索是计算机联锁的核心部分，其准确性及高效性对保证行车安全至关重要。建立铁路站场结构的有向图模型，将站场进路搜索问题转化为有向图的遍历问题；根据铁路站场简化图的特点，从数据存储结方式和队列结构2个方面改进传统Dijkstra算法，采用广度优先搜索方式，提出以最短路径为目标函数的进路搜索策略；编制仿真程序对该算法进行验证，结果表明：基于改进Dijkstra算法能够正确、高效地完成多种类别进路搜索。
- 进路搜索 /
- 有向图 /
- Dijkstra算法 /
- 最短路径
Abstract: Route searching is one of the core parts of computer interlocking and its efficiency and accuracy is vital to ensure the safety of traffic control. A directed graph model based on the structure of railway station yard is modeled and the problem of searching routes in a railway station yard is then converted as the problem of traversing a directed graph. According to the characteristics of simplified railway station yard graph, traditional Dijkstra algorithm is improved from the aspects of data storage and queue structure, breadth-first search is adopted, and a route searching strategy with the shortest path as objective function is proposed. Furthermore, a simulation program is built to verify this algorithm and the simulation results show that this improved Dijkstra algorithm can complete searching types of routes accurately and efficiently.
- route searching /
- directed graph /
- Dijkstra algorithm /
- shortest path

HTML全文

图 1 某铁路站场平面布置

下载: 全尺寸图片幻灯片

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

下载: 全尺寸图片幻灯片

图 3 代码框架结构

下载: 全尺寸图片幻灯片

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

下载: 全尺寸图片幻灯片

图 5 D14—D28进路搜索路径

下载: 全尺寸图片幻灯片

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

下载: 全尺寸图片幻灯片

图 7 SF—XI进路搜索路径

下载: 全尺寸图片幻灯片

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

下载: 全尺寸图片幻灯片

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

下载: 全尺寸图片幻灯片

表 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 站场图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 站场图边数组格式

起点数字	起点字符串	起点类型	终点数字	终点字符串	终点类型	距离
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

参考文献(12)

[1]	赵志熙.计算机联锁系统技术[M].北京: 中国铁道出版社, 1999: 233-237.
[2]	谢林,杨扬. 基于二维坐标信息进路搜索算法研究 [J]. 铁路计算机应用,2015,24(8):16-19. DOI: 10.3969/j.issn.1005-8451.2015.08.005
[3]	梁艺凡,谭丽,冯挺. A*进路搜索算法的研究与实现 [J]. 铁道标准设计,2013(2):17-20.
[4]	康文雄,许耀钊. 节点约束型最短路径的分层Dijkstra算法 [J]. 华南理工大学学报(自然科学版),2017,45(1):66-72.
[5]	王海梅,周献中. 一种限制搜索区域的最短路径改进算法 [J]. 南京理工大学学报(自然科学版),2011,33(5):638-642.
[6]	严蔚敏, 吴伟民. 数据结构(C语言版)[M]. 北京: 清华大学出版社, 1997.
[7]	耿杰,蔡伯根,王剑,等. 基于深度优先搜索的铁路站场遍历算法研究 [J]. 铁道学报,2012,34(4):51-56. DOI: 10.3969/j.issn.1001-8360.2012.04.009
[8]	肖蒙,宁海安,赵志荣. 基于有向图的进路搜索算法研究与设计 [J]. 自动化与仪器仪表,2012(6):69-73. DOI: 10.3969/j.issn.1001-9227.2012.06.027
[9]	蔚洁,杨怀雷,成汝震. 基于Dijkstra算法的最优路径搜索方法 [J]. 河北师范大学学报(自然科学版),2008,32(5):590-593.
[10]	樊守伟,严艳,张少杰,等. Dijkstra算法与旅游路径优化田 [J]. 西安邮电大学学报,2014,19(1):121-124.
[11]	赵艳丽. 实际路网最短路径算法优化与实现[D]. 广州: 华南理工大学, 2015.
[12]	吴鹏,寇玮华,许木南,等. 基于Dijkstra和深度优先搜索的进路搜索算法研究 [J]. 交通运输工程与信息学报,2017,15(4):38-43. DOI: 10.3969/j.issn.1672-4747.2017.04.006

施引文献(5)

期刊类型引用(2)

1.	史永胜，容璇. 基于特征匹配的飞机外表面缺陷差异检测研究. 航空计算技术. 2023(01): 6-10 . 百度学术
2.	杨凯，张淼，祁苗苗. 铁路车辆监测图像识别模型训练及验证平台研究. 铁路计算机应用. 2023(06): 26-30 . 本站查看