Centre de documentation
scientifique

A hybrid link-node approach for finding shortest paths in road networks with turn restrictions / Qingquan Li in Transactions in GIS, vol 19 n° 6 (December 2015)  

Public [article]  inTransactions in GIS > vol 19 n° 6 (December 2015) . - pp 915 - 929 Titre : A hybrid link-node approach for finding shortest paths in road networks with turn restrictions Type de document : Article/Communication Auteurs : Qingquan Li, Auteur ; Bi Yu Chen, Auteur ; Yafei Wang, Auteur ; William H. K. Lam, Auteur Année de publication : 2015 Article en page(s) : pp 915 - 929 Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Géomatique [Termes IGN] analyse comparative [Termes IGN] calcul d'itinéraire [Termes IGN] chemin le plus court, algorithme du [Termes IGN] navigation automobile [Termes IGN] noeud [Termes IGN] requête spatiale [Termes IGN] réseau routier [Termes IGN] traitement de données localisées Résumé : (auteur) 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. Numéro de notice : A2016-438 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article nature-HAL : ArtAvecCL-RevueIntern DOI : 10.1111/tgis.12133 En ligne : http://dx.doi.org/10.1111/tgis.12133 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=81349 [article]