Premium
A Hybrid Link‐Node Approach for Finding Shortest Paths in Road Networks with Turn Restrictions
Author(s) -
Li Qingquan,
Chen Bi Yu,
Wang Yafei,
Lam William H. K.
Publication year - 2015
Publication title -
transactions in gis
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.721
H-Index - 63
eISSN - 1467-9671
pISSN - 1361-1682
DOI - 10.1111/tgis.12133
Subject(s) - node (physics) , link (geometry) , shortest path problem , computer science , path (computing) , turn (biochemistry) , k shortest path routing , mathematical optimization , algorithm , mathematics , theoretical computer science , computer network , graph , engineering , structural engineering , biochemistry , chemistry
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 D ijkstra'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 D ijkstra's algorithm, while having a similar computational performance to the classical node‐based D ijkstra's algorithm.