FINDING A REALISTIC DETOUR BY AI SEARCH TECHNIQUES
Takumi Shibuya, Tetsurou Ikeda, H Imai, Shôichi Nishimura, Hiroshi SHIMOURA, Kenji TENMOKU · 1995
In the navigation system, it is very important not only to find the shortest path but also a detour, in case of a traffic jam for example. This paper surveys algorithms for the shortest path problem and the k shortest path problem at first, extends the latter algorithm for the 2-terminal k shortest paths problem, using AI search techniques such as the bidirectional A 3 algorithm, then defines `detour' precisely, and proposes algorithms for finding a realistic detour based on these algorithms. The efficiency and property of the algorithms are examined through experiments on an actual road network. 1. INTRODUCTION The shortest path problem is very important in various fields. For example, route navigation systems must show the shortest route to the destination as fast as possible. Thus, the shortest path problem is studied very well for a long time. For example, the Dijkstra method is the most famous and traditional algorithm for this problem. To make this algorithm more efficient, m...