| dbo:abstract
|
- In computer science, the method of contraction hierarchies is a speed-up technique for finding the shortest-path in a graph. The most intuitive applications are car-navigation systems: a user wants to drive from to using the quickest possible route. The metric optimized here is the travel time. Intersections are represented by vertices, the road sections connecting them by edges. The edge weights represent the time it takes to drive along this segment of the road. A path from to is a sequence of edges (road sections); the shortest path is the one with the minimal sum of edge weights among all possible paths. The shortest path in a graph can be computed using Dijkstra's algorithm but, given that road networks consist of tens of millions of vertices, this is impractical. Contraction hierarchies is a speed-up method optimized to exploit properties of graphs representing road networks. The speed-up is achieved by creating shortcuts in a preprocessing phase which are then used during a shortest-path query to skip over "unimportant" vertices. This is based on the observation that road networks are highly hierarchical. Some intersections, for example highway junctions, are "more important" and higher up in the hierarchy than for example a junction leading into a dead end. Shortcuts can be used to save the precomputed distance between two important junctions such that the algorithm doesn't have to consider the full path between these junctions at query time. Contraction hierarchies do not know about which roads humans consider "important" (e.g. highways), but they are provided with the graph as input and are able to assign importance to vertices using heuristics. Contraction hierarchies are not only applied to speed-up algorithms in car-navigation systems but also in web-based route planners, traffic simulation, and logistics optimization. Implementations of the algorithm are publicly available as open source software. (en)
- En mathématiques appliquées, la méthode des contractions hiérarchiques est une technique destinée à réduire le temps de calcul du plus court chemin grâce à la construction d'une représentation dite "contractée" du graphe initial sur laquelle sont exécutés des algorithmes adaptés aux recherches sur structure multi-niveaux. Les temps de calcul d’itinéraire issus de cette méthode peuvent être drastiquement plus rapides que l'algorithme de Dijkstra et surpasser de plus anciennes méthodes d'optimisation telles que les Highway Hierarchies. Elle a été proposée en 2008 par Robert Geisberger, Peter Sanders, Dominik Schultes, et Daniel Delling de l’université Karlsruhe Institute of Technology d’Allemagne. Comme Dijkstra, cette méthode peut permettre au sein d’un graphe routier, la récupération d’un plus court chemin comme la récupération de zones de chalandise. Cette méthode peut se scinder en au moins 2 phases : 1.
* Une phase de prétraitement du graphe initial. 2.
* Une phase d'exécution de la requête sur la représentation contractée du graphe. La première phase est vouée à générer plusieurs couches successives de représentation du graphe initial de plus en plus synthétiques. Aujourd'hui plusieurs outils open-source de calcul d'itinéraire utilisent cette méthode : OSRM, OpenTripPlanner, Graphhopper, Tempus, RoutingKit (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 25804 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- In computer science, the method of contraction hierarchies is a speed-up technique for finding the shortest-path in a graph. The most intuitive applications are car-navigation systems: a user wants to drive from to using the quickest possible route. The metric optimized here is the travel time. Intersections are represented by vertices, the road sections connecting them by edges. The edge weights represent the time it takes to drive along this segment of the road. A path from to is a sequence of edges (road sections); the shortest path is the one with the minimal sum of edge weights among all possible paths. The shortest path in a graph can be computed using Dijkstra's algorithm but, given that road networks consist of tens of millions of vertices, this is impractical. Contraction hier (en)
- En mathématiques appliquées, la méthode des contractions hiérarchiques est une technique destinée à réduire le temps de calcul du plus court chemin grâce à la construction d'une représentation dite "contractée" du graphe initial sur laquelle sont exécutés des algorithmes adaptés aux recherches sur structure multi-niveaux. Les temps de calcul d’itinéraire issus de cette méthode peuvent être drastiquement plus rapides que l'algorithme de Dijkstra et surpasser de plus anciennes méthodes d'optimisation telles que les Highway Hierarchies. Elle a été proposée en 2008 par Robert Geisberger, Peter Sanders, Dominik Schultes, et Daniel Delling de l’université Karlsruhe Institute of Technology d’Allemagne. Comme Dijkstra, cette méthode peut permettre au sein d’un graphe routier, la récupération d’un (fr)
|
| rdfs:label
|
- Contraction hierarchies (en)
- Contractions hiérarchiques (fr)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
