INTRODUCTION OF SEARCHING AREA EXTRACTION SCHEME AND BI-DIRECTIONAL DIJKSTRA ALGORITHM FOR REDUCING SEARCH TIME OF THE SHORTEST PATH
SH Lee, Kunhee Choi, W-G Kim · Intelligent Transportation: Realizing the Future. Abstracts of the Third World Congress on Intelligent Transport SystemsITS America · 1996
The shortest path algorithm for route guidance is implicitly required not only to support geometrical variations of transportation networks such as U-TURN or P-TURN but to efficiently search reasonable routes in a searching mechanism. The purpose of this paper is to integrate two such requirements; that is, to allow U-TURN and P-TURN possibilities and to cut down searching time in locating routes between two points (origin and destination) in networks. The authors also propose a new type of link searching algorithm which can solve the limitation of vine building algorithms at consecutively left-turn prohibited intersections. The test site is a block of Gangnam road network that has some left-turn prohibited and allowed U-TURN intersections. Four models have been identified to be comparatively analyzed in terms of searching efficiency. The models are as follows: 1) Model 1 - Link Searching Dijkstra Algorithm without Searching Area Extraction (SAE); 2) Model 2 - Link Searching Dijkstra Algorithm with SAE; 3) Model 3 - Link Searching Bi-directional Dijkstra Algorithm without SAE; and 4) Model 4 - Link Searching Bi-directional Dijkstra Algorithm with SAE. The results of comparative evaluation show that Model 4 can effectively find an optimum path faster that any other models, as expected. Some discussions and future research agenda have been presented in the light of dynamic route guidance applications of the urban ATIS.