A Hybrid Link-Node Approach for Finding Shortest Paths in Road Networks with Turn Restrictions

Qingquan Li, Bi Yu Chen, Yafei Wang, Hing Keung William Lam

Research output: Journal article publicationJournal articleAcademic researchpeer-review

22 Citations (Scopus)

Abstract

John Wiley & Sons Ltd. 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.
Original languageEnglish
Pages (from-to)915-929
Number of pages15
JournalTransactions in GIS
Volume19
Issue number6
DOIs
Publication statusPublished - 1 Dec 2015

ASJC Scopus subject areas

  • Earth and Planetary Sciences(all)

Cite this