Transportation network navigation with turn penalties
Gene Eu Jan, Ming-Che Lee, Shang-Hsing Hsieh, Yung‐Yuan Chen · 2009
The path length and number of turns are the major factors in path planning of transportation and navigation systems. Shortest path planning has been widely studied in the literatures. Most researches only take the issue of shortest distance into account, and the impact of turns are rarely mentioned, that is, the shortest path may not be the fastest. Considering both two factors in a path-searching algorithm is NP-complete. This paper proposes two algorithms: the least-turn path algorithm and the minimum-cost path algorithm to balance both the path length and turns. The proposed algorithms adapt Lee's rectilinear routing algorithm to find a least-turn path with turn penalty on a mesh-connected network. In addition, Kirby's concept and a modified Dijkstra's algorithm are also introduced for the proposed minimum-cost path algorithm, which considers the turn penalty and the length factor on a transportation network. The time complexities for both algorithms are O(N), where N is the number of nodes on a mesh-connected network or the intersections on a transportation network.