For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Finding Useful Detours in Geographical Databases
Tetsuo SHIBUYA Hiroshi IMAI Shigeki NISHIMURA Hiroshi SHIMOURA Kenji TENMOKU
IEICE TRANSACTIONS on Information and Systems
Publication Date: 1999/01/25
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Algorithm and Computational Complexity
geographical databases, car navigation, shortest paths, detour query,
Full Text: PDF>>
In geographical databases for navigation, users raise various types of queries concerning route guidance. The most fundamental query is a shortest-route query, but, as dynamical traffic information newly becomes available and the static geographical database of roads itself has grown up further, more flexible queries are required to realize a user-friendly interface meeting the current settings. One important query among them is a detour query which provides information about detours, say listing several candidates for useful detours. This paper first reviews algorithms for the shortest and k shortest paths, and discusses their extensions to detour queries. Algorithms for finding a realistic detour are given. The efficiency and property of the algorithms are examined through experiments on an actual road network.