Discussion :

[philppe27]

Bonjour et meilleurs voeux pour cette année 2012 à tous,

J'aurais besoin de votre aide pour le problème suivant:
- J'ai besoin de calculer des itinéraires routiers avec environ 15 à 20 étapes par itinéraires
- j'ai automatisé le calcul de la distance entre chaque étape à partir de Google Maps avec des morceaux de programmes que j'ai trouvés sur différents forums (voir fichier ci-joint)

Je recherche, donc, à optimiser l'itinéraire en réduisant au maximum les km parcourus. La contrainte est un départ et une arrivée imposée.
J'ai fait des recherches sur différents forums et j'ai compris que mon problème s'apparentait à des permutations et que le nombre de permutations se calcule de la manière suivante : 15 étapes ---> nbre de permutations ou de possibilités de trajets = 1X2X3X4....X15 soit 15! ou factorielle 15.
A partir de là on comprend bien que plus on a d'étapes plus le nbre de possibilités de trajets augmente d'une manière phénoménale.
J'ai même trouvé des codes qui permettaient de traiter mon problème, mais malheureusement au dessus de 11 étapes le nbre de possibilités fait que la macro plante. D'après ce que j'ai compris la macro plante parce que toutes les possibilités d'itinéraires sont stockés dans une matrice VBA et que la capacité de stockage d'une matrice dans VBA est atteinte.

N'étant pas très matheux j'ai besoin de votre aide, car je ne comprends pas que l'on ait besoin de stocker toutes les possibilités dans une matrice.
En effet, mon raisonnement est qu'il faut définir un algorithme dans VBA :
- pour calculer pas à pas chaque possibilité
- calculer le nombre de km total
- comparer le nbre de km avec le résultat retenu précédemment
- retenir le résultat avec le moins de km
- et ainsi de suite jusqu'à la dernière possibilité
Bien évidemment le temps de traitement risque d'être long mais finalement faible par rapport au gain de l'optimisation.
Pourriez vous m'aider sur ce sujet ?

Cordialement

[ZebreLoup]

Sinon regarde ce fil

J'avais fait une implémentation de l'algorithme de Dijkstra qui est bien plus rapide que de tester toutes les permutations. Ça m'avait pris un peu de temps alors autant que ça serve.

Le seul problème que tu vas avoir, c'est qu'en fait, il ne faut utiliser que les distances entre villes qui se touchent, sinon, vu que tu as rentrer toutes les distances, ça va toujours te renvoyer le chemin direct sans te dire par où passer.

Je m'explique :
Imaginons pour simplifier que l'on travaille sur 4 villes Paris, Toulouse, Lyon, Montpellier et que l'on veut faire Paris-Montpellier. Il faudra rentrer Paris-Toulouse, Toulouse-Montpellier, Paris-Lyon et Lyon-Montpellier. Car le Paris-Montpellier (comme le Lyon-Toulouse) n'est pas un trajet "connexe". Si tu rentres une distance donnée par Google Map, c'est déjà optimisé en fait, et tu ne sais pas comme il l'a optimisé.
J'espère que j'ai été assez clair.
Il faut donc virer tous les distances qui ne correspondent pas à un trajet direct.

[philppe27]

Bon dans un premier temps c'est un peu hard pour moi mais je regarde cela à tête reposée et je te recontacte lorsque je me suis fait une idée précise

Merci pour ce fichier.
J'ai fait des tests et il semble que cela ne corresponde pas exactement à ce que je cherche mais peut-être que je m'y prend mal...
La "liste des noeuds" qui correspond à mes étapes devraient être tous présents dans la liste "Résultats Chemin" or par exemple lorsque je mets C1 en départ et C9 en arrivée il manque les étapes C2, C4, C5 et C6.
Je dois absolument me rendre en C2, C4, C5 et C6 mais je ne sais pas dans quel ordre aller à ces étapes. C'est le résultat que je cherche à obtenir.
Merci pour votre aide

Autre précision :
Par rapport à mon point départ, j'ai des étapes au Nord au Sud à l'Est et à l'Ouest les distances similaires par rapport à mon point de départ ne sont donc pas forcément proches

[Qwazerty]

Salut

Si tu fonctionnes avec internet, plutôt que d'utiliser GoogleMap, utilise plutôt Mappy.fr, tu fais une petite prise de contrôle d'internet explorer, tu renseigne autant d'étapes que nécessaire et il te calcul le meilleur chemin

++
Qwaz

[philppe27]

Je peux me tromper mais compte tenu du nbre de combinaisons possibles si 15 étapes par exemple = 15X14X13X12...X2X1 le temps de traitement va être énorme et bien plus important qu'en faisant le somme des combinaisons sur excel.
Mais peut-être existe-il déjà une possibilité que je ne connais pas ?

[Qwazerty]

Salut

Mappy te permet de calculer l'itinéraire le plus adapté, exactement ce que tu cherches il me semble.

http://fr.mappy.com/#d%5B%5D=Lyon,+6...=r&p=itinerary

Inverse Brest et Toulouse par exemple, tu verras, il les remet en place

++
Qwaz