Urban Rail Transit Efficient Path Search using Best-First Strategy

Abstract

The passenger route selection and passenger assignment are the basis of the analysis of the
Urban Rail Transit (URT) passenger flow. In order to improve URT passenger management
and operation planning, it is of great importance to implement a fast and efficient path search
algorithm. This paper reconstructs the urban rail transit network based on network topology
and proposes an efficient path search algorithm for the URT network based on the Best-First
search strategy, which can improve the efficiency of the search while avoiding the problem of
omitted or redundant routes. Firstly, reasonably restrictions were made on the efficient paths
between ODs based on travel costs and transfer counts; secondly, the network structure was
simplified by omitting intermediate stations; finally, a tree-like search based on the Best-First
search strategy was performed on the simplified network to obtain efficient paths that meet the
actual passenger choice. Based on the assumption that the travel time distribution of one single
path approximately obeys a normal distribution, Origin-Destination (OD) pairs of Chengdu
Metro were taken as examples to examine the algorithm. Travel time of specific OD pairs was
extracted from the transaction data of Chengdu Metro and was analyzed by the Expectation
Maximum (EM) clustering method to obtain the observed travel time of each route. The error
between the clustering result and the efficient paths cost obtained by this algorithm was less
than 5%, which verified the rationality of the efficient path generation algorithm.