Discussion :

[clavier12AZQSWX]

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)....

[fred1599]

algorithme de dijkstra

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

[clavier12AZQSWX]

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...

[fred1599]

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.

[clavier12AZQSWX]

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 :

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

[dividee]

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...

[Bear the french]

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