A dissimilar alternative paths-search algorithm for navigation services: A heuristic approach

Abstract

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.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 14 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.