Least time path planning under urban timetabled public transport using A∗ Algorithm

This paper proposes an ad hoc A* algorithm to find a least time path under urban timetabled public transport network. Vehicles are assumed to run punctually associated with timetables. This work first formulate complex urban timetabled public transport network considering scheduled lines serving over it and walk between two nodes for transfer purpose. Then, multi-label arc, shorte for m-arc, is defined to represent detailed travel process, and timing of each m-arc is expounded, too. Path is composed of a sequence of m-arcs. To find a least travel time path from an origin with pre-specified initial time to a destination under urban timetabled public transport among a large number of candidates, an ad hoc A* algorithm is developed, which propose a strategy for estimating elapsed time of partial paths that ended at destination, to be a tight lower bound of associated real elapsed time for the purpose of trying to reduce searching scope. The proposed algorithm is proved to guarantee an optimal solution in theory and demonstrated with an application for its high efficiency.