Descripteur
Termes IGN > mathématiques > algorithmique > calcul d'itinéraire > chemin le plus court, algorithme du
chemin le plus court, algorithme duSynonyme(s)algorithme de Dijkstra |
Documents disponibles dans cette catégorie (36)
Ajouter le résultat dans votre panier
Visionner les documents numériques
Affiner la recherche Interroger des sources externes
Etendre la recherche sur niveau(x) vers le bas
Crowdsourcing a cyclist perspective on suggested recreational paths in real-world networks / Kevin Baker in Cartography and Geographic Information Science, Vol 44 n° 5 (September 2017)
[article]
Titre : Crowdsourcing a cyclist perspective on suggested recreational paths in real-world networks Type de document : Article/Communication Auteurs : Kevin Baker, Auteur ; Kristien Ooms, Auteur ; Steven Verstockt, Auteur ; et al., Auteur Année de publication : 2017 Article en page(s) : pp 422 - 435 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Géomatique web
[Termes IGN] carte thématique
[Termes IGN] chemin le plus court, algorithme du
[Termes IGN] cycliste
[Termes IGN] données localisées des bénévoles
[Termes IGN] géomatique web
[Termes IGN] itinéraire
[Termes IGN] loisir
[Termes IGN] production participative
[Termes IGN] trace GPSRésumé : (Auteur) Routing and navigation services for leisure activities are conditioned by special needs and trade-offs. The advent of online communities and large crowdsourced datasets offers opportunities to improve the adoption of a user’s perspective in these suggested paths. This paper focuses on achieving two goals. First, the presented methodology analyses a dataset of 190,610 historical GPS traces to gain insights into the appreciation or attractiveness of each edge in a real-world network for a specific leisure activity (i.e. road cycling). Second, as literature on these leisure activities is still sparse, we want to create a thorough understanding of the activities at hand for future work. An appreciation model is proposed and the spread of this score is analyzed in shortest-path alternatives of popular routing engines for this activity. This analysis successfully discriminates these shortest paths based on the scoring value and three morphological parameters of the path. However, the robustness of the model should be improved to ensure the viability of the proposed approach in future work. More specifically, further research on the local optimality of the route choices will be imperative. Numéro de notice : A2017-449 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article DOI : 10.1080/15230406.2016.1192486 En ligne : http://dx.doi.org/10.1080/15230406.2016.1192486 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=86359
in Cartography and Geographic Information Science > Vol 44 n° 5 (September 2017) . - pp 422 - 435[article]Réservation
Réserver ce documentExemplaires (1)
Code-barres Cote Support Localisation Section Disponibilité 032-2017051 RAB Revue Centre de documentation En réserve L003 Disponible Seamline determination for high resolution orthoimage mosaicking using watershed segmentation / Wang Mi in Photogrammetric Engineering & Remote Sensing, PERS, vol 82 n° 2 (February 2016)
[article]
Titre : Seamline determination for high resolution orthoimage mosaicking using watershed segmentation Type de document : Article/Communication Auteurs : Wang Mi, Auteur ; Yuan Shenggu, Auteur ; Pan Jun, Auteur Année de publication : 2016 Article en page(s) : pp 121 - 133 Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Traitement d'image optique
[Termes IGN] chemin le plus court, algorithme du
[Termes IGN] classification pixellaire
[Termes IGN] coefficient de corrélation
[Termes IGN] extraction de traits caractéristiques
[Termes IGN] image aérienne
[Termes IGN] mosaïquage d'images
[Termes IGN] orthoimage
[Termes IGN] orthophotoplan numérique
[Termes IGN] raccord d'images
[Termes IGN] segmentation d'image
[Termes IGN] zone d'intérêtRésumé : (auteur) Image mosaicking is a process during which multiple orthoimages are combined into a single seamless composite orthoimage. One of the most difficult steps in the automatic mosaicking of orthoimages is the seamline determination. This paper presents a novel algorithm that selects seamlines based on marker-based watershed segmentation. A representative seamline is extracted at the object level and the pixel level as follows. First, a watershed segmentation is performed to obtain the objects. To avoid over-segmentation, a regional adaptive marker-based watershed segmentation is proposed. Second, the object difference estimated by the correlation coefficient of each object is calculated, and the region adjacency matrix is built. Third, a technique for minimizing the maximum object cost is adopted to determine the objects through which the seamlines pass. Finally, pixel-level optimization is performed using Dijkstra's algorithm with a binary min-heap to determine the final seamlines. The experimental results on digital aerial orthoimages in different areas demonstrate the feasibility and effectiveness of the proposed method compared with other algorithms. Numéro de notice : A2016-055 Affiliation des auteurs : non IGN Thématique : IMAGERIE Nature : Article DOI : 10.14358/PERS.82.2.121 En ligne : https://doi.org/10.14358/PERS.82.2.121 Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=79656
in Photogrammetric Engineering & Remote Sensing, PERS > vol 82 n° 2 (February 2016) . - pp 121 - 133[article]SPLZ: An efficient algorithm for single source shortest path problem using compression method / Jingwei Sun in Geoinformatica, vol 20 n° 1 (January - March 2016)
[article]
Titre : SPLZ: An efficient algorithm for single source shortest path problem using compression method Type de document : Article/Communication Auteurs : Jingwei Sun, Auteur ; Guangzhong Sun, Auteur Année de publication : 2016 Article en page(s) : pp 1 - 18 Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Géomatique
[Termes IGN] chemin le plus court, algorithme du
[Termes IGN] compression de données
[Termes IGN] réseau routier
[Termes IGN] traitement de données localiséesRésumé : (auteur) Efficient solution of the single source shortest path (SSSP) problem on road networks is an important requirement for numerous real-world applications. This paper introduces an algorithm for the SSSP problem using compression method. Owning to precomputing and storing all-pairs shortest path (APSP), the process of solving SSSP problem is a simple lookup of a little data from precomputed APSP and decompression. APSP without compression needs at least 1TB memory for a road network with one million vertices. Our algorithm can compress such an APSP into several GB, and ensure a good performance of decompression. In our experiment on a dataset about Northwest USA (with 1.2 millions vertices), our method can achieve about three orders of magnitude faster than Dijkstra algorithm based on binary heap. Numéro de notice : A2016-365 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article DOI : 10.1007/s10707-015-0229-7 En ligne : http://dx.doi.org/10.1007/s10707-015-0229-7 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=81128
in Geoinformatica > vol 20 n° 1 (January - March 2016) . - pp 1 - 18[article]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)
[article]
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éesRé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
in Transactions in GIS > vol 19 n° 6 (December 2015) . - pp 915 - 929[article]A dilution-matching-encoding compaction of trajectories over road networks / Ranit Gotsman in Geoinformatica, vol 19 n° 2 (April - June 2015)
[article]
Titre : A dilution-matching-encoding compaction of trajectories over road networks Type de document : Article/Communication Auteurs : Ranit Gotsman, Auteur ; Yaron Kanza, Auteur Année de publication : 2015 Article en page(s) : pp 331-364 Note générale : bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Géomatique web
[Termes IGN] calcul d'itinéraire
[Termes IGN] chemin le plus court, algorithme du
[Termes IGN] géocodage
[Termes IGN] noeud
[Termes IGN] positionnement par GPS
[Termes IGN] réseau routier
[Termes IGN] stockage de données
[Termes IGN] vectorisationRésumé : (auteur) Many devices nowadays record traveled routes as sequences of GPS locations. With the growing popularity of smartphones, millions of such routes are generated each day, and many routes have to be stored locally on the device or transmitted to a remote database. It is, thus, essential to encode the sequences, in order to decrease the volume of the stored or transmitted data. In this paper we study the problem of encoding routes over a vectorial road network (map), where GPS locations can be associated with vertices or with road segments. We consider a three-step process of dilution, map-matching and coding, which helps reducing the amount of transmitted data between the cellular device and remote servers. We present two methods to code routes. The first method represents the given route as a sequence of greedy paths. We provide two algorithms to generate a greedy-path code for a sequence of n vertices on the map. The first algorithm has O(n) time complexity, and the second one has O(n 2) time complexity, but it is optimal, meaning that it generates the shortest possible greedy-path code. Decoding a greedy-path code can be done in O(n) time. The second method encodes a route as a sequence of shortest paths. We provide algorithms to generate unidirectional and bidirectional optimal shortest-path codes. Encoding and decoding a shortest-path code can be done in O(k n 2 logn) time, where k is the length of the produced code, assuming the graph valency is bounded. Our experimental evaluation shows that shortest-path codes are more compact than greedy-path codes, justifying the larger time complexity. Numéro de notice : A2015-491 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE Nature : Article DOI : 10.1007/s10707-014-0216-4 Date de publication en ligne : 11/08/2014 En ligne : https://doi.org/10.1007/s10707-014-0216-4 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=77284
in Geoinformatica > vol 19 n° 2 (April - June 2015) . - pp 331-364[article]Algorithms for vision-based path following along previously taught paths / Deon George Sabatta (2015)PermalinkUrban network analysis: Centrality, sinuosity and shortcut detection / Theophile Emmanouilidis in Revue internationale de géomatique, vol 23 n° 3 - 4 (septembre 2013 - février 2014)PermalinkAnt intelligence for solving optimal path-covering problems with multi-objectives / X. Li in International journal of geographical information science IJGIS, vol 23 n° 7-8 (july 2009)PermalinkOn A* search with stopover areas / T. Sander in International journal of geographical information science IJGIS, vol 23 n° 6 (june 2009)PermalinkFinding shortest paths on real road networks: the case for A* / W. Zeng in International journal of geographical information science IJGIS, vol 23 n°3-4 (march - april 2009)PermalinkA shortest path algorithm with novel heuristics for dynamic transportation networks / B. Huang in International journal of geographical information science IJGIS, vol 21 n° 6-7 (july 2007)PermalinkEffets spatiaux et effets réseau dans l’évaluation d’indicateurs sur les nœuds d’un réseau d’infrastructure / Jean-François Gleyze in Cybergeo, European journal of geography, n° 2007 ([01/01/2007])PermalinkLa vulnérabilité structurelle des réseaux de transport dans un contexte de risques, Volume 1. Volume principal / Jean-François Gleyze (2005)PermalinkLa vulnérabilité structurelle des réseaux de transport dans un contexte de risques, Volume 2. Annexes / Jean-François Gleyze (2005)PermalinkFonctionnalité du réseau de métro parisien : Efficacité et fiabilité du réseau de métro parisien dans l'éventualité des catastrophes / Jean-François Gleyze (2003)Permalink