Centre dedocumentation
scientifique

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

Public [article]  inGeoinformatica [en ligne] > 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]

A framework to manage uncertainty in the computation of waste collection routes after a flood / Arnaud Le Guilcher in ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, vol V-4-2021 (July 2021)  

Public [article]  inISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences > vol V-4-2021 (July 2021) . - pp 61 - 68 Titre : A framework to manage uncertainty in the computation of waste collection routes after a flood Type de document : Article/Communication Auteurs : Arnaud Le Guilcher , Auteur ; Sofiane Martel, Auteur ; Mickaël Brasebin , Auteur ; Yann Méneroux , Auteur Année de publication : 2021 Projets : 1-Pas de projet / Conférence : ISPRS 2021, Commission 4, 24th ISPRS Congress, Imaging today foreseeing tomorrow 05/07/2021 09/07/2021 Nice on-line France OA Annals Commission 4 Article en page(s) : pp 61 - 68 Note générale : biblographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Géomatique [Termes IGN] cadre conceptuel [Termes IGN] calcul d'itinéraire [Termes IGN] catastrophe naturelle [Termes IGN] collecte des déchets [Termes IGN] discrétisation spatiale [Termes IGN] incertitude géométrique [Termes IGN] inondation [Termes IGN] programmation stochastique [Termes IGN] variable aléatoire Résumé : (auteur) In this paper, we describe a framework to find a good quality waste collection tour after a flood, without having to solve a complicated optimization problem from scratch in limited time. We model the computation of a waste collection tour as a capacitated routing problem, on the vertices or on the edges of a graph, with uncertain waste quantities and uncertain road availability. Multiple models have been conceived to manage uncertainty in routing problems, and we build on the ideas of discretizing the uncertain parameters and computing master solutions that can be adapted to propose an original method to compute efficient solutions. We first introduce our model for the progressive removal of the uncertainty, then outline our method to compute solutions: our method first considers a low-dimensional set of random variables that govern the behaviour of the problem parameters, discretizes these variables and computes a solution for each discrete point before the flood, and then uses these solutions as a basis to build operational solutions when there are enough information about the parameters of the routing problem. We then give computational tools to implement this method. We give a framework to compute the basis of solutions in an efficient way, by computing all the solutions simultaneously and sharing information (that can lead to good quality solutions) between the different problems based on how close their parameters are, and we also describe how real solutions can be derived from this basis. Our main contributions are our model for the progressive removal of uncertainty, our multi-step method to compute efficient solutions, and our intrusive framework to compute solutions on the discrete grid of parameters. Numéro de notice : A2021-316 Affiliation des auteurs : UGE-LASTIG (2020- ) Thématique : GEOMATIQUE Nature : Article nature-HAL : ArtAvecCL-RevueIntern DOI : 10.5194/isprs-annals-V-4-2021-61-2021 En ligne : https://doi.org/10.5194/isprs-annals-V-4-2021-61-2021 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=97946 [article]

PgRouting : des fonctions de graphe pour PostGreSQL et POstGIS / Anonyme in Géomatique expert, n° 134 (avril 2021)

Public [article]  inGéomatique expert > n° 134 (avril 2021) . - pp 34 - 41 Titre : PgRouting : des fonctions de graphe pour PostGreSQL et POstGIS Type de document : Article/Communication Auteurs : Anonyme, Auteur Année de publication : 2021 Article en page(s) : pp 34 - 41 Langues : Français (fre) Descripteur : [Vedettes matières IGN] Systèmes d'information géographique [Termes IGN] chemin le plus court, algorithme du [Termes IGN] PostGIS [Termes IGN] PostgreSQL Résumé : (auteur) Extension relativement peu connue du duo PostGreSQL/POstGIS, PgRouting enrichit la base de données avec des fonctions destinées à opérer sur des graphes : on pourra ainsi s'en servir pour calculer des plus courts chemins ou bien résoudre des problèmes de logistique. Numéro de notice : A2021-902 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article DOI : sans Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=99195 [article]

Exemplaires (1)

Code-barres	Cote	Support	Localisation	Section	Disponibilité
IFN-001-P00263	PER	Revue	Nogent-sur-Vernisson	Salle périodiques	Exclu du prêt

A trajectory restoration algorithm for low-sampling-rate floating car data and complex urban road networks / Bozhao Li in International journal of geographical information science IJGIS, vol 35 n° 4 (April 2021)  

Public [article]  inInternational journal of geographical information science IJGIS > vol 35 n° 4 (April 2021) . - pp 717 - 740 Titre : A trajectory restoration algorithm for low-sampling-rate floating car data and complex urban road networks Type de document : Article/Communication Auteurs : Bozhao Li, Auteur ; Zhongliang Cai, Auteur ; Mengjun Kang, Auteur ; et al., Auteur Année de publication : 2021 Article en page(s) : pp 717 - 740 Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Analyse spatiale [Termes IGN] appariement de cartes [Termes IGN] chemin le plus court, algorithme du [Termes IGN] Pékin (Chine) [Termes IGN] réseau routier [Termes IGN] taux d'échantillonnage [Termes IGN] trafic routier [Termes IGN] trajectoire (véhicule non spatial) [Termes IGN] zone urbaine Résumé : (auteur) Low-sampling-rate floating car data (FCD) are more challenging than those with high-sampling-rate FCD for map matching (MM) algorithms. Some MM algorithms for low-sampling-rate FCD lack sufficient efficiency nor accuracy, especially related to complex urban road networks. This paper proposes a new method named the trajectory restoration algorithm, which is based on geometry MM algorithms to ensure efficiency and accuracy. The proposed algorithm adopts the modified A* shortest path algorithm to reduce the number of function calls and fully considers road network topology and historical matched points to improve its accuracy. We test the efficiency and accuracy of the trajectory restoration algorithm with FCD data for the complex urban road networks in Beijing. The results have strong continuity which greatly improves the utilization of FCD. We show that the proposed algorithm outperforms related MM methods in efficiency and accuracy and its robustness to restore trajectories of both high and low sampling rates in complex urban road networks. Numéro de notice : A2021-269 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article DOI : 10.1080/13658816.2020.1825721 Date de publication en ligne : 20/10/2020 En ligne : https://doi.org/10.1080/13658816.2020.1825721 Format de la ressource électronique : url article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=97326 [article]

Finding the most navigable path in road networks / Ramneek Kaur in Geoinformatica [en ligne], vol 25 n° 1 (January 2021)  

Public [article]  inGeoinformatica [en ligne] > vol 25 n° 1 (January 2021) . - pp 207 - 240 Titre : Finding the most navigable path in road networks Type de document : Article/Communication Auteurs : Ramneek Kaur, Auteur ; Vikram Goyal, Auteur ; Venkata M. V. Gunturi, Auteur Année de publication : 2021 Article en page(s) : pp 207 - 240 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Analyse spatiale [Termes IGN] arc [Termes IGN] calcul d'itinéraire [Termes IGN] durée de trajet [Termes IGN] programmation dynamique [Termes IGN] réseau routier Résumé : (Auteur) Input to the Most Navigable Path (MNP) problem consists of the following: (a) a road network represented as a directed graph, where each edge is associated with numeric attributes of cost and “navigability score” values; (b) a source and a destination and; (c) a budget value which denotes the maximum permissible cost of the solution. Given the input, MNP aims to determine a path between the source and the destination which maximizes the navigability score while constraining its cost to be within the given budget value. The problem can be modeled as the arc orienteering problem which is known to be NP-hard. The current state-of-the-art for this problem may generate paths having loops, and its adaptation for MNP that yields simple paths, was found to be inefficient. In this paper, we propose five novel algorithms for the MNP problem. Our algorithms first compute a seed path from the source to the destination, and then modify the seed path to improve its navigability. We explore two approaches to compute the seed path. For modification of the seed path, we explore different Dynamic Programming based approaches. We also propose an indexing structure for the MNP problem which helps in reducing the running time of some of our algorithms. Our experimental results indicate that the proposed solutions yield comparable or better solutions while being orders of magnitude faster than the current state-of-the-art for large real road networks. Numéro de notice : A2021-095 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article nature-HAL : ArtAvecCL-RevueIntern DOI : 10.1007/s10707-020-00428-5 Date de publication en ligne : 03/01/2021 En ligne : https://doi.org/10.1007/s10707-020-00428-5 Format de la ressource électronique : URL Article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=96935 [article]

Introducing diversion graph for real-time spatial data analysis with location based social networks / Sameera Kannangara (2021)  

Permalink

Machine learning for the distributed and dynamic management of a fleet of taxis and autonomous shuttles / Tatiana Babicheva (2021)  

Permalink

Route intersection reduction with connected autonomous vehicles / Sadegh Motallebi in Geoinformatica [en ligne], vol 25 n° 1 (January 2021)  

Permalink

Automated labeling of schematic maps by optimization with knowledge acquired from existing maps / Tian Lan in Transactions in GIS, Vol 24 n° 6 (December 2020)  

Permalink

Les stations virtuelles au service de la cartographie mobile / Mathieu Regul in XYZ, n° 165 (décembre 2020)

Permalink

Generation of crowd arrival and destination locations/times in complex transit facilities / Brian Ricks in The Visual Computer, vol 36 n° 8 (August 2020)  

Permalink

Evaluating the impact of visualization of risk upon emergency route-planning / Lisa Cheong in International journal of geographical information science IJGIS, vol 34 n° 5 (May 2020)  

Permalink

The "Incense Road" from Petra to Gaza: an analysis using GIS and Cost functions / Motti Zohar in International journal of geographical information science IJGIS, vol 34 n° 2 (February 2020)  

Permalink

SMSM: a similarity measure for trajectory stops and moves / Andre L. Lehmann in International journal of geographical information science IJGIS, vol 33 n° 9 (September 2019)  

Permalink

Analyse spatiotemporelle des tournées de livraison d’une entreprise de livraison à domicile / Khaled Belhassine in Revue internationale de géomatique, vol 29 n° 2 (avril - juin 2019)  

Permalink