基于轨道交通网络特点的K最短路算法研究

城市轨道交通网络发展带来出行路径选择的复杂性,为了科学掌握线路客流,组织运输,合理引导乘客路径选择,需要开展轨道多路径算法研究;同时,随着生活节奏加快,要求算法高效,注重路径获取的实时性。针对轨道网络特征,将站点之间K最短路搜索转化为线路换乘组合搜索,降低搜索空间复杂度,并利用杭州轨道交通网络进行案例验证。算法明显提升轨道网络K最短路搜索效率,能够更快速响应轨道交通实际运行变化,有助于提升今后轨道交通出行服务应用。

Shortest-path Algorithm Based on the Characteristics of Rail Transit Network

The complexity of travel route selection is a challenge brought about by urban rail network development. Accordingly, research on the rail multipath algorithm must be performed to scientifically master the passenger flow of each route, organize transportation, and offer a reasonable guide for passenger route selection. With the acceleration of urban life, efficiency of the algorithm is required, and the real-time performance of path acquisition is emphasized. According to the rail network characteristics, this study translates the K shortest path between stations into a line transfer combination search, reduces the complexity of the search space, and uses the Hangzhou rail network for case verification. Consequently, the algorithm significantly improves the K shortest path efficiency of the rail network, more quickly responds to the actual rail-operating changes, and is beneficial to the future application of the rail travel service.