comment définir le trajet le plus court ou l'idéal?

bonjour,

Auourd'hui on a une greve de bus dans notre ville.
D'habitude les déplacements sont faits en bus, et donc là on doit les accompagner (donc jouer les taxi) dans la ville entière.

Quand j'ai la liste des adresses des déplacements de la journée, y-a-t-il un moyen informatique de savoir quel est l'ordonnancement idéal des interventions ?
Là les rendez-vous sont pris à la volée en fonction des disponiblités, du coup ou peut aller du nord puis à l'extreme sud plusieurs fois et revenir....
Alors que si les interventions étaient ordonnancées par lieu (par adresse géographique, pas par ordre alphabétique!), ce serait mieux au niveau temps de déplacement (et donc essence, disponibilité..Etc).

comment se résoud ce cas au niveau informatique (et donc avec python si possible) ?

merci de votre aide.

ps : au niveau humain, on mettrait tous les points sur une carte et on reliérait au plus proche chaque point, à vue d'oeil comme le jeu d'enfant (relier 1 2 3 ..49 et un dessin apparait)....

algorithme de dijkstra

Il y a pas mal de pdf sur le net concernant cet algorithme.

Citation:

---

Envoyé par fred1599

algorithme de dijkstra

---

oh là! mes cours de licence info, je dois les retrouver...
mais de mémoire, ça concernait les arcs ou les graphes ou les matrices...

J'en avais déjà entendu parler, mais j'ai pas le niveau théorique pour t'en dire plus.

Tu peux peut-être trouvé (j'ai pas le temps) un code python utilisant cet algorithme et l'analyser (pas le copier, hein :) )

Peut-être que certains codeurs ici pourront t'aider plus que moi pour les détails.

cela ne répond pas exactement à mon besoin, sauf si je fais un traitement itératif caca (passage car moins de 200x200 itérations suivant cpu).
Mais ce que permet de faire postgis est d'une simplicité à bruler mes cours de licence :

http://www.bostongis.com/PrinterFrie...ighbor_generic

Suffit de voir les Cases, et comment par une simple requête SQL, on a le résultat.

Dans tous les cas ma première étape est de formaliser chaque adresse.
La seconde sera d'obtenir ses corrdonnées géographiques sur le globe.

Ensuite on verra...

Mais bon, je rêve d'un :

Citation:

---

SELECT client_nom,adresse_postale FROM intervention ORDER BY 'le plus proche de celui d'avant'

---

Si j'ai bien compris le problème, il s'agit plutôt d'un cas typique du problème du voyageur de commerce (http://fr.wikipedia.org/wiki/Probl%C...ur_de_commerce), c'est à dire, trouver une tournée qui minimise le coût total (temps de déplacement).

C'est un problème fort étudié. Il n'existe pas d'algorithme exact efficace (càd en temps polynomial) pour ce problème mais il a des algorithmes donnant des solutions approchées qui sont généralement suffisantes en pratique. La version anglaise de la page wikipedia ci-dessus est beaucoup plus détaillée à ce sujet.

Ce problème est abrévié TSP (pour Travelling Salesman Problem). Une recherche sur "python TSP" devrait donner quelques résultats utilisables...

Bonjour,

Je suis débutant mais je partage ma vision théorique du problème.

Il me paraît compliqué de gérer le réseau autoroutier, je serai donc allé sur une solution plus simple mais qui peut être erronée : le chemin le plus court à vol d'oiseau.
La première étape : affecter les coordonnées GPS à chaque adresse. Considérons que chaque coordonnée est un point 2D (x,y). Idéalement, le point de départ devra être en bordure de ce nuage de points.
Deuxième étape : pour ordonner les points... Calculer l'ensemble des vecteurs définis par le point de départ comme origine et le n autres points... Retenir le vecteur dont la longueur est la moins longue et inserer dans mon trajet (en la supprimant de la liste des possibles)... Puis recommencer les calculs avec ce point en nouvelle origine...

Pour Python, je créerai
1. une Class Adress() avec plusieurs méthodes : def adress_postal(), def coordonnees_gps()
2. une Class Vecteur() avec plusieurs méthodes : def calcul_vect_entre_2_points(), def longueur_vecteur()...
3. Une fonction def comparaison_longueur_vecteur()

Bertrand

Salut,

Citation:

---

Envoyé par Bear the french

Il me paraît compliqué de gérer le réseau autoroutier, je serai donc allé sur une solution plus simple mais qui peut être erronée : le chemin le plus court à vol d'oiseau.

---

Si la solution ne tient pas compte de l'état des routes (encombrements, travaux, accidents,...) ni des différentes possibilités pour aller de A à B par la route, à la vitesse légale permise,... des prises de rendez vous qui peuvent évoluer en temps réel, ... quelle sera l'utilité de "coder"??

On peut bien sûr penser "algo" ou plutôt "complexité algorithmique" mais pour ce qui est réalisation i.e. "classes" voire "langage de programmation", cela me semble "prématuré".

Cordialement

- W

Oui, ma solution est simpliste. Un peu comme mon niveau en python.:oops:

J'imagine la version autoroutière comme une toile avec des points représentant les intersections... Avec pleins d'autres paramètres comme le sens de circulation, la vitesse maximum autorisée (pour transformer les distances en échelle temps), l'influence des stops et des feux...

Bertrand

On pourrait utiliser un service Web pour le calcul de distance / temps de trajet. Genre Google Maps ou ViaMichelin...

L'algorithme proposé par Bear the french (choisir la destination la plus proche à chaque étape) est ce qu'on appelle un algorithme glouton: à chaque étape on se contente d'une optimisation locale, un tronçon de trajet à la fois. C'est facile à implémenter et cela permet d'avoir une première solution de qualité "moyenne". On peut ensuite affiner cette solution, par exemple avec un algorithme de type 2-opt.

Salut,

Citation:

---

Envoyé par Bear the french

Oui, ma solution est simpliste. Un peu comme mon niveau en python.:oops:

---

Pas du tout... Quelque part il faudra bien des "adresses" et des "trajets" puisque ce sont des "objets" du "domaine"... comment seront réalisés ces objets (et avec quelles classes) reste à définir.

Par exemple, on pourrait imaginer créer une interface avec Google Maps et y récupérer des trajets déjà calculés. Adresses et trajets seraient dans ce cas représentées par des informations distribuées entre Google et l'application.
Cet exemple pour dire que tant que nombre d'options techniques n'ont pas été évaluées et arrêtées, difficile de coder.

- W

Citation:

---

Envoyé par wiztricks

Par exemple, on pourrait imaginer créer une interface avec Google Maps et y récupérer des trajets déjà calculés. Adresses et trajets seraient dans ce cas représentées par des informations distribuées entre Google et l'application.
Cet exemple pour dire que tant que nombre d'options techniques n'ont pas été évaluées et arrêtées, difficile de coder.
- W

---

Oui, ça serait idéal d'utiliser "l'intelligence" de GoogleMap et d'en extraire les infos. L'exercice doit être compliqué ... Mais intéressant car cette parenté entre GoogleMap et le logiciel Python peut permettre de gérer l'échelle temps, sens de circulation, modifications des routes...

Cette interface (python/html) utilise sans doute une bibliothèque. Quelle serait le nom de cette bibliothèque ?

Bertrand

Citation:

---

Envoyé par Bear the french

Cette interface (python/html) utilise sans doute une bibliothèque. Quelle serait le nom de cette bibliothèque ?

---

L'API Distance Matrix de Google devrait convenir ici. Donc c'est plutôt du HTTP & XML ou JSON dont on aurait besoin.

Pour l'envoi de la requête, on peut utiliser urllib ou urllib2.

Pour parser le résultat, il y a le module json ou bien l'un des nombreux modules XML...

Ce ne semble pas trop compliqué, mais il faudra veiller à ce que les adresses soient dans un format reconnu pour la géolocalisation.

[edit] Hum, le licensing du service oblige à afficher les résultats sur une Google Map. C'est à prendre en compte...

Salut,

Il n'est pas interdit de construire une application Python qui contrôlerait l'affichage "dans" un "browser" embarqué.

C'est ce que permet par exemple le Webkit inclus dans Qt (mais accessible aussi via d'autres GUI suivant les OS).

Dans ce cas, l'interprétation du JSON et du XML ne serait plus à faire par l'application "Python" mais en partie par le "browser" embarqué.

- W