Tout d'abord bravo pour ton projet, c'est un sujet très intéressant. Quand est-ce qu'il y aura Bonn dans ta démo? ☺
Je pense que l'algorithme de recherche de plus court chemin est très éloigné de ce qui est utilisé en réalité. Les algorithmes de type Dijkstra ou A* sont des algorithmes généralistes mais ici notre graphe est assez loin d'être aléatoire, c'est un réseau routier et il y a beaucoup de structures supplémentaires qui ne sont pas forcément faciles à décrire mathématiquement — parceque difficile à identifier — mais dont on peut tirer parti.
À mon avis il est beacoup plus efficace d'essayer d'imiter ce que fait un être humain pour déterminer son trajet face à une carte:
On détermine une série d'étapes intermédiaires en les choisissant parmi une liste prédéfinie.
On calcule un plus court chemin entre ces étapes.
On résout le problème en partant de plus courts chemins reliant ces étapes intermédiaires en utilisant une méthode de simulated annealing pour améliorer la première approximation.
Le 1 correspond assez bien à la façon dont on s'oriente: pour un trajet dans une ville on s'oriente grâce aux grandes avenues et places principales par exemple. Pour ton on exemple, on peut choisir des étapes de référence indépendemment de critères de fréquentation, en prenant un maillage relativement large (par exemple une tous les 1km).
Le 2 est plus rapide entre les étapes intermédiaires parceque on peut abandonner rapidement les recherches infructueuses (si deux étapes sont distantes de 1,5 km et que mon chemin fait plus de 3km je peux l'abandonner — ou le mettre de côté pour l'instant). Comme les étapes sont prédéfinies on peut précalculer certains chemins.
Le 3 permet d'ajuster l'approximation obtenue en 2, le simulated annealing se prête bien à ce genre d'optimisation.
On peut imaginer plein de variantes — par exemple différents niveaux d'étapes intermédiaires correspondant aux échelles du voyage (quartier, ville, région,...), et très certainement c'est une bonne idée de partir de plusieurs approximations initiales.
# Recherche de plus court chemin
Posté par Michaël (site web personnel) . En réponse au journal rv/hervé : recherche d’itinéraire vélo minimisant l'énergie en utilisant les données d'OSM. Évalué à 2. Dernière modification le 28 octobre 2014 à 08:22.
Salut!
Tout d'abord bravo pour ton projet, c'est un sujet très intéressant. Quand est-ce qu'il y aura Bonn dans ta démo? ☺
Je pense que l'algorithme de recherche de plus court chemin est très éloigné de ce qui est utilisé en réalité. Les algorithmes de type Dijkstra ou A* sont des algorithmes généralistes mais ici notre graphe est assez loin d'être aléatoire, c'est un réseau routier et il y a beaucoup de structures supplémentaires qui ne sont pas forcément faciles à décrire mathématiquement — parceque difficile à identifier — mais dont on peut tirer parti.
À mon avis il est beacoup plus efficace d'essayer d'imiter ce que fait un être humain pour déterminer son trajet face à une carte:
On détermine une série d'étapes intermédiaires en les choisissant parmi une liste prédéfinie.
On calcule un plus court chemin entre ces étapes.
On résout le problème en partant de plus courts chemins reliant ces étapes intermédiaires en utilisant une méthode de simulated annealing pour améliorer la première approximation.
Le 1 correspond assez bien à la façon dont on s'oriente: pour un trajet dans une ville on s'oriente grâce aux grandes avenues et places principales par exemple. Pour ton on exemple, on peut choisir des étapes de référence indépendemment de critères de fréquentation, en prenant un maillage relativement large (par exemple une tous les 1km).
Le 2 est plus rapide entre les étapes intermédiaires parceque on peut abandonner rapidement les recherches infructueuses (si deux étapes sont distantes de 1,5 km et que mon chemin fait plus de 3km je peux l'abandonner — ou le mettre de côté pour l'instant). Comme les étapes sont prédéfinies on peut précalculer certains chemins.
Le 3 permet d'ajuster l'approximation obtenue en 2, le simulated annealing se prête bien à ce genre d'optimisation.
On peut imaginer plein de variantes — par exemple différents niveaux d'étapes intermédiaires correspondant aux échelles du voyage (quartier, ville, région,...), et très certainement c'est une bonne idée de partir de plusieurs approximations initiales.