1. #1
    Membre éclairé Avatar de b_reda31
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2007
    Messages
    759
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 34
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2007
    Messages : 759
    Points : 802
    Points
    802

    Par défaut Algorithme de recherche de chemin dans un réseau de transport collectif

    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.
    « Il est assez difficile de trouver une erreur dans son code quand on la cherche. C’est encore bien plus dur quand on est convaincu que le code est juste!!»

  2. #2
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 534
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 534
    Points : 3 189
    Points
    3 189

    Par défaut

    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.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  3. #3
    Membre éclairé Avatar de b_reda31
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2007
    Messages
    759
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 34
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2007
    Messages : 759
    Points : 802
    Points
    802

    Par défaut

    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)
    « Il est assez difficile de trouver une erreur dans son code quand on la cherche. C’est encore bien plus dur quand on est convaincu que le code est juste!!»

  4. #4
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 534
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 534
    Points : 3 189
    Points
    3 189

    Par défaut

    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à.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

  5. #5
    Responsable Qt


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherches
    Inscrit en
    août 2008
    Messages
    22 494
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherches
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 22 494
    Points : 123 769
    Points
    123 769

    Par défaut

    Citation Envoyé par b_reda31 Voir le message
    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).
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions), HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

Discussions similaires

  1. algorithme de calcul du courant dans un réseau électrique
    Par jerry tekobon dans le forum Général Algorithmique
    Réponses: 4
    Dernier message: 14/06/2013, 08h00
  2. Rechercher du texte dans lecteur réseau
    Par arcane dans le forum Windows 7
    Réponses: 2
    Dernier message: 01/09/2011, 10h19
  3. Recherche de chemins dans une table
    Par Diafwl dans le forum PHP & MySQL
    Réponses: 7
    Dernier message: 31/01/2006, 18h16
  4. Algorithme de recherche de chemin
    Par amelie gaya dans le forum Général Algorithmique
    Réponses: 3
    Dernier message: 09/06/2002, 16h29

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo