A Hybrid Link‐Node Approach for Finding Shortest Paths in Road Networks with Turn Restrictions |
| |
| Authors: | Qingquan Li Bi Yu Chen Yafei Wang William H K Lam |
| |
| Affiliation: | 1. State Key Laboratory of Information Engineering in Surveying, Mapping and Remote SensingWuhan University;2. Department of Civil and Environmental EngineeringHong Kong Polytechnic University |
| |
| Abstract: | Turn restrictions, such as ‘no left turn’ or ‘no U‐turn’, are commonly encountered in real road networks. These turn restrictions must be explicitly considered in the shortest path problem and ignoring them may lead to infeasible paths. In the present study, a hybrid link‐node Dijkstra's (HLND) algorithm is proposed to exactly solve the shortest path problem in road networks with turn restrictions. A new hybrid link–node labelling approach is devised by using a link–based labelling strategy at restricted nodes with turn restrictions, and a node‐based labelling strategy at unrestricted nodes without turn restrictions. Computational results for several real road networks show that the proposed HLND algorithm obtains the same optimal results as the link‐based Dijkstra's algorithm, while having a similar computational performance to the classical node‐based Dijkstra's algorithm. |
| |
| Keywords: | |
|
|
