Discussion :

[b_reda31]

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.

[tbc92]

Tu as à peu près tout dit. Algorithme du plus court chemin.

Pour mettre des coûts en face de chaque arc, je pense que le meilleur critère, c'est le temps : donc sur une ligne de bus , c'est le temps qu'il faut pour aller en bus de l'arrêt 1 à l'arrêt 2.
Et pour les correspondances... c'est plus compliqué. tu dois gérer la station "XXX", la ligne A et la ligne B passe par cette station. Si le passager doit marcher 100mètres entre la ligne A et la ligne B, on sait à peu près estimer le temps qu'il faut pour faire 100 mètres à pied. Mais il faut ajouter un temps d'attente. Si la ligne B a un bus toutes les 20 minutes, il faudra attendre statistiquement 10 minutes.
Tu as donc besoin de connaître la fréquence des bus sur chaque ligne pour ton estimation.

Option beaucoup plus pointue :
Sur des lignes de bus, avec des horaires assez régulier , ça paraît la bonne méthode. Sur des lignes de train ou des lignes d'avion, ou sur des lignes de bus avec des horaires très bien connus, il faudra faire autrement. On va prendre l'horaire de départ du passager, on sait qu'il va arriver à la station XXX à telle heure. on sait qu'il lui faut x minutes pour aller du point XXX.A au point XXX.B.
Et là, on pourra regarder quand va passer le prochain bus. Donc même si on sait qu'il passe un bus toutes les 20 minutes, on va pouvoir dire plus précisément si le temps d'attente va être de 0mn, ou de 20mn.


A voir dans ton cas de figure. Mais je pense que sur des lignes de bus, la première méthode est largement suffisante.

[b_reda31]

Merci à vous tbc92 pour votre réponse.
Votre remarque est très pertinente ! Le faite de pondérer les arcs par une durée au lieu d'une distance permet de normaliser ce poids (en temps) ce qui permet de prendre en compte le temps de déplacement à pieds entre deux stations ainsi que le temps d'attente (temps max / 2) comme vous l'avez mentionné.
Cependant, contrairement à une distance, le temps nécessaire entre deux stations est variable, car il dépends fortement de l'état du traffic... ce qui peut nous mener à l'utilisation d'un graphe à "poids variables" Mais bon! pour un début, je vais pas trop me casser la tête, je vais estimer la pondération (temps nécessaire entre deux station) en fonction de la distance entre ces deux arrêts!

On peut ainsi obtenir un graphe standard (pondéré et non orienté) pour lequel il est possible d'appliquer des algos du plus court chemin...
Quel algo me conseillez-vous ?
je précise que le nombre de stations d’arrêts est assez conséquent ! peut être de l'ordre de 1000 , donc l'utilisation d'une matrice d'adjacence pour la représentation du graphe peut s’avérer très coûteuse! (1000 * 1000)

[tbc92]

Reformuler clairement un problème, je sais faire. Mais ma compétence s'arrête là (pas tout à fait, mais presque)
DIJKSTRA, A* , voilà les 2 noms que je saurais te donner, mais je ne saurais pas t"en dire plus.
Dans beaucoup de questions sur les parcours d'arbres, les arcs ont tous le même coût. Mais pas dans ton cas. Il faut donc que tu t"assures que l'algorithme que tu retiens sache gérer ce cas là.

[dourouc05]

je précise que le nombre de stations d’arrêts est assez conséquent ! peut être de l'ordre de 1000 , donc l'utilisation d'une matrice d'adjacence pour la représentation du graphe peut s’avérer très coûteuse! (1000 * 1000)

Oui et non. Un million d'éléments, ce n'est pas si gigantesque pour un ordinateur actuel (de l'ordre du mégaoctet, avec un seul bit stocké pour chaque paire de nœuds). D'ailleurs, ta matrice d'adjacence est probablement creuse, donc nettement plus légère à stocker en mémoire qu'une matrice dense, ça doit se rapprocher d'une représentation plus naturelle d'un graphe (chaque nœud correspond à la liste des nœuds auxquels il est connecté, avec un poids).