Calculs d’itinéraires

Calculer un itinéraire optimal est une tâche difficile. Dans un marché très concurrentiel, l'algorithme de routage des développeur est souvent confidentiel, il est basé sur des méthodes de calculs mais aussi des observations ou des suppositions. Différents objectifs peuvent être recherchés : le plus rapide, le moins cher…

La recherche de chemin consiste à trouver comment se déplacer dans un environnement entre un point de départ et un point d'arrivée en prenant en compte différentes contraintes. Il peut se ramener à rechercher le meilleur chemin dans un graphe lorsque l’on se déplace uniquement sur un réseau (route, rails,…) sinon le cas général est plus complexe (navigation maritime). Pour obtenir le meilleur itinéraire deux méthodes principales sont possibles :

• Calculer la longueur de tous les parcours possibles. Ce principe peut être représenté par l’algorithme de Dijkstra
• Essayer en priorité les parcours se dirigeant vers la bonne direction

Exemple : rechercher le meilleur itinéraire entre Grenoble et Bordeaux à partir des données suivantes :

• Bordeaux → Nantes : 4h
• Bordeaux → Marseille : 9h
• Bordeaux → Lyon : 12h
• Nantes → Paris : 2h
• Nantes → Lyon : 7h
• Paris → Grenoble : 4h30
• Marseille → Lyon :2h30
• Marseille → Grenoble : 4h30
• Lyon → Grenoble : 1h30

On modélise ce problème par un graphe en indiquant le nom des villes et la durée des trajets :

Sans entrer dans les détails, l'algorithme de Dijkstra travaille sur des graphes (chaque ville est un sommet du graphe et chaque route est une arête du graphe), visionnez cette vidéo pour en savoir plus.

Algorithme de Dijkstra