A Dissimilar Alternative Paths-Search Algorithm for Navigation Services: A Heuristic Approach

作者：Jeong Yeon Jeong; Kim Tschangho John; Park Chang Ho; Kim Dong Kyu^*

来源：KSCE Journal of Civil Engineering, 2010, 14(1): 41-49.

DOI：10.1007/s12205-010-0041-8

• dissimilar alternative path
• navigation service
• K shortest paths algorithm
• path-partition-deletion method

The purpose of this paper is to present the development of a heuristic algorithm that searches dissimilar alternative paths efficiently for multi-route problems in navigation services. The K shortest paths algorithm, one of the algorithms that provides multiple paths, often provides very similar paths between an origin and a destination, oftentimes differentiated by only one different link. The algorithm developed in this paper is based on the renewed path-partition-deletion method, which searches for the shortest paths by executing the shortest-path algorithm only once. Users can obtain information on the alternative paths corresponding with their preferences by the user-specified allowable cost and duplication ratios included in the algorithm. Empirical studies based on a toy network and a Chicago network are presented to evaluate the efficiency of the developed algorithm. The results show the algorithm can be applied to the implementation of the paths-search algorithm for multi-route navigation services.

• 出版日期2010-1