Répondre à la discussion
Affichage des résultats 1 à 30 sur 30

Algorithme lie au calcul de temps entre deux villes



  1. #1
    anthony_unac

    Algorithme lie au calcul de temps entre deux villes

    Bonsoir

    Existe il un logiciel qui vous donne toutes les villes situees a moins d une heure (par exemple) d une ville d origine. En bonus, le logiciel serait capable de colorier sur la carte la zone des villes situees a moins d une heure de la ville d origine ?

    Cordialement
    Anthony

    -----


  2. Publicité
  3. #2
    Zartan

    Re : Algorithme lie au calcul de temps entre deux villes

    Bonsoir, ce n'est pas un problème très difficile quand on a la carte. Ce qui est difficile, c'est de calculer le meilleur parcours entre X villes et ça s'appelle le problème du voyageur de commerce.

  4. #3
    JPL

    Re : Algorithme lie au calcul de temps entre deux villes

    Rien à voir avec le problème du voyageur de commerce. Là c'est juste la distance entre deux villes, répété autant de fois qu'il y a de villes. Sauf qu'il faut préciser c'est c'est à pied, à cheval, en voiture, en train... Si c'est en voiture il faut tenir compte de la réglementation de vitesse sur les différents segments du trajet. En fait ce que tu voudrais c'est une peu ce que fait un GPS. Demande à Tomtom ou à Garmin.
    Rien ne sert de penser, il faut réfléchir avant - Pierre Dac

  5. #4
    kwariz

    Re : Algorithme lie au calcul de temps entre deux villes

    Bonsoir,

    Si on dispose d'un graphe décrivant le réseau routier (une arête représente un tronçon à vitesse constante) alors l'algorithme de Dijkstra est ce qu'il te faut.

  6. #5
    Zartan

    Re : Algorithme lie au calcul de temps entre deux villes

    Pour les données vous avez des cartes ici : http://openstreetmap.fr

  7. A voir en vidéo sur Futura
  8. #6
    anthony_unac

    Re : Algorithme lie au calcul de temps entre deux villes

    Bonjour,

    Merci a tous pour vos réponses.

    1/ Il me faut préciser (vous avez raison) que le mode de transport est la voiture. Donc le temps pour se rendre à une ville donnée dépendra de la vitesse a laquelle le véhicule peut rouler sur les différentes routes amenant à la ville de destination.

    2/ Mon problème n'a rien a voir avec celui du voyageur. Il ne s'agit pas de calculer le meilleur parcours entre X villes.

    3/ Le but est de dessiner au final un "rayon" autour de ma ville d'origine contenant toutes les villes situées à moins d'une heure de l'origine. Bien évidement ce dessin n'est pas un cercle (le trajet ne s'effectue pas a vol d'oiseau.

    4/ Malheureusement, le GPS n'est pas capable de dessiner un tel "rayon". En revanche il peut me dire combien de temps durera le parcours (trafic compris) entre la ville d'origine et UNE ville voisine.

    5/ Après réflexion, peut être que ce sujet n'est peut être pas trop à sa place ici mais ou le mettre ?


    6/ Exemple :
    -------------

    Ville d'origine : PERPIGNAN

    Mode de transport : VOITURE

    But : DÉTERMINER TOUTES LES COMMUNES SITUÉES A MOINS D'UNE HEURE DE PERPIGNAN

    Constatation : CERTAINES COMMUNES SONT PROCHES DE PERPIGNAN (A VOL D'OISEAU) MAIS PLUS ÉLOIGNÉES QUE D'AUTRE EN TERME DE TEMPS (EX: Le Perthus est plus éloignée de Perpignan que Caixas mais on s'y rend plus vite)(EX: Argeles est plus éloignée que Montner mais on s'y rend plus rapidement)

    Un logiciel capable de calculer tout ceci existe t il aujourd'hui ?
    En gros l'idée c'est de créer une carte du département ou on laisse la ville de Perpignan à sa position géographique actuelle et on replace toutes les communes des alentours en fonction ,non pas de leurs positions géographiques (distance en km par rapport a Perpignan), mais de leurs temps d'atteinte (temps en minutes) en partant de Perpignan.
    Je me souviens qu'à l'époque la SNCF avait redessinée la carte de France sur les mêmes critères en choisissant Paris comme ville d'origine. Marseille étant atteinte en 3H cela donnait une *drole* de forme à la carte de France.

    Cordialement
    Anthony

  9. Publicité
  10. #7
    kwariz

    Re : Algorithme lie au calcul de temps entre deux villes

    Bonjour,

    je ne sais pas s'il existe un logiciel qui te fasse ça pour n'importe quelle ville (faut demander à google), mais ce n'est pas compliqué à créer. Si on se restreint à la France, pour une ville on construit la liste de toute les villes à moins de 130km (une requête à google maps ?), pour chacune de ces villes on calcule (une requête à google maps ?) la distance en temps et on ne garde que celles dont la distance est inférieure à 1H.

  11. #8
    anthony_unac

    Re : Algorithme lie au calcul de temps entre deux villes

    Citation Envoyé par kwariz Voir le message
    Bonjour,

    Si on se restreint à la France, pour une ville on construit la liste de toute les villes à moins de 130km (une requête à google maps ?), pour chacune de ces villes on calcule (une requête à google maps ?) la distance en temps et on ne garde que celles dont la distance est inférieure à 1H.
    Une telle requête ne semble pas possible en fait.

  12. #9
    kwariz

    Re : Algorithme lie au calcul de temps entre deux villes

    Si je demande à google maps un chemin de "F-59000" (Lille) à "F-66000" (Perpignan) il me donne :
    gmaps.png
    Il me donne toutes les infos nécessaires. Les listes de codes postaux sont disponibles, après tout va dépendre du nom bre de villes que tu considères.

  13. #10
    kwariz

    Re : Algorithme lie au calcul de temps entre deux villes

    En cherchant par curiosité je suis même tombé sur un site proposant une petite db (au format csv) des communes françaises avec entre autre leurs coordonnées géographiques ce qui permet d'estimer (je pense suffisament corrctement) les communes situées dans un rayon de x km à vol d'oiseau autour d'une autre commune.

  14. #11
    anthony_unac

    Re : Algorithme lie au calcul de temps entre deux villes

    Sachant qu'il y a (parait t il) 226 communes dans les Pyrénées Orientales, il serait beaucoup trop long de procéder de la sorte. En même temps, je ne vois pas comment faire autrement ?
    Peut être en biaisant la chose : restriction aux communes les plus grandes par exemple mais c'est moche car
    1/ Il n'y a pas vraiment de communes beaucoup plus grandes que d'autres (a part Perpignan)
    2/ Toute la subtilité de la démarche réside dans l'atteinte de communes situées en montagne.

  15. #12
    kwariz

    Re : Algorithme lie au calcul de temps entre deux villes

    C'est même impossible en fait ... google limite à un maximum de 2500 requêtes par jour soit un vingtaine de jours pour obtenir les distances en temps entre toutes les communes des PO.
    Peut-être touveras-tu ton bonheur sur openstreetmap, le lien donné par Zartan ; il faut creuser.

  16. Publicité
  17. #13
    anthony_unac

    Re : Algorithme lie au calcul de temps entre deux villes

    Citation Envoyé par kwariz Voir le message
    une petite db (au format csv) des communes françaises avec entre autre leurs coordonnées géographiques ce qui permet d'estimer (je pense suffisament corrctement) les communes situées dans un rayon de x km à vol d'oiseau autour d'une autre commune.
    Oui, mais le but de la manœuvre est de trouver toutes les communes situées a moins d'une heure d'une ville d'origine. Autrement dit, ce n'est plus le facteur *distance* qui importe mais le facteur *temps*. A combien de temps se trouve la ville x_i de ma ville d'origine. Dans le 66, il y a une collection de 226 communes soit 226 tests à réaliser (de x_1 à x_226) pour savoir si le temps d'atteinte est inférieur à 1 H.
    Ensuite, il faut pouvoir redessiner la collection de communes dont le temps d’atteinte est inférieur à 1 H etc...

  18. #14
    kwariz

    Re : Algorithme lie au calcul de temps entre deux villes

    J'ai du mal m'exprimer, je parle de 3 distances :
    1. distance en km à vol d'oiseau
      facile à déterminer avec le fichier csv
    2. distance en km en empruntant le réseau routier
      plus difficile, certainement faisable avec les données d'openstreetmap
    3. distance en temps en empruntant le réseau routier
      on peut éventuellement se débrouiller avec openstreetmap (à creuser)
      google peut aider dans une certaine mesure
    le projet a une certaine ampleur ! surtout si on essaye dl'ajouter une composante temps réel (X est à 55 minutes de Y, sauf sur la période du ... au ... à cause de travaux) ...
    Suivant la région géographique considérée le volume de données peut devenir gigantesque.

  19. #15
    PA5CAL

    Re : Algorithme lie au calcul de temps entre deux villes

    Bonsoir

    Le seul gros problème est de pouvoir disposer des données de temps de parcours, ou des données permettant de les calculer. Le volume qu'elles représentent n'est pas "gigantesque" (toute la France peut tenir dans la mémoire d'un smartphone actuel), mais il faut les obtenir et assurer leur mise-à-jour.

    Comme je doute que tu le fasses toi-même, tu dois faire appel à un service spécialisé, et ta question devient donc beaucoup plus commerciale qu'informatique. En effet, ces informations ne tombent pas du ciel, mais de bases de données actualisées (éventuellement en temps réel) résultant du travail de professionnels, et qui ont par conséquent un coût.

    Leur niveau d'élaboration peut être éventuellement adapté à ce que tu souhaites obtenir par le prestataire. Le contenu du logiciel nécessaire à l'utilisateur final pour en tirer partie en dépendra directement.

    La première question à te poser est donc : où trouver de telles informations, et à quel prix ? Ensuite, il sera toujours temps d'envisager la réalisation du logiciel spécifique dont tu as besoin (lequel n'est pas très compliqué à concevoir et à développer, je parle d'expérience).

  20. #16
    kwariz

    Re : Algorithme lie au calcul de temps entre deux villes

    Citation Envoyé par PA5CAL Voir le message
    Le volume qu'elles représentent n'est pas "gigantesque" (toute la France peut tenir dans la mémoire d'un smartphone actuel), mais il faut les obtenir et assurer leur mise-à-jour.
    Je t'assure que pour obtenir ce qui tient dans un portable (ordre de grandeur 500Mo/1Go+ pour une carte routière de la France) est petit par rapport à ce qu'il te faut pour le créer, aussi bien en temps qu'en volume de données, mais tout dépend et de la zone géographique, et de la précision souhaitée.

  21. #17
    Zartan

    Re : Algorithme lie au calcul de temps entre deux villes

    Citation Envoyé par PA5CAL Voir le message
    La première question à te poser est donc : où trouver de telles informations, et à quel prix ?
    Citation Envoyé par Zartan Voir le message
    Pour les données vous avez des cartes ici : http://openstreetmap.fr
    Pour info openstreetmap est un équivalent de google maps en opensource. Il faut un serveur puissant pour faire tourner la carte mondiale. C'est gratuit.

  22. #18
    PA5CAL

    Re : Algorithme lie au calcul de temps entre deux villes

    Citation Envoyé par kwariz Voir le message
    Je t'assure que pour obtenir ce qui tient dans un portable (ordre de grandeur 500Mo/1Go+ pour une carte routière de la France) est petit par rapport à ce qu'il te faut pour le créer, aussi bien en temps qu'en volume de données, mais tout dépend et de la zone géographique, et de la précision souhaitée.
    Il se trouve que, pour avoir déjà effectué ce travail pour des données nationales, j'ai une idée assez précise du temps de traitement et de la taille des données justes nécessaires pour obtenir ce que tu souhaites. Et on se situe au-dessous de 500 Mo de stockage, avec des traitements finaux de moins de 3 secondes sur les petits matériels actuels (le pré-traitement des données brutes peut être long même sur du gros matériel).

    Dois-je préciser qu'il n'est pas utile d'avoir l'intégralité des données des cartes routières ?...
    Dernière modification par PA5CAL ; 24/10/2012 à 19h16.

  23. Publicité
  24. #19
    PA5CAL

    Re : Algorithme lie au calcul de temps entre deux villes

    Citation Envoyé par Zartan Voir le message
    Pour info openstreetmap est un équivalent de google maps en opensource. Il faut un serveur puissant pour faire tourner la carte mondiale. C'est gratuit.
    C'est gratuit, mais c'est suffisamment nul (lourd, incomplet, erroné, pas à jour, ...) pour obliger un certain nombre d'utilisateurs à recourir à d'autres solutions plus sérieuses (et par conséquent payantes, mais aussi plus adaptés à leurs besoins).
    Dernière modification par PA5CAL ; 24/10/2012 à 19h22.

  25. #20
    kwariz

    Re : Algorithme lie au calcul de temps entre deux villes

    Citation Envoyé par PA5CAL Voir le message
    Il se trouve que, pour avoir déjà effectué ce travail pour des données nationales, j'ai une idée assez précise du temps de traitement et de la taille des données justes nécessaires pour obtenir ce que tu souhaites. Et on se situe au-dessous de 500 Mo de stockage, avec des traitements finaux de moins de 3 secondes sur les petits matériels actuels (le pré-traitement des données brutes peut être long même sur du gros matériel).

    Dois-je préciser qu'il n'est pas utile d'avoir l'intégralité des données des cartes routières ?...
    J'ai effectivement du mal m'exprimer, mais il était clair (du moins pour moi) que je ne parlais que de données «brutes» (fichier csv pour les distances vol d'oiseau, openstreet pour les données kilométriques voire temporelles). Je ne parlais pas d'un truc tout fait, sinon mes propos n'auraient pas eu grand sens.

  26. #21
    Zartan

    Re : Algorithme lie au calcul de temps entre deux villes

    Citation Envoyé par PA5CAL Voir le message
    C'est gratuit, mais c'est suffisamment nul (lourd, incomplet, erroné, pas à jour, ...) pour obliger un certain nombre d'utilisateurs à recourir à d'autres solutions plus sérieuses (et par conséquent payantes, mais aussi plus adaptés à leurs besoins).
    C'est suffisamment sérieux pour que Apple l'utilise dans iPhoto : http://thenextweb.com/apple/2012/05/...in-iphoto-app/

  27. #22
    PA5CAL

    Re : Algorithme lie au calcul de temps entre deux villes

    Citation Envoyé par Zartan Voir le message
    C'est suffisamment sérieux pour que Apple l'utilise dans iPhoto : http://thenextweb.com/apple/2012/05/...in-iphoto-app/
    Ce n'est pas une référence. N'es-tu pas au courant des déboires de la firme relatifs aux informations géolocalisées, et des nombreuses moqueries qu'elle suscite à ce sujet sur le net ?

    Cela dit, si je critique, ce n'est qu'en tant qu'utilisateur abusé, qui l'a expérimenté et qui en est revenu...
    Dernière modification par PA5CAL ; 24/10/2012 à 20h28.

  28. #23
    Zartan

    Re : Algorithme lie au calcul de temps entre deux villes

    Citation Envoyé par PA5CAL Voir le message
    Ce n'est pas une référence. N'es-tu pas au courant des déboires de la firme relatifs à la géolocalisation, et des nombreuses moqueries qu'elle suscite à ce sujet sur le net ?
    Leurs déboires viennent d'un autre fournisseur (tomtom je crois). Comme autre référence ils ont FourSquare: http://www.journaldugeek.com/2012/03...openstreetmap/

    Cela dit, si je critique, ce n'est qu'en tant qu'utilisateur abusé, qui l'a expérimenté et qui en est revenu...
    Ca va je ne discuterai pas davantage donc.

  29. #24
    anthony_unac

    Re : Algorithme lie au calcul de temps entre deux villes

    Re,

    Merci pour l'aide !
    Finalement, ce n'était pas si compliqué.
    Voila le travail :
    http://www.excel-downloads.com/forum...ml#post1212124

    Cordialement
    Anthony

  30. Publicité
  31. #25
    kwariz

    Re : Algorithme lie au calcul de temps entre deux villes

    Bonjour,

    sympa
    Par curiosité, quelle sont tes sources de données pour les villes ?
    Tu insères le temps de parcours manuellement ?
    Ce fichier prend pour centre Perpignan, c'est ça ?

  32. #26
    anthony_unac

    Re : Algorithme lie au calcul de temps entre deux villes

    Citation Envoyé par kwariz Voir le message
    Bonjour,

    sympa
    Par curiosité, quelle sont tes sources de données pour les villes ?
    Tu insères le temps de parcours manuellement ?
    Ce fichier prend pour centre Perpignan, c'est ça ?
    Merci,

    Mes sources sont officielles.
    Le temps de parcours est inséré manuellement à l'aide de l'application viamichelin (d'ailleurs je n'ai pas encore fini faut que je me tape les 226 communes et j en suis à 63 ou qqch comme ca lol)
    Exact l'origine représente Perpignan.
    A noter qu'on pourrait faire de même avec n'importe quels autres villes et départements.

  33. #27
    kwariz

    Re : Algorithme lie au calcul de temps entre deux villes

    Ce qui serait intéressant serait de partager le lien vers ces données officielles (insee? un .gouv.fr? la poste? wikipedia?)

    Ce qui serait intéressant aussi serait d'automatiser les tes requêtes manuelles, mais bon, c'est une autre histoire.

  34. #28
    anthony_unac

    Re : Algorithme lie au calcul de temps entre deux villes

    Citation Envoyé par kwariz Voir le message
    Ce qui serait intéressant serait de partager le lien vers ces données officielles (insee? un .gouv.fr? la poste? wikipedia?)

    Ce qui serait intéressant aussi serait d'automatiser les tes requêtes manuelles, mais bon, c'est une autre histoire.
    Il m'a suffit de taper "liste des communes des pyrenees orientales" sur google

    Automatiser mes requêtes serait génial mais je ne vois pas vraiment comment m'y prendre avec viamichelin ?
    Pas le choix pour l'instant je tourne en manuel lol

  35. #29
    kwariz

    Re : Algorithme lie au calcul de temps entre deux villes

    Citation Envoyé par anthony_unac Voir le message
    Il m'a suffit de taper "liste des communes des pyrenees orientales" sur google
    Oh tu t'es tapé la liste à la main ?

  36. #30
    anthony_unac

    Re : Algorithme lie au calcul de temps entre deux villes

    non non les données officielles au format excel (longitude, latitude etc...) je les ai acheté 2 euros
    En revanche le temps d'atteinte des communes en partant de Perpignan, c’était en manuel.

Sur le même thème :

Discussions similaires

  1. Calcul de Distance entre 2 villes
    Par Malonepaps dans le forum Mathématiques du supérieur
    Réponses: 6
    Dernier message: 22/09/2014, 16h51
  2. Réponses: 4
    Dernier message: 24/03/2008, 18h47
  3. Réponses: 5
    Dernier message: 31/10/2006, 08h11
  4. Paire répulsive : nouvel état lié entre deux atomes ?
    Par RSSBot dans le forum Commentez les actus, dossiers et définitions
    Réponses: 0
    Dernier message: 17/07/2006, 07h27