城市轨道交通网络时变路径搜索算法

为求解时变路径搜索问题,设计并实现了城市轨道交通大规模网络条件下的时变k短路径搜索算法.算法可分为两部分:首先基于深度优先的边删除法搜索网络的静态k短路径,然后将静态k短路径按照列车到发时刻进行扩展并排序获得时变k短路径.将算法应用于北京地铁网络路径搜索实例中,通过与既有算法对比,证明本文算法具有较优的效率,并能够获取基于列车时刻表的有效的时变k短路径集,为城市轨道交通网络路径搜索和管理提供辅助技术支持.

Temporal path searching algorithm of urban rail transit network

A new method on searching the dynamic and temporal k-shortest paths in the urban rail transit network is put forward in this paper,which can be used to solved the dynamic path searching problem in huge scale network.The algorithm can be divided into two part:firstly,the static k-shortest path of the network can be searched based on depth-first deletion algorithm;then the temporal path can be obtained and sorted by the train arrival and departure time expanding in the schedule.The effectiveness of the algorithm proposed in this paper is verified in comparison with the existing algorithm through the case study in Beijing subway network,and the temporal k-shortest path in the network based on the train schedule can be obtained accurately,which demonstrates that it could provide decision support for the operation and travel guidance of path management in urban rail transit network.