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 (35)
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
A 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)
[article]
Titre : A shortest path algorithm with novel heuristics for dynamic transportation networks Type de document : Article/Communication Auteurs : B. Huang, Auteur ; Q. Wu, Auteur ; F.B. Zhan, Auteur Année de publication : 2007 Article en page(s) : pp 625 - 644 Note générale : Bibliographie Langues : Anglais (eng) Descripteur : [Vedettes matières IGN] Bases de données localisées
[Termes IGN] chemin le plus court, algorithme du
[Termes IGN] méthode heuristique
[Termes IGN] réseau routier
[Termes IGN] trafic routierRésumé : (Auteur) Finding an optimal route in dynamic real-time transportation networks is a critical problem for vehicle navigation. Existing approaches are either too complex or incapable of managing complex circumstances where both the location of a mobile object and traffic conditions change over time. In this paper, we propose an incremental search approach with novel heuristics based on a variation of the A* algorithm-Lifelong Planning A*. In addition, we suggest using an ellipse to prune the unnecessary nodes to be scanned in order to speed up the dynamic search process. The proposed algorithm determines the shortest-cost path between a moving object and its destination by continually adapting to the dynamic traffic conditions, while making use of the previous search results. Experimental results evince that the proposed algorithm performs significantly better than the well-known A* algorithm. Copyright Taylor & Francis Numéro de notice : A2007-263 Affiliation des auteurs : non IGN Thématique : GEOMATIQUE/INFORMATIQUE Nature : Article DOI : 10.1080/13658810601079759 En ligne : https://doi.org/10.1080/13658810601079759 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=28626
in International journal of geographical information science IJGIS > vol 21 n° 6-7 (july 2007) . - pp 625 - 644[article]Réservation
Réserver ce documentExemplaires(2)
Code-barres Cote Support Localisation Section Disponibilité 079-07041 RAB Revue Centre de documentation En réserve L003 Disponible 079-07042 RAB Revue Centre de documentation En réserve L003 Disponible Effets 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])
[article]
Titre : Effets spatiaux et effets réseau dans l’évaluation d’indicateurs sur les nœuds d’un réseau d’infrastructure Titre original : Making allowances for spatial and network effects when assessing indicators on infrastructure network nodes Type de document : Article/Communication Auteurs : Jean-François Gleyze , Auteur Année de publication : 2007 Article en page(s) : n° 370 Note générale : bibliographie Langues : Français (fre) Anglais (eng) Descripteur : [Vedettes matières IGN] Analyse spatiale
[Termes IGN] accessibilité
[Termes IGN] chemin le plus court, algorithme du
[Termes IGN] graphe
[Termes IGN] réseau de transport
[Termes IGN] théorie des graphes
[Termes IGN] triangulation de DelaunayRésumé : (auteur) The quantitative study of an infrastructure network in geography often consists in assessing indicators on the network components (nodes and sections). In that respect, the network is modelled by a graph whose vertices and edges respectively correspond to the nodal and linear network infrastructures. Then, such a graph can be studied thanks to tools provided by the graph theory and mainly based on the shortest paths features. The most typical indicators are accessibility (closeness from a given vertex to the others graph vertices, computed in summarizing the shortest path lengths) and centrality or “betweenness” (contribution of a given vertex or edge to the origin-destination paths, computed in counting the shortest paths passing through this component). For this reason, accessibility and centrality features of a vertex depend on the shortest paths distribution on the network, and also on the relative location of the vertex inside the network.
However, the spatial location of vertices predisposes them to be accessible and central, regardless of the relational potentialities provided by the network structure. Actually, a vertex located at the centre (resp. on the periphery) of the network area is more (resp. less) likely to be accessible and central. Therefore, it seems relevant to highlight how the network makes the vertices accessible and central, independently on the advantages only provided by their spatial location. Then, we show that it is possible to make allowances for the corresponding “network and spatial effects” by comparing the shortest paths traditionnally taken into account to compute these indicators with a set of optimal paths called “Delaunay paths”. Besides the study of accessibility and centrality indicators, our method can be extended to the study of any indicator (structural or not), as long as such an indicator is usually computed from shortest paths. It finally provides a useful tool to interpret indicators on a network and to understand the networks contribution to the phenomena described by these indicators.Numéro de notice : A2007-109 Affiliation des auteurs : COGIT (1988-2011) Thématique : GEOMATIQUE Nature : Article nature-HAL : ArtAvecCL-RevueIntern DOI : 10.4000/cybergeo.5532 En ligne : https://doi.org/10.4000/cybergeo.5532 Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=101424
in Cybergeo, European journal of geography > n° 2007 [01/01/2007] . - n° 370[article]La vulnérabilité structurelle des réseaux de transport dans un contexte de risques, Volume 1. Volume principal / Jean-François Gleyze (2005)
Titre de série : La vulnérabilité structurelle des réseaux de transport dans un contexte de risques, Volume 1 Titre : Volume principal Type de document : Thèse/HDR Auteurs : Jean-François Gleyze , Auteur ; Claude Grasland, Directeur de thèse Editeur : Paris : Université de Paris 7 Denis Diderot Année de publication : 2005 Importance : 539 p. Format : 21 x 30 cm Note générale : Bibliographie Langues : Français (fre) Descripteur : [Vedettes matières IGN] Analyse spatiale
[Termes IGN] analyse structurelle
[Termes IGN] chemin le plus court, algorithme du
[Termes IGN] diagramme de Voronoï
[Termes IGN] graphe
[Termes IGN] réseau de transport
[Termes IGN] réseau métropolitain
[Termes IGN] risque naturel
[Termes IGN] risque technologique
[Termes IGN] trame
[Termes IGN] triangulation de Delaunay
[Termes IGN] vulnérabilitéIndex. décimale : THESE Thèses et HDR Résumé : (Auteur) Les risques naturels et anthropiques font peser sur les territoires et les populations des menaces telles, qu’ils font l’objet de nombreuses études à but préventif. Une des manières de réduire le risque consiste à diminuer la vulnérabilité des enjeux exposés, c’est-à-dire à prévenir l’endommagement potentiel des entités soumises au risque. Parmi celles-ci, les réseaux de transport occupent une place particulière, car non seulement le risque constitue une menace matérielle (sur l’infrastructure), mais il met également en péril les fonctions assurées par les réseaux (l’usage) en dégradant les propriétés induites par leur structure (les potentialités relationnelles). Afin de comprendre et d’anticiper les perturbations fonctionnelles d’un réseau de transport menacé par des catastrophes, il est donc nécessaire de définir et d’évaluer la vulnérabilité de sa structure et d’en comprendre les mécanismes sous-jacents. Pour ce faire, nous aurons besoin préalablement de définir avec précision le cadre, les hypothèses, les choix de modélisation et les outils relatifs à l’étude de la structure des réseaux. Sur cette base, nous présenterons ensuite la définition traditionnelle de la vulnérabilité ainsi que les outils d’évaluation et de caractérisation associés, et nous en analyserons la portée et les limites. Nous proposerons enfin d’améliorer la compréhension de la vulnérabilité structurelle des réseaux en mettant en évidence et en caractérisant les propriétés de la trame explicatives des niveaux de vulnérabilité. L’ensemble des recherches seront éprouvées à travers l’étude de plusieurs réseaux réels, opérant à différentes échelles, et présentant, pour certains, des singularités intéressantes dans un contexte de risque (réseau de métro parisien, réseaux routiers orléanais, français et européen). Note de contenu : Introduction
A) DE LA NOTION DE RISQUE A LA NOTION DE VULNERABILITE STRUCTURELLE DES RESEAUX DE TRANSPORT
A.1 Risque, aléa et vulnérabilité
A.1.1 Qu'est-ce que le risque ?
A.1.2 La composante aléa, aspects probabilites du risque
A.1.3 La composatne vulnérabilité, aspects déterministes du risque
A.1.4 la déterminiation du niveau du risque
A.1.5 Synthèse, ouverture de recherche en géographie
A.2 les vulnérabilités des réseaux de transport
A.2.1 Risques et réseaux
A.2.2 De l'étude de l'impact des catastrophes sur les réseaux de transport
A.2.3 La question de la vulnérabilité structurelle des réseaux de transport
A.3 Evaluations et représentations de la vulnérabilité des réseaux de transport, les enjeux de la l'approche structurelle
A.3.1 L'approche traditionnelle des réseaux de transport et l'évaluation pratique des vulnérabilités associées
A.3.2 Entre réseau-support et réseau-service, le réseau-médiateur : l'approche structurelle des réseaux de transport
A.3.3 L'étude de la vulnérabilité structurelle des réseaux de transport : objectifs et démarche
B) L'ETUDE DES RESEAUX DE TRANSPORT D'UN POINT DE VUE STRUCTUREL
B.1 Cadre d'étude général : apports et limite de la théorie des graphes pour la formalisation des réseaux et de leur structure
B.1.1 La représeantion topologique d'un réseau par un graphe : généralités
B.1.2 L'intégration de la géométrie : géoréférencement, valuation et étiquetage
B.1.3 La description des caractéristiques relationnelles d'un réseau modélisé par un graphe : les plus courts chemins
B.1.4 Cycles, connexité et connectivité : quand la théorie des graphes se mêle de vulnérabilité
B.2 Concepts et outils spécifiques à l'étude structurelle des réseaux et de leurs potentialités relationnelles
B.2.1 La définition d'un réseau de référence pour faire la part des effets de l'implantation spatiale et des propriétés structurelles du réseau
B.2.2 L'élaboration d'une pondération robuste pour rendre le réseau insensible aux effets de la densité spatiale de ses sommets
B.2.3 Chemins et logiques relationnelles sur le réseau
B.2.4 L'échelle d'étude : principe des approches locale et globale
B.3 Présentation des réseaux étudiés
B.3.1 Le réseau de métro parisien intra-muros
B.3.2 Des réseaux routiers à différentes échelles
C) PROCESSUS DE L'ANALYSE DE LA VULNERABILITE STRUCTURELLE DES RESEAUX DE TRANSPORT
C.1 préalable : l'évaluation du rôle de médiateur d'un réseau dans une configuration donnée
C.1.1 Dans quelle mesure le réseau remplit-il son rôle de médiateur ? la notion d'efficacité
C.1.2 Comment le réeau est-il sollicité pour remplir son rôle de médiateur ? la notion de centralité intermédiaire
C.2 L'analyse théorique de la vulnérabilité d'un réseau par la comparaison de ses configurations normale et endommagée
C.2.1 Principes et fondements de l'analyse théorique de vulnérabilité
C.2.2 Quantifier et comprendre in extenso la vulnérabilité structurelle d'un réesau de transport
C.3 L'analyse pratique de la vulnérabilité d'un réseau par l'étude de scénarios d'endommagement
C.3.1 Les scénarios élémentaires
C.3.2 Les scénarios complexes
C.3.3 Les profils de vulnérabilité
C.4 Synthèse : apports et limite du processus d'analyse de vulnérabilité
D) AMELIORATION DE LA COMPREHENSION DE LA VULNERABILITE STRUCTURELLE D'UN RESEAU PAR L'EXAMEN DES FORCES ET DES FAIBLESSES DE SA TRAME
D.1 Améliorer la caractérisation de la vulnérabilité par l'examen de la configuration locale du réseau
D.1.1 La centralité intermédiaire : le facteur explicatif principal de la vulnérabilité
D.1.2 Analyse qualitative de la structure locale des réseaux
D.1.3 Analyse quantative de la structure locale des réseaux
D.2 Améliorer l'analyse de la vulnérabilité par l'examen des ressources relationnelles du réseau
D.2.1 Les plus courts chemins : le révélateur principal de l'organisation relationnelle du réseau
D.2.2 Les logiques de chemin de remplacement : identifier et quantifier les solutions alternatives aux plus courts chemins
D.2.3 La comparaison des plus courts chemins et des chemins de remplacement : les ressources relationnelles du réseau dans un contexte de risques
D.3 Synthèse : processus étendu de l'analyse de la vulnérabilité structurelle des réseaux de transport
ConclusionNuméro de notice : 23320A Affiliation des auteurs : COGIT (1988-2011) Thématique : GEOMATIQUE Nature : Thèse française Note de thèse : Thèse de doctorat : analyse théorique. épistémologique en géographie : Paris 7 : 2005 Organisme de stage : COGIT (IGN) nature-HAL : Thèse DOI : sans En ligne : https://hal.science/tel-00138991 Format de la ressource électronique : URL Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=45288 Voir aussiRéservation
Réserver ce documentExemplaires(1)
Code-barres Cote Support Localisation Section Disponibilité 23320-01A THESE Livre Centre de documentation Thèses Disponible La vulnérabilité structurelle des réseaux de transport dans un contexte de risques, Volume 2. Annexes / Jean-François Gleyze (2005)
Titre de série : La vulnérabilité structurelle des réseaux de transport dans un contexte de risques, Volume 2 Titre : Annexes Type de document : Thèse/HDR Auteurs : Jean-François Gleyze , Auteur ; Claude Grasland, Directeur de thèse Editeur : Champs-sur-Marne : Ecole nationale des sciences géographiques ENSG Année de publication : 2005 Importance : 300 p. Format : 21 x 30 cm Note générale : Bibliographie Langues : Français (fre) Descripteur : [Vedettes matières IGN] Analyse spatiale
[Termes IGN] chemin le plus court, algorithme du
[Termes IGN] crue
[Termes IGN] diagramme de Voronoï
[Termes IGN] dommage
[Termes IGN] graphe
[Termes IGN] Ile-de-France
[Termes IGN] réseau métropolitain
[Termes IGN] réseau routier
[Termes IGN] triangulation de DelaunayIndex. décimale : THESE Thèses et HDR Note de contenu : ANNEXE 1 : LES DOMMAGES LIES AUX CRUES SUR LE RESEAU ROUTIER DE LA REGION ILE-DE-FRANCE
1.1 : Contexte et objectifs de l'étude
- Première phase de 1 'étude- Deuxième phase de l'étude
1.2 : Méthodologie
- Cadre méthodologique : chronologie - Le modèle de trafic de l'IAURIF
1.3 : Application et résultats
- Scénarios testés - Identification des points de coupure potentielle - Analyse des arcs coupés- Simulation de trafic en situation perturbée - Résultats
ANNEXE 2 : STRUCTURE DES DONNEES
2.1 : Matrice d'incidence - Champ " incidence "
2.2 : Matrice d'adjacence - Champ " adjacence "
2.3 : Table descriptive de ta structure des arêtes - Champ " infoarc "
2.4 : Table descriptive de la situation topologique des sommets au sein du graphe Champ " infosommet "
2.5 : Matrice des coordonnées des sommets du graphe - Champ " coordonnées "
2.6 : Vecteur des vatuations des arêtes du graphe - Champ " vatuation "
2.7 : Vecteur des poids des sommets du graphe - Champ " poids"
2.8 : Table des relations considérées sur te graphe - Champ " relation "
2.9 : Table des plus courts chemins - Champ " pcc "
2.10 : Matrice d'équivalence et matrice de transition entre tes arêtes du graphe d'étude et les arêtes de la triangutation de Delaunay construite sur son semis de sommets - Champs " doublure " et " resumearc "
2.11 : Matrices d'incidence relations - arêtes / sommets - Champs " transit-arêtes " et " transit-sommets "
ANNEXE 3 : AUTRES RESEAUX ABORDES
3.1 : Des graphes théoriques simples pour ta mise en évidence de structures remarquables élémentaires
3.2 : Des réseaux géographiques simples pour éprouver ta portée des outils d'analyse structurelle des réseaux
- Le réseau fluvial des villes russes au Moyen-Âge ([PITTS, 19651, [PITTS, 19791)
- Les réseaux routiers des villes américaines d'Indianapolis et de Columbus (Ohio) en 1954 et en 1965 ([MURACO, 19721)
- Le réseau routier simplifié des villes françaises ([GLEYZE, 2001 (c)]
ANNEXE 4 : GRAPHES ET ALGEBRE - APPLICATIONS AUX CALCULS SUR LES RESEAUX ELECTRIQUES
4 1 : Fondements algébriques de la théorie des graphes
4.2 : Application de ta théorie des graphes à t'étude des réseaux électriques
- Rappels d'électricité
- Modélisation d'un réseau électrique par la théorie des graphes
ANNEXE 5 : DETERMINATION DU (DES) PLUS COURT(S) CHEMIN(S) ENTRE LES PAIRES DE SOMMETS D'UN GRAPHE
5.1 : Principe de l'algorithme
5.2 : Données requises
5.3 : Initia(isation de t'algorithme
5.4 : Passage de l'étape (p-1) à l'étape p
5.5 : Fin de l'algorithme et résultat
ANNEXE 6 : LE CALCUL COMBINE DES PLUS COURTS CHEMINS ET DE LA CENTRALITE INTERMEDIAIRE SUR UN GRAPHE VALUE
6.1 : L'indice de centralité intermédiaire
6.2 : Principe de t'algorithme
6.3 : Description de t'algorithme
6.4 : Codage
ANNEXE 7 : DIAGRAMME DE VORONOÏ ET TRIANGULATION DE DELAUNAY
7.1 : Diagramme de Vorondf d'un semis de sommets et surface des cellules associées
- Principe du diagramme de Voronoï et des cellules associées
- Calcul des surfaces des cellules d'un diagramme de Voronaï construit sur un semis de sommets donnés
- Modification de la surface des cellules de Voronoïpar ajout ou suppression d'un sommet au semis initial
7.2 : Triangutation de Delaunay sur un semis de sommets et évolution de la triangutation par ajout ou suppression de sommets
- Propriétés de la triangulation de Delaunay dans un contexte d'analyse spatiale
- Ajout d'un sommet à une triangulation existante
- Construction de la triangulation de Delaunay sur un semis quelconque de sommets
- Suppression d'un sommet appartenant à un semis triangulé
ANNEXE 8 : PLUS COURTS CHEMINS SUR UNE TRIANGULATION DE DELAUNAY
8 1 : Plus court chemin entre deux sommets quelconques sur une triangutation de Delaunay
8.2 : Chemin de Delaunay entre deux sommets quelconques sur une triangutation de Delaunay
8.3 : Calcul du chemin de Delaunay entre deux sommets d'un semis
ANNEXE 9 : OUTILS MATHEMATIQUES D'ANALYSE SPATIALE
9.1 : Caractérisation du cercle circonscrit à un triangte
9.2 : Calcul de ta surface d'un polygone
9.3 : Situation d'un point relativement à une surface polygonale
9.4 : Tirage au hasard d'un point au sein d'une surface potygonate
9.5 : Enveloppe convexe d'un semis de points
9.6 : Orientation moyenne d'un ensemble de segments, d'un contour ou d'un faisceau de directions
ANNEXE 10 : RESULTATS OBTENUS SUR LES AUTRES RESEAUX D'ETUDE ET RESULTATS COMPLEMENTAIRES SUR LE RESEAU DE METRO PARISIEN
10 1 : Résultats obtenus sur te réseau routier orléanais
10.2 : Résultats obtenus sur te réseau routier français
10.3 : Résultats obtenus sur te réseau routier européen
10.4 : Résultats obtenus sur tes réseaux réguliers
10.5 : Résultats obtenus sur te réseau fluvial des vittes russes au Moyen-Âge
10.6 : Résultats obtenus sur te réseau routier de ta ville d'indianapotis
10.7 : Résultats obtenus sur te réseau routier de ta ville de Cotumbus
10.8 : Résultats obtenus sur te réseau routier français simptifié
10.9 : Résultats complémentaires sur te réseau de métro et de RER de Paris intramurosNuméro de notice : 23320B Affiliation des auteurs : COGIT (1988-2011) Thématique : GEOMATIQUE Nature : Thèse française Note de thèse : Thèse de doctorat : analyse théorique. épistémologique en géographie : Paris 7 : 2005 Organisme de stage : COGIT (IGN) nature-HAL : Thèse DOI : sans En ligne : https://hal.science/tel-00138991 Format de la ressource électronique : URL Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=45289 Voir aussiRéservation
Réserver ce documentExemplaires(1)
Code-barres Cote Support Localisation Section Disponibilité 23320-01B THESE Livre Centre de documentation Thèses Disponible Fonctionnalité 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)
contenu dans Sixièmes rencontres de Théo Quant : les rencontres, Besançon, 2003 / Cécile Tannier (2003)
Titre : Fonctionnalité du réseau de métro parisien : Efficacité et fiabilité du réseau de métro parisien dans l'éventualité des catastrophes Type de document : Article/Communication Auteurs : Jean-François Gleyze , Auteur Editeur : Paris : Institut Géographique National - IGN (1940-2007) Année de publication : 2003 Conférence : Théo Quant 2003, 6es rencontres de Théo Quant, colloquium on theorical and quantitative geography 20/02/2003 21/02/2003 Besançon France OA Abstracts only Importance : 13 p. Note générale : bibliographie Langues : Français (fre) Descripteur : [Vedettes matières IGN] Analyse spatiale
[Termes IGN] chemin le plus court, algorithme du
[Termes IGN] efficacité
[Termes IGN] graphe
[Termes IGN] Paris (75)
[Termes IGN] prévention des risques
[Termes IGN] recherche du chemin optimal, algorithme de
[Termes IGN] réseau métropolitain
[Termes IGN] risque urbainRésumé : (auteur) Les catastrophes naturelles et anthropiques menacent d’endommager les réseaux de transport, non seulement de manière structurelle, mais également de manière fonctionnelle en provoquant des perturbations par le jeu des déviations. Dans ce contexte, nous avons choisi d’étudier le fonctionnement du réseau de métro parisien en mode normal et en mode endommagé. Dans un premier temps, nous définissons et quantifions l’efficacité du réseau pour le rôle qui lui est assigné. Nous caractérisons ensuite le rôle fonctionnel des différentes composantes du réseau en mode de fonctionnement normal. En regard de cette étude, nous considérons enfin l’éventualité de catastrophes et étudions les potentialités du réseau en termes de chemins alternatifs, d’une part, à l’aide d’un indice synthétique issu de la recherche sur les transports, d’autre part, dans le contexte de scénarios d’endommagement précis. Les conclusions de ce travail éclairent la compréhension du fonctionnement du réseau dans une logique de prévention de risques. Numéro de notice : C2003-036 Affiliation des auteurs : COGIT (1988-2011) Thématique : GEOMATIQUE/URBANISME Nature : Communication nature-HAL : ComAvecCL&ActesPubliésNat DOI : sans En ligne : http://thema.univ-fcomte.fr/theoq/pdf/2003/TQ2003%20ARTICLE%2040.pdf Format de la ressource électronique : URL article Permalink : https://documentation.ensg.eu/index.php?lvl=notice_display&id=84908 Documents numériques
en open access
Fonctionnalité du réseau de métro parisienAdobe Acrobat PDF Routing in graphs with forbidden paths / Dieter Fritsch in GIS Geo-Informations-Systeme, vol 2002 n° 6 (Juni 2002)PermalinkDetection of urban structures in SAR images by robust fuzzy clustering algorithms: the example of street tracking / F. Dell'acqua in IEEE Transactions on geoscience and remote sensing, vol 39 n° 10 (October 2001)PermalinkAdvances in spatial data bases, 5th International Symposium, SSD '97, Berlin, Germany, July 15-18 1997 / Agnès Voisard (1997)Permalink