A novel shortest path algorithm with topology transformation for urban rail transit network. (July 2022)

• Record Type: Journal Article
• Authors: Hao, Yuanyuan; Si, Bingfeng; Zhao, Chunliang
• Is Part Of: Computers & industrial engineering. Volume 169(2022)
• Publication Date: 2022-07
• Subjects: Urban rail transit system -- Topology transformation -- Hierarchical topology network -- The shortest path; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2022.108223
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: A hierarchical network framework based on topology and restoration (HTNR) is proposed. The station extraction algorithm is developed to simplify the type of stations. The search_restoration algorithm is established to find the shortest path. Experimental results show that HTNR is superior to peer competitors. Abstract: As the scale of the network expands and the line relationship becomes more complicated, the performance of the traditional shortest path algorithm is degraded. How to design a fast shortest algorithm is full of challenges. A lot of research is dedicated to improving the search ability of the shortest path algorithm. As an alternative way, the rail network contraction has attracted few attention. Meanwhile, the research is preliminary since it lacks a complete theoretical basis and its design is too complicated. In this paper, a hierarchical network framework based on topology and restoration (HTNR) is proposed to search the expected path. First, the homeomorphic open rectangular sets are established by using the topological transformation. Then, the types of stations are simplified by extracting non-transfer stations, which adopts the 9-intersection model. Next, the shortest path is searched by executing the search_restoration algorithm. Finally, to verify the effectiveness and efficiency of the proposed HTNR, a series of experiments are implemented on multiple test rail networks. The results show that the proposed framework has obvious superiority or competitiveness over state-of-the-art algorithms.