基于深度优先搜索的铁路站场遍历算法研究

Traversing Algorithm of Railway Yard Based on DFS

在列车运行控制系统中,及时准确地了解列车所在位置是非常重要的。卫星定位技术GNSS(GlobalNavigation Satellite System)已经逐渐应用到列车定位技术中,在对列车进行定位时需要对定位数据的可靠性进行验证。车站的定位数据可靠性验证工作建立在对车站站场进行多次遍历获得定位数据的基础上。利用计算机仿真技术模拟列车在站场内遍历能够对现场很难实现的遍历情况进行重复测试。本文对铁路站场与有向图的相似性进行研究,建立基于铁路站场结构的拓扑模型,在此基础上结合站场实际遍历的情况与图的深度优先遍历算法思路,提出一种基于链表数据结构的连续遍历站场的算法。结合实际站场图进行遍历算法仿真,较好地实现了连续遍历并获取较高的遍历效率。

It is important to know the location of the train timely and accurately for the train control system. As for the train localization using the GNSS technology, validation of GNSS location data is necessary. In a railway yard, before validating the data reliability, the yard has to be traversed several times in order to get the location data. The computer simulation technology is used to simulate yard-traversing, and traversing can be realized repeatedly by simulation even for some situations difficult on site. In this paper, the similarity between railway yard and direct graph was researched. A new topological model of the railway yard structure was proposed. Then, considering the actual traversing situation and referring to the Depth First Search Algorithm, a new continuous traversal algorithm based on the chained list structure was also proposed. Simulation results of real railway yards confirm that the proposed algorithm achieves continuous traversing process with quite high efficiency.