A Hybrid Search Method to Find Minimal Length Paths for Navigation Route Planning

摘要

This paper reports an experimental result on combining multiple search methods in order to find the minimal length path for navigation route planning. In particular, in order to incorporate the strengths of A~* algorithm and Dijkstra 's algorithm, a framework of unifying the two algorithms is investigated. In the unified search algorithm, the OPEN lists of the A~* algorithm and the Dijkstra's algorithm are (ir)regularly switched, so that the computational cost is reduced and the route that could not be searched by A~* algorithm can be discovered. The experimental results, obtained using artificial and real-city map data, demonstrate that the proposed hybrid algorithm can reduce computational cost significantly and shows similar results with the suggested route from the origin to the destination in Dijkstra's algorithm.