The Reachable Paths Finding Problem With Constrain Of Last Trains In Urban Mass Transit Network

The process of urban mass transport network continues to accelerate, to bring great convenience to the people when traveling. At the same time, the development of urban mass transport network brings new problems for people to travel, such as passengers who travel by subway cannot get to the destination by transfer due to the time of the last train of each line is not continuous.With the constant expansion of urban mass transit network, the choice of passenger travel path becomes more and more, how to provide passengers with real-time reachable-path is the starting point for research in this article. In this paper, reachable-path under the conditions of the last trains designed for passenger travel path under the conditions of the last trains induced to provide a practical way.First, the article defines the concept of reachability with the constrain of last trains, points that the reachability with the constrain of last trains consists of three parts, namely space reachability, time reachability and reachable convenience. And deeply analyzes the factors that affecting space and time reachability and reachable convenience under the last trains condition.Then established a simplified model of urban mass transport network in accordance with the definition of efficient path, an improved depth-first search algorithm was proposed for searching the efficient paths set during network among all OD pairs. Considering the transfer station and the routing endpoints station play a secisive role in judging the reachability of a path, some judgment rules was proposed. Then a method to calculation the latest boarding time that can be reachable between the OD pairs was raised, and so was the algorithm for generating real-time reachable paths. Considering some factors of reachable convenience, a generalized cost function was defined to evaluate every reachable path between O and D.Finally, the path searching simulation system with constrain of last trains in of Beijing subway was designed and implemented. And the model and algorithms in this paper was verified by living example.