Optimisation itinéraires routiers avec étapes [Résolu]

[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

[philppe27]

Bravo,

C'est exactement ce que je cherche

Merci

Mais finalement déçu car le nbre d'étape est limité à 6...!!!

[Qwazerty]

Salut

Arff ça c'est ballo...

15 étapes par exemple = 15X14X13X12...X2X1

Pour le nombre de solution, tu fais erreur je pense, il ne faut pas prendre le factoriel, mais l'addition d'une suite.
Pour 15 villes, tu auras
14+13+12+11...+1 = 105
On débute à 14 car une ville ne peut être associée avec elle-même.

De plus, tu n'as pas toutes les possibilités en fait
Imaginons 6 villes nommée A, B...F
Si on part de ton tableau, tu as la distance entre chaque ville.
Si au cours de la boucle de teste, tu utilises un trajet A->C, il faudra supprimer de ce teste tous les autres trajets ayant A comme ville de départ et C comme ville d'arrivé et poursuivre le teste avec uniquement les trajet ayant C comme ville de départ.
Pour avoir une représentation graphique du problème, place les 6 villes en cercle et trace un trait reliant chacune d'elle (pour 6 villes, 14 traits de liaison représentant chacun une distance à parcourir.
Une autre variable qui va limité les calcule est de se dire qu'a chaque fois que tu est en train de calculer un trajet tu dois vérifier que le nombre de km parcouru n'est pas supérieur trajet le plus court déjà trouvé, si au cours du calcul d'un trajet tu dépasses le trajet retenu comme étant le plus court, tu passes au trajet suivant, si arrivé à la fin du trajet celui-ci offre un km plus faible, il devient le trajet le plus court....

Un autre paramètre qui lui va à l'encontre de tout ça, le trajet le plus court n'est pas forcement le plus rapide... à toi de voir ce que tu veux privilégier.

++
Qwaz

[philppe27]

Bonsoir Qwaz,

Merci pour tes commentaires judicieux. Mais tu trouveras, ci-joint, un fichier qui tend à démontrer que le nombre de possibilités est le factoriel du nombre d'étapes (en n'incluant pas dans le calcul, comme tu l'indiques, l'étape du départ et celle de l'arrivée qui sont imposées).
Par contre, j'ai trouvé un code qui calcule les permutations possibles dans une chaine de caractères :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
Sub GetString()
    Dim InString As String
    InString = InputBox("Enter text to permute:")
    If Len(InString) < 2 Then Exit Sub
    If Len(InString) >= 8 Then
        MsgBox "Too many permutations!"
        Exit Sub
    Else
        ActiveSheet.Columns(1).Clear
        CurrentRow = 1
        Call GetPermutation("", InString)
    End If
End Sub
 
Sub GetPermutation(x As String, y As String)
'   The source of this algorithm is unknown
   Dim i As Integer, j As Integer
    j = Len(y)
    If j < 2 Then
        Cells(CurrentRow, 1) = x & y
        CurrentRow = CurrentRow + 1
    Else
        For i = 1 To j
            Call GetPermutation(x + Mid(y, i, 1), _
            Left(y, i - 1) + Right(y, j - i))
        Next
    End If
End Sub

Je pense que si ce code fonctionne pour trouver toutes les permutations d'une chaine de caractères, il dot pouvoir être adapté pour un itinéraire.
Si tu peux m'aider tes suggestions sont les bienvenues.
Merci d'avance,

Philippe

[Qwazerty]

Salut

Avant de coder quoi que ce soit, il faut déjà bien définir ce que doit faire le code.

Oui pour la nombre de possibilités, je pensais uniquement au nombre de trajet entre 2 villes possibles, comme dans le schéma joint, il faut ensuite combiner les différents trajets, ce qui en effet va représenter un certain nombre de permutation.

Je reviens avec un autre schéma dans 5 min
[Edit]
Je rajoute un fichier Excel pour illustré la diminution du nombre de possibilité au fur et à mesure de l'avancement de la boucle, bien sur je ne présente qu'une des solutions, la boucle devra tester toutes les autres en respectant les mêmes règles.
Le nombre de possibilités globales sont comme tu l'as dis factorielles du nombre de ville -2.
Soit pour 6 villes, 4! = 4x3x2x1 = 24 possibilité.
Donc ça va faire un paquet de permutation
[/Edit]


++
Qwaz

[philppe27]

ok pour le nbre de permutations.
J'ai testé le code que je t'ai communiqué. J'ai bien retrouvé mes 24 permutations comme j'avais trouvé manuellement dans mon fichier.
Pour l'instant, je ne vois pas sur quel critère exclure certaines permutations... Elles sont toutes plausibles (?!)
Je repense à une de tes remarques: distance ou temps ?
Dans mon premier fichier si dans l'onglet Données cellule B6 tu mets une lettre ou un chiffre les cases en km se transformeront en heures. Sur Google Maps j'ai également récupéré les temps de trajet.

[Qwazerty]

J'ai craqué, je n'avais pas fait attention au code que tu avais donné, c'est une bonne solution avec une boucle récursive.
Je regarde pour l'adapter.

Salut

Bon c’était un chouilla plus compliqué avec les villes de départ et d'arrivé fixes..

Essai comme ça, c'est plutôt rapide, vérifie bien que ça sorte le bon trajet

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
Sub Villes()
 
Dim TabVilleEtape
Dim TheCell As Range
Dim DicoDistance As New Dictionary, DicoVille As New Dictionary
Dim LastRow As Integer
Dim x As Integer, y As Integer
Dim TabRetour
 
 
 
    'On place les km dans le dico (plus rapide que d'aller chercher dans le tableau excel
    With ThisWorkbook.Sheets("Données")
        LastRow = .Range("B28").End(xlUp).Row
        TabVilleEtape = .Range("B7", .Cells(LastRow, "B").Offset(0, LastRow - 7)).Value
    End With
 
    'On boucle dans le tableau
    For x = 2 To LastRow - 6
        For y = 2 To LastRow - 6
            DicoDistance.Add TabVilleEtape(1, x) & "¤" & TabVilleEtape(1, y), CDbl(TabVilleEtape(x, y))
        Next
    Next
 
    'On récupère la liste des villes étapes
    With ThisWorkbook.Sheets("Données")
        For Each TheCell In .Range("X10", .Range("X29").End(xlUp))
            DicoVille.Add TheCell.Value, ""
        Next
    End With
 
 
    'On appelle PermuteVilles
    With ThisWorkbook.Sheets("Données")
        TabRetour = PermuteVilles(DicoDistance, DicoVille, .Range("X8"), .Range("X9"))
 
        'On place le meilleur parcours dans le tabelau excel
        'On vide
        .Range("Y8:Y28").ClearContents
        'On inscrit les km
        .Range("Z8").Value = Split(TabRetour, "$")(1)
        'On ne conserve que le parcours
        TabRetour = Split(TabRetour, "$")(0)
        'On permute la chaine en tableau
        TabRetour = Split(TabRetour, "¤")
        'On place le tableau
        .Range("Y8").Resize(UBound(TabRetour) + 1).Value = WorksheetFunction.Transpose(TabRetour)
 
    End With
 
 
End Sub
 
 
Function PermuteVilles(DicoKm As Dictionary, DicoVille As Dictionary, VilleDepart As String, VilleArrive, Optional aParcours As String = "<vide>", Optional aDistance As Double)
Dim DicoVilleTmp As New Dictionary
Dim iVille As Long
Dim Parcours
Static MeilleurKm As Double
Static MeilleurParcours As String
 
Dim ParcoursEnCours As String
Dim Distance As Double
 
    'On prolonge le parcours existant
    If aParcours <> "<vide>" Then
        ParcoursEnCours = aParcours
        Distance = aDistance
    Else
        'On initialise les variables "Meilleur", les variables static sont conservées, même aprés une analyse complete
        MeilleurKm = 0
        MeilleurParcours = ""
    End If
 
    'On clone le dico, moins la ville de départ
    For iVille = 0 To DicoVille.Count - 1
        If DicoVille.Keys(iVille) <> VilleDepart Then
            DicoVilleTmp.Add DicoVille.Keys(iVille), ""
        End If
    Next
 
    'On ajoute le parcours villeDepart -> VilleX au parcours
    If ParcoursEnCours <> "" Then ParcoursEnCours = ParcoursEnCours & "¤"
    ParcoursEnCours = ParcoursEnCours & VilleDepart
 
    'On calcule les distances entre villeDepart et toutes les villes étapes
    For iVille = 0 To DicoVilleTmp.Count - 1
        Distance = Distance + DicoKm(VilleDepart & "¤" & DicoVilleTmp.Keys(iVille))
        'Si la distance dépasse la distance la plus courte déjà trouvée
        If MeilleurKm = 0 Or MeilleurKm > Distance Then
            PermuteVilles DicoKm, DicoVilleTmp, CStr(DicoVilleTmp.Keys(iVille)), VilleArrive, ParcoursEnCours, Distance
        Else
            'On retourne la meilleur combinaison
            PermuteVilles = MeilleurParcours & "$" & CStr(MeilleurKm)
            Exit Function
        End If
    Next
 
    If DicoVilleTmp.Count = 0 Then
        'On boucle le trajet avec la ville d'arrivé
        If ParcoursEnCours <> "" Then ParcoursEnCours = ParcoursEnCours & "¤"
        ParcoursEnCours = ParcoursEnCours & VilleArrive
        Distance = Distance + DicoKm(VilleDepart & "¤" & VilleArrive)
        'On verifie les km
        If MeilleurKm = 0 Or MeilleurKm > Distance Then
            MeilleurKm = Distance
            MeilleurParcours = ParcoursEnCours
        End If
        'On vide les variables pour annalyser le prochain parcours
        Distance = 0
        ParcoursEnCours = ""
    End If
 
    'On retourne la meilleur combinaison
    PermuteVilles = MeilleurParcours & "$" & CStr(MeilleurKm)
 
End Function

Pour que ça fonctionne avec une liste de villes pleine, il faut décaler tes 2 petits tableaux "Nb de permutations utiles" et "Nb total de km" vers le bas.

Je te laisse organiser les résultats à ta sauce.

++
Qwaz

[philppe27]

Merci Qwaz pour ce retour,

J'essaie de tout comprendre, c'est un peu hard pour moi.
J'ai recopier le code tel quel et j'ai décalé les 2 tableaux.
J'ai un souci lorsque je lance la macro il bloque sur la fonction :

Code :

Function PermuteVilles(DicoKm As Dictionary, DicoVille As Dictionary, VilleDepart As String, VilleArrive, Optional aParcours As String = "<vide>", Optional aDistance As Double)

et m'envoie le message

Erreur de compilation Type défini par l'utilisateur non défini

Peux tu m'aider sur ce point ? Merci

Apparemment, ça coince sur Dictionary qui ne semble pas être reconnu

Bon, j'ai trouvé pour Dictionary Outils Référence et cochez "Microsoft Scripting Runtime"
Par contre, j'ai un souci sur le DicoDistance qui s'arrête à l'item 256 dans l'affichage des variables locales alors que le nbre de possibilités est de 20X20 soit 400.
D'autre part le programme plante sur le code

Code :

1
2
3
4
5
With ThisWorkbook.Sheets("Données")
        For Each TheCell In .Range("X10", .Range("X29").End(xlUp))
            DicoVille.Add TheCell.Value, ""
        Next
    End With

quand la cellule ajoutée est vide.
Je me demande si la colonne à utiliser n'est pas plutôt la B, la X étant réservée aux étapes imposées (pour l'instant le départ et l'arrivée) ?

[Qwazerty]

SAlut
Zut c'est vrai j'ai oublié de te préciser, sur la colonne X, les 2 premières cellules X8 et X9 correspondent respectivement à la ville de départ et d'arrivé, ensuite tu as la liste de toutes les villes étapes.

Pour le coup des 256 valeurs, je pense que c'est uniquement l'affichage de l'espion qui est limité mais pas la capacité du dictionary.
++
Qwaz

[philppe27]

Qwarz,

J'ai commencé à tester ton programme avec les éléments que tu m'as fournis. Il semble que dans certains cas le résultat obtenu n'est pas optimisé.
Ci-joint le fichier avec le programme, dans la cellule AA7 le résultat avec le programme et un résultat plus optimisé dans la cellule AB8.
Je me demande si lorsque tu compares les itinéraires tu compares bien en tenant compte à chaque fois de l'étape de départ et de celle d'arrivée dans l'itinéraire total.

Merci de ton aide

[Qwazerty]

Salut

Arff, je pense avoir trouver, j'ai toujours un pas d'avance au moment de l'appel récursif, la distance et le parcours que je transmet à la fonction ne correspondent pas...

J'essai de corriger ça.

[Edit]
Essai avec ce code

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
Sub Villes()
 
Dim TabVilleEtape
Dim TheCell As Range
Dim DicoDistance As New Dictionary
Dim DicoVille As New Dictionary
Dim LastRow As Integer
Dim x As Integer, y As Integer
Dim TabRetour
 
 
 
    'On place les km dans le dico (plus rapide que d'aller chercher dans le tableau excel
    With ThisWorkbook.Sheets("Données")
        LastRow = .Range("B28").End(xlUp).Row
        TabVilleEtape = .Range("B7", .Cells(LastRow, "B").Offset(0, LastRow - 7)).Value
    End With
 
    'On boucle dans le tableau
    For x = 2 To LastRow - 6
        For y = 2 To LastRow - 6
            DicoDistance.Add TabVilleEtape(1, x) & "¤" & TabVilleEtape(1, y), CDbl(TabVilleEtape(x, y))
        Next
    Next
 
    'On récupère la liste des villes étapes
    With ThisWorkbook.Sheets("Données")
        For Each TheCell In .Range("X10", .Range("X29").End(xlUp))
            DicoVille.Add TheCell.Value, ""
        Next
    End With
 
 
    'On appelle PermuteVilles
    With ThisWorkbook.Sheets("Données")
        TabRetour = PermuteVilles(DicoDistance, DicoVille, .Range("X8"), .Range("X9"))
 
        'On place le meilleur parcours dans le tabelau excel
        'On vide
        .Range("Y8:Y28").ClearContents
        'On inscrit les km
        .Range("AA7").Value = Split(TabRetour, "$")(1)
        'On ne conserve que le parcours
        TabRetour = Split(TabRetour, "$")(0)
        'On permute la chaine en tableau
        TabRetour = Split(TabRetour, "¤")
        'On place le tableau
        .Range("Y8").Resize(UBound(TabRetour) + 1).Value = WorksheetFunction.Transpose(TabRetour)
 
    End With
 
 
End Sub
Function PermuteVilles(DicoKm As Dictionary, DicoVille As Dictionary, VilleDepart As String, VilleArrive, Optional aParcours As String = "<vide>", Optional aDistance As Double)
Dim DicoVilleTmp As New Dictionary
Dim iVille As Long
Static MeilleurKm As Double
Static MeilleurParcours As String
 
Dim ParcoursEnCours As String
Dim Distance As Double
 
Dim ParcoursTmp As String
Dim DistanceTmp As Double
 
    'On prolonge le parcours existant
    If aParcours <> "<vide>" Then
        ParcoursEnCours = aParcours
        Distance = aDistance
    Else
        'On initialise les variables "Meilleur", les variables static sont conservées, même aprés une analyse complete
        MeilleurKm = 0
        MeilleurParcours = ""
        'Et On début le parcours
        ParcoursEnCours = VilleDepart
    End If
 
    'On clone le dico, moins la ville de départ
    For iVille = 0 To DicoVille.Count - 1
        If DicoVille.Keys(iVille) <> VilleDepart Then
            DicoVilleTmp.Add DicoVille.Keys(iVille), ""
        End If
    Next
 
    'On calcule les distances entre villeDepart et toutes les villes étapes
    For iVille = 0 To DicoVilleTmp.Count - 1
        'On ajoute la ville au parcours et distance temporaires, pour conserver les bon contenu dans ParcoursEnCours et Distance
        'Comme ça, après l'appel récursif, ParcoursEnCours et Distance contiennent les bonne valeur pour accépter le teste d'une nouvelle ville
        If ParcoursEnCours <> "" Then ParcoursTmp = ParcoursEnCours & "¤"
        ParcoursTmp = ParcoursTmp & DicoVilleTmp.Keys(iVille)
        DistanceTmp = Distance + DicoKm(VilleDepart & "¤" & DicoVilleTmp.Keys(iVille))
        'Si la distance dépasse la distance la plus courte déjà trouvée
        If MeilleurKm = 0 Or MeilleurKm > Distance Then
            PermuteVilles DicoKm, DicoVilleTmp, CStr(DicoVilleTmp.Keys(iVille)), VilleArrive, ParcoursTmp, DistanceTmp
        Else
            'On retourne la meilleur combinaison
            PermuteVilles = MeilleurParcours & "$" & CStr(MeilleurKm)
            Exit Function
        End If
    Next
 
    If DicoVilleTmp.Count = 0 Then
        'On boucle le trajet avec la ville d'arrivé
        If ParcoursEnCours <> "" Then ParcoursEnCours = ParcoursEnCours & "¤"
        ParcoursEnCours = ParcoursEnCours & VilleArrive
        Distance = Distance + DicoKm(VilleDepart & "¤" & VilleArrive)
        'On verifie les km
        If MeilleurKm = 0 Or MeilleurKm > Distance Then
            MeilleurKm = Distance
            MeilleurParcours = ParcoursEnCours
        End If
        'On vide les variables pour annalyser le prochain parcours
        Distance = 0
        ParcoursEnCours = ""
    End If
 
    'On retourne la meilleur combinaison
    PermuteVilles = MeilleurParcours & "$" & CStr(MeilleurKm)
 
End Function

[/Edit]

++
Qwaz

[philppe27]

Merci Qwarz le programme fonctionne très bien maintenant. C'est bien un parcours optimisé que j'obtiens.
Pour 12 étapes + départ+arrivée j'obtiens sur mon ordi un traitement d'environ 12 mn, je ne vois pas trop comment optimiser le temps de traitement. Qu'en penses tu ?

[Qwazerty]

Salut

Humm, pour la vitesse...
Peut-être en ordonnant le tableau de gauche dans un ordre particulier au niveau des distances... mais la comme ça je vois pas trop.

Par contre ton fichier semble avoir un problème, il y des liens externes qu'on ne peut pas modifier et le fait de le passer en format xlsm (2007+) rend le fichier illisible.

Voila un code qui permet d'analyser un peu ce qui se passe dans la boucle

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
Sub Villes()
 
Dim TabVilleEtape
Dim TheCell As Range
Dim DicoDistance As New Dictionary
Dim DicoVille As New Dictionary
Dim LastRow As Integer
Dim x As Integer, y As Integer
Dim TabRetour
 
 
 
    'On place les km dans le dico (plus rapide que d'aller chercher dans le tableau excel
    With ThisWorkbook.Sheets("Données")
        LastRow = .Range("B28").End(xlUp).Row
        TabVilleEtape = .Range("B7", .Cells(LastRow, "B").Offset(0, LastRow - 7)).Value
    End With
 
    'On boucle dans le tableau
    For x = 2 To LastRow - 6
        For y = 2 To LastRow - 6
            DicoDistance.Add TabVilleEtape(1, x) & "¤" & TabVilleEtape(1, y), CDbl(TabVilleEtape(x, y))
        Next
    Next
 
    'On récupère la liste des villes étapes
    With ThisWorkbook.Sheets("Données")
        For Each TheCell In .Range("X10", .Range("X29").End(xlUp))
            DicoVille.Add TheCell.Value, ""
        Next
    End With
 
 
    'On appelle PermuteVilles
    With ThisWorkbook.Sheets("Données")
        TabRetour = PermuteVilles(DicoDistance, DicoVille, .Range("X8"), .Range("X9"))
 
        'On place le meilleur parcours dans le tabelau excel
        'On vide
        .Range("Y8:Y28").ClearContents
        'On inscrit les km
        .Range("AA7").Value = Split(TabRetour, "$")(1)
        'On ne conserve que le parcours
        TabRetour = Split(TabRetour, "$")(0)
        'On permute la chaine en tableau
        TabRetour = Split(TabRetour, "¤")
        'On place le tableau
        .Range("Y8").Resize(UBound(TabRetour) + 1).Value = WorksheetFunction.Transpose(TabRetour)
 
    End With
 
 
End Sub
Function PermuteVilles(DicoKm As Dictionary, DicoVille As Dictionary, VilleDepart As String, VilleArrive, Optional aParcours As String = "<vide>", Optional aDistance As Double)
Dim DicoVilleTmp As New Dictionary
Dim iVille As Long
Static MeilleurKm As Double
Static MeilleurParcours As String
Static NbrPermute As Long
Dim ParcoursEnCours As String
Dim Distance As Double
 
Dim ParcoursTmp As String
Dim DistanceTmp As Double
 
    'On prolonge le parcours existant
    If aParcours <> "<vide>" Then
        ParcoursEnCours = aParcours
        Distance = aDistance
    Else
        'On initialise les variables "Meilleur", les variables static sont conservées, même aprés une analyse complete
        MeilleurKm = 0
        MeilleurParcours = ""
        'Et On début le parcours
        ParcoursEnCours = VilleDepart
        NbrPermute = 0
    End If
 
    'On clone le dico, moins la ville de départ
    For iVille = 0 To DicoVille.Count - 1
        If DicoVille.Keys(iVille) <> VilleDepart Then
            DicoVilleTmp.Add DicoVille.Keys(iVille), ""
        End If
    Next
 
    'On calcule les distances entre villeDepart et toutes les villes étapes
    For iVille = 0 To DicoVilleTmp.Count - 1
        NbrPermute = NbrPermute + 1
        'On ajoute la ville au parcours et distance temporaires, pour conserver les bon contenu dans ParcoursEnCours et Distance
        'Comme ça, après l'appel récursif, ParcoursEnCours et Distance contiennent les bonne valeur pour accépter le teste d'une nouvelle ville
        If ParcoursEnCours <> "" Then ParcoursTmp = ParcoursEnCours & "¤"
        ParcoursTmp = ParcoursTmp & DicoVilleTmp.Keys(iVille)
        DistanceTmp = Distance + DicoKm(VilleDepart & "¤" & DicoVilleTmp.Keys(iVille))
 
        'On note dans le tableau Excel (analyse)
        With ThisWorkbook.Sheets("Données")
            With .Cells(.Rows.Count, "B").End(xlUp).Offset(1)
                .Value = ParcoursTmp
                .Offset(0, 1) = DistanceTmp
            End With
        End With
 
        'Si la distance dépasse la distance la plus courte déjà trouvée
        If MeilleurKm = 0 Or MeilleurKm > Distance Then
            PermuteVilles DicoKm, DicoVilleTmp, CStr(DicoVilleTmp.Keys(iVille)), VilleArrive, ParcoursTmp, DistanceTmp
        Else
            'On retourne la meilleur combinaison
            PermuteVilles = MeilleurParcours & "$" & CStr(MeilleurKm) & " / " & NbrPermute
            Exit Function
        End If
    Next
 
    If DicoVilleTmp.Count = 0 Then
        'On boucle le trajet avec la ville d'arrivé
        If ParcoursEnCours <> "" Then ParcoursEnCours = ParcoursEnCours & "¤"
        ParcoursEnCours = ParcoursEnCours & VilleArrive
        Distance = Distance + DicoKm(VilleDepart & "¤" & VilleArrive)
        'On verifie les km
        If MeilleurKm = 0 Or MeilleurKm > Distance Then
            MeilleurKm = Distance
            MeilleurParcours = ParcoursEnCours
        End If
        'On vide les variables pour annalyser le prochain parcours
        Distance = 0
        ParcoursEnCours = ""
    End If
 
    'On retourne la meilleur combinaison
    PermuteVilles = MeilleurParcours & "$" & CStr(MeilleurKm) & " / " & NbrPermute
 
End Function

Mais bon ... je ne vois pas trop comment l'optimiser plus.
J'avais penser à regarder le trajet le plus court entre 2 ville, pour ensuite avant de tester le parcoursencours avec un nouvelle ville ajouter le parcours le plus court autant de fois que de ville restant à faire sur le teste en cours... mais avec 13km en trajet le plus court, ça ne donnera rien je pense.
++
Qwaz

[ZebreLoup]

Alors personne n'a lu mes messages au début du fil ? Snif

Tout d'abord, je proposais un algorithme qui marche bien et qui est beaucoup plus rapide que de tout tester. Mais bon, ça, chacun fait comme il veut.

Par contre, si on veut vraiment tout tester, il faut déjà reposer le problème comme je l'avais dit. C'est-à-dire que par exemple le graphique de Qwazerty ne marche pas. Si je reprends l'exemple des 4 villes Paris, Toulouse, Lyon et Montpellier. Paris-Montpellier et Lyon-Toulouse ne doivent pas être des distances données en paramètre, car elles ne sont pas connexes, tu dois de toute façon passer par une autre ville pour faire ces trajets.
Du coup, le nombre de possibilité ne va pas dépendre uniquement du nombre de villes, mais du nombre de routes qui relient les villes. On ne peut pas travailler avec les permutations, il faut travailler sur des arbres :
Si je pars d'une ville A, je regarde chaque ville qui est reliée à A par une route directe (Il faut donc retravailler un peu les hypothèses). Pour chaque ville, je recommence un algorithme récursif :
Je regarde toutes les villes reliées à ma ville actuelle (sauf la ville d'où j'arrive)
- Il n'y en a pas : cette branche est "morte", on l'oublie
- Une ville reliée est la ville d'arrivée : la branche est finie, on stocke le trajet complet et la distance pour comparaison.
- Pour toutes les autres villes reliées, je continue l'algorithme.

Ceci reste bien sûr l'algorithme bourrin (bien moins efficace que le Dijkstra), mais ça marchera tant qu'il n'y a pas trop de villes.

Avant de commencer à coder quoi que ce soit, enlève de tes paramètres tous les trajets qui ne sont pas "directs" !

[Qwazerty]

Salut
J'avoue ne pas m'y être intéressé car il me semble, peut-être à tord, que la liste des villes que l'on fourni est la liste des villes où on doit se rendre et non pas la liste des villes ou l'on peut potentiellement passer pour aller d'une ville à une autre.

Tu dis, on regarde l'arbre des possibles pour une ville donnée, si pas de ville connexe on oublie cette ville, sauf qu'on a une livraison à faire dans cette ville et qu'il va bien falloir y passer.
La solution du Path finder est valable uniquement pour trouver le trajet le plus court entre 2 points en ayant la liste des points qu'il est possible d’emprunter, alors que dans notre cas, on a la liste des point que l'on doit emprunter.

Mais peut-être ai-je mal abordé le sujet? A l'auteur du message de clarifier tout ça

++
Qwaz