Centre de documentation
scientifique

Constrained shortest path problems in bi-colored graphs: a label-setting approach / Amin AliAbdi in Geoinformatica, vol 25 n° 3 (July 2021)  

Public [article]  inGeoinformatica > vol 25 n° 3 (July 2021) . - pp 513 - 531 Titre : Constrained shortest path problems in bi-colored graphs: a label-setting approach Type de document : Article/Communication Auteurs : Amin AliAbdi, Auteur ; Ali Mohades, Auteur ; Mansoor Davoodi, Auteur Année de publication : 2021 Article en page(s) : pp 513 - 531 Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Géomatique [Termes IGN] calcul d'itinéraire [Termes IGN] chemin le plus court, algorithme du [Termes IGN] données d'entrainement sans étiquette [Termes IGN] graphe [Termes IGN] programmation par contraintes Résumé : (auteur) Definition of an optimal path in the real-world routing problems is not necessarily the shortest one, because parameters such as travel time, safety, quality, and smoothness also played essential roles in the definition of optimality. In this paper, we use bi-colored graphs for modeling urban and heterogeneous environments and introduce variations of constraint routing problems. Bi-colored graphs are a kind of directed graphs whose vertices are divided into two subsets of white and gray. We consider two criteria, minimizing the length and minimizing the number of gray vertices and present two problems called gray vertices bounded shortest path problem and length bounded shortest path problem on bi-colored graphs. We propose an efficient time label-setting algorithm to solve these problems. Likewise, we simulate the algorithm and compare it with the related path planning methods on random graphs as well as real-world environments. The simulation results show the efficiency of the proposed algorithm. Numéro de notice : A2021-974 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article DOI : 10.1007/s10707-019-00385-8 Date de publication en ligne : 03/12/2019 En ligne : https://doi.org/10.1007/s10707-019-00385-8 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=100393 [article]