Bonjour à toutes et à tous,
je désire mettre en place un algorithme qui permet de trouver des chemins dans un réseau de transport collectifs à partir d'un point de départ et d'un point d'arrivée... je m'explique :
Je dispose des données suivantes :
- Ensemble de Ligne de transport collectifs (BUS) avec la position (longitude, latitude) de chaque station d’arrêt. (pour chaque ligne)
Autrement dit, pour chaque ligne de bus, je dispose des coordonnées GPS de tous ses stations d’arrêt.
à partir de ces données, il est possible de définir les "correspondances" entre chaque couple de ligne si elle existe (pour chaque couple de ligne, il peut y en avoir une, plusieurs ou aucune correspondance)
Une correspondance peut être représentée par deux stations d’arrêts de deux lignes différentes espacées d'une distance négligeable (inférieure à un certains seuil)
je voudrai maintenant exploiter ces données pour établir un petit guide touristique qui permette d'orienter un touriste sur les transports à prendre pour aller d'un point de départ à un point destination.
je pense à modéliser le réseau que j'ai, sous forme d'un graphe où les stations d’arrêt représentent les noeuds du graphe. Deux stations successives sont reliées par un arc dont la pondération peut être évaluée (selon la distance, l'état de la route, de la circulation...etc).
Il faut aussi ajouter les arcs de correspondance, ce qui permet de relier deux lignes différentes. Cependant cet arc représente représente le changement de ligne, je dois donc enregistrer cette information de manière à avoir au final, le chemin avec un nombre de correspondance minimal ou devrais-je dire optimal.
Pour un début, je considère que le point de départ et le point de destination sont des stations d’arrêts (de la même ligne ou de deux lignes différentes), l'objectif est donc de trouver le chemin "optimal" qui mène du point de départ au point d'arrivé.
Je reviens à ma question :
Pour ce type de problème, peut on appliquer les algorithmes de plus court chemin dans un graphe (ex : algo de Dijkstra) ? Si oui par quel moyen intergrer dans la fonction de coût le nombre de correspondance faite !
Sinon, aurait-il d'autre algorithmes plus appropriés pour ce type de problème ?
Merci à vous.
Partager