A Diamond Search Algorithm of Travel Route Planning

Many optimal algorithms for travel route planning have been successfully and widely used in the fields of dynamic system control, decision making, and manufacture processes planning. In this paper, the optimal algorithm for travel route planning with constrains of a given set of mid nodes is proposed. The algorithm provides an efficient cost and path computation for searching the road map from both the start note and the target node simultaneously. The optimal trajectory and the related cost between the start node and the set of mid nodes as well as that between the set of mid nodes and the target can be determined by the algorithm of Dijkstra or other algorithms, after that the optimal route between the start node and the target node is determined by only searching the necessary nodes of the set of mid nodes. The shape of the searched road map is in the form of skewed diamond so we call this algorithm the diamond search algorithm. This algorithm not only can provide an efficient computation for travel route planning, but also has the potential be applied to the fields of decision making, dynamic control, unmanned vehicle navigation, and automated manufacturing processes.