A hybrid link-node approach for finding shortest paths in road networks with turn restrictions
A hybrid link-node approach for finding shortest paths in road networks with turn restrictions
复制标题
一种混合链路节点方法，用于在具有转弯限制的道路网络中寻找最短路径
DOI：
10.1111/tgis.12133
复制
发表时间：
2015
影响因子：
2.4
通讯作者：
Lam William H. K.
中科院分区：
文献类型：
--
作者：
Li Qingquan;Chen Bi Yu;Wang Y.F.;Lam William H. K.
转弯限制，如“禁止左转”或“禁止掉头”，在真实的道路网络中很常见。在最短路径问题中必须明确考虑这些转弯限制，忽略它们可能导致路径不可行。本文提出了一种混合链路节点Dijkstra （HLND）算法，用于精确求解具有转弯限制的道路网络中的最短路径问题。本文设计了一种新的链路-节点混合标记方法，在有回合限制的受限节点上使用基于链路的标记策略，在没有回合限制的不受限节点上使用基于节点的标记策略。对多个实际道路网络的计算结果表明，本文提出的HLND算法与基于链路的Dijkstra算法获得了相同的最优结果，而与经典的基于节点的Dijkstra算法具有相似的计算性能。
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.