Research And Application Of An Improved Multi-path Searching Algorithm On City Public Transportation Network

Optimal route selection on city public transportation network for going out is one of important research content in CPT (City Public Transportation), and affects directly efficiencies of daily work, study, living and going out of city residents.Based on analysis a variant of multi-path search algorithms in door and out door of China at present, a method of modeling has been proposed for large scale CPT network, therefore, an improved algorithm in which A* algorithm and idea of the deviation path have been combined with each other has been presented too.The primary research work and innovations made by author of this paper are summarized as the follo wings:1) Analysis and research of relevant searching algorithms. Introduction and implementation of an improved algorithm which combined A* and deviation path, searched potential one or multi-best routes according to heuristic feedback.2) A modeling method includes data structure of storage was introduced for large scale CPT network.3) A suitable heuristic feedback function which obtained high efficiency under the guarantee of best solution no losing was applied.4) Design and implementation of the improved algorithm based on the conclusion of this paper and efficiency comparison with the pure A* algorithm through the experiments.There is almost no report of research that bring the deviation path to A* algorithm and construct the heuristic evaluating function using geographic location information of bus stops. The significant higher efficiency of improved algorithm compared with Dijkstra algorithm and A* algorithm was proved by the experimental results.