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

Research on route search based on improved Dijkstra algorithm

进路搜索是计算机联锁的核心部分,其准确性及高效性对保证行车安全至关重要。建立铁路站场结构的有向图模型,将站场进路搜索问题转化为有向图的遍历问题;根据铁路站场简化图的特点,从数据存储结方式和队列结构2个方面改进传统Dijkstra算法,采用广度优先搜索方式,提出以最短路径为目标函数的进路搜索策略;编制仿真程序对该算法进行验证,结果表明:基于改进Dijkstra算法能够正确、高效地完成多种类别进路搜索。

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.