Discussion :

[flicky]

Bonjour,
D'abord merci à l'avance a quiconque contribuera à ce que j'en arrive à règler mon problème.

J'ai passé beaucoup de temps à fouiller les forums et par extension, me retrouver à lire et tenter de comprendre un tant soit peu, un paquet de choses sur des problèmes NP-complet, divers algorithmes (Dijkstra, Lin-Kernigan, le cycle hamiltonien, le problème du voyageur de commerce, le problème du postier chinois, etc. ). Au final, je n'ai pas de solution à mon "problème", probablement du fait qu'il est toujours diffèrents en quelques sortes par rapport à la lecture que je fait.
Par exemple, le cas du voyageur de commerce m'apparait un fort bonne piste, mais dans mon cas il y a notamment la différence que je n'ai pas a organiser mon ittinéraire en considérant devoir revenir au point d'origine (ce qui devrait devrait avoir l'avantage d'être moins complexe...).

Voilà un fichier exposant où j'en suis :

Le but :
Créer des regroupements de lieux.

Les"consignes" que je dois respecter :
Je dois arriver a ralier tous les lieux identifiés (désigné par la lattitude (colonne H) et la longitude(colonne I)).
Je dois débuter par le lieux situé le plus au nord-est (désigné par la valeur la plus faible sur l'axe des X (colonne H) et la plus élevé sur l'axe des Y (colonne I)).
Je dois progresser en passant chaque fois par le lieux le plus près (distance à vol d'oiseau).

Je connais la population de chaque lieu (colonne L).
Chaque fois que le cumul de la population des lieux raliers dépasse 15 000 habitants, je dois créer un code (ex. : Regroup1; Regroup2, etc.) qui désigne les lieux inclut dans le regroupement et l'indiquer dans la colonne M.
Je débute ensuite un nouveau regroupement avec le lieux le plus près du dernier lieux inclut dans le regroupement précédent.
Autre petites contrainte : les regroupements ne doivent pas compter plus de 16 000 habitants, donc même si je n'ai pas atteint 15000 habitants dans un regroupement, je ferme ce regroupement plutot que de lui ajouter un lieu qui ferait passé sa population a plus de 16 000 habitants.

[mercatog]

Bonjour
Ci-joint proposition un peu lente (~3.5 min) testée sur ton fichier

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
Option Explicit
 
Const N As Byte = 3
Dim Sh As Worksheet
Dim Tb As Variant
Dim T As Double
 
Sub TRAITEMENT()
Dim LastLig As Long, Nb As Long
 
T = Timer
 
'Création d'une feuille temporaire et y copie les colonnes B, H et I à partir de la feuille BD
Set Sh = ThisWorkbook.Worksheets.Add
With ThisWorkbook.Worksheets("BD")
    LastLig = .Cells(.Rows.Count, 2).End(xlUp).Row
    Union(.Range("B5:B" & LastLig), .Range("H5:I" & LastLig)).Copy Sh.Range("A1")
End With
 
'Nb: nombre de données (nombre de points)
Nb = LastLig - 5
 
With Sh
    'On tri les données an prenant la latitude la plus grande
    .Range("A2:C" & Nb + 1).Sort Key1:=.Range("B2"), Order1:=xlDescending, Header:=xlNo
 
    'On refait un tri des données par ordre croissant des distances à partir du point 1
    'Appel à la procédure TRIER ci-après
    TRIER 2, Nb
 
    'On applique le traitement au tableau (procédures ci-après)
    Tb = .Range("A2:C" & Nb + 1)
    PARCOURS Nb
    .Range("A2:C" & Nb + 1) = Tb
    Erase Tb
 
    'Après traitement, on importe la population de chaque point
    With .Range("D2:D" & Nb + 1)
        .Formula = "=VLOOKUP(A2,BD!$B$6:$L$" & LastLig & ",11,FALSE)"
        .Value = .Value
    End With
    'on fait le regroupement des points selon la population globale
    Tb = .Range("A2:E" & Nb + 1)
    CLASSEMENT Nb
    .Range("A2:E" & Nb + 1) = Tb
End With
 
'on réinjecte le groupement dans la feuille BD
With ThisWorkbook.Worksheets("BD").Range("M6:M" & LastLig)
    .Formula = "=VLOOKUP(B6,'" & Sh.Name & "'!$A$2:$E$" & Nb + 1 & ",5,false)"
    .Value = .Value
End With
'Eventuellement on supprime la feuille temporaire
'Application.DisplayAlerts = False
'Sh.Delete
'Application.DisplayAlerts = True
Set Sh = Nothing
MsgBox "optimisation terminée en " & Format(TimeSerial(0, 0, Timer - T), "hh:mm:ss")
End Sub
 
'procédure qui permet de refaire l'inversion de l'ordre des point tant que la permutation permet de diminuer
'la distance total du parcours (Cf fonction DIFF_2OPT)
 
Private Sub PARCOURS(ByVal Nb As Integer)
Dim p As Integer, q As Integer
Dim Modif As Boolean
Dim Ind As Byte
 
Do
    Modif = False
    Ind = Ind + 1
    For p = 2 To Nb - 1
        For q = p + 1 To Nb
            If DIFF_2OPT(p, q, Nb) < 0 Then
                RENVERSE p, q
                Modif = True
                Application.StatusBar = "Traitement en cours...   Passage " & Ind & " : " & p & " et " & q & "   " & Format(TimeSerial(0, 0, Timer - T), "hh:mm:ss")
            End If
            DoEvents
        Next q
    Next p
Loop Until Not Modif
Application.StatusBar = False
End Sub
 
'Procédure permetant de trier les points d'un échantillon de Nb points
'en prenant comme critère la distance de chaque point par rapport au point k
Private Sub TRIER(ByVal k As Integer, ByVal Nb As Integer)
Dim m As Integer
 
With Sh
    Tb = .Range("A" & k & ":C" & Nb + 1)
    For m = k To Nb + 1
        With .Range("D" & m)
            .Formula = "=Distance(" & k - 1 & "," & m - 1 & ")"
            .Value = .Value
        End With
    Next m
    .Range("A" & k & ":D" & Nb + 1).Sort Key1:=.Range("D" & k), Order1:=xlAscending, Header:=xlNo
    .Range("D" & k & ":D" & Nb + 1).ClearContents
End With
End Sub
 
'procédure qui permet le regroupement des points successifs
'en respactant que la population globale =>15000 et >160000
Private Sub CLASSEMENT(ByVal Nb As Integer)
Dim i As Integer, Indx As Integer
Dim T As Long
 
Indx = 1
For i = 1 To Nb
    T = T + Tb(i, 4)
    Tb(i, 5) = "Groupe_" & Indx
    If T >= 15000 Then
        If T < 16000 Then
            Indx = Indx + 1
            T = 0
        Else
            T = Tb(i, 4)
        End If
    End If
Next i
End Sub
 
 
'Fonction qui permet de claculer la distances entre 2 points i et j
'connaissant les latitudes et longitudes respectives de i et j
Function DISTANCE(ByVal i As Integer, ByVal j As Integer) As Double
Dim Lat1 As Double, Lat2 As Double, Lon1 As Double, Lon2 As Double
Const R As Integer = 6371                          ' de la terre, en km
 
Lat1 = DEG2RAD(Tb(i, 2))
Lon1 = DEG2RAD(Tb(i, 3))
Lat2 = DEG2RAD(Tb(j, 2))
Lon2 = DEG2RAD(Tb(j, 3))
' Calcul
DISTANCE = WorksheetFunction.Acos((Sin(Lat1) * Sin(Lat2)) + (Cos(Lat1) * Cos(Lat2) * Cos(Lon1 - Lon2))) * R
 
End Function
 
' Fonction qui convertit les degrés en radians
Private Function DEG2RAD(ByVal Dg As Double) As Double
Dim pPi As Double
pPi = Application.WorksheetFunction.Pi()
 
DEG2RAD = Dg / 180 * pPi
End Function
 
'Permute les points i et j (dans notre cas on permute respctivement le N°, la latitude et la longitude de i et j)
Private Sub PERMUTE(ByVal i As Integer, ByVal j As Integer)
Dim Tmp(1 To N) As Variant
Dim y As Byte
 
If i <> j Then
    For y = 1 To N
        Tmp(y) = Tb(i, y)
        Tb(i, y) = Tb(j, y)
        Tb(j, y) = Tmp(y)
    Next y
End If
End Sub
 
'Renverse le parcours entre les villes i et j
Private Sub RENVERSE(ByVal i As Integer, ByVal j As Integer)
Dim a As Integer, b As Integer
 
a = Application.Min(i, j)
b = Application.Max(i, j)
Do While a < b
    PERMUTE a, b
    a = a + 1
    b = b - 1
    DoEvents
Loop
End Sub
 
'Différence de la distance du parcours si on renversait les villes i et j
Private Function DIFF_2OPT(ByVal i As Integer, ByVal j As Integer, ByVal Nb As Integer) As Double
Dim d As Double
 
If i < j Then
    d = DISTANCE(i - 1, j) - DISTANCE(i - 1, i)
    If j < Nb Then d = d + DISTANCE(i, j + 1) - DISTANCE(j, j + 1)
    DIFF_2OPT = d
End If
End Function

[flicky]

Franchement Mercatog ta réponse est bien bien au dela de mes attentes, Elle est pour moi (et mon confrère) d'une qualité exceptionnelle.
Je m'attendais à des pistes de solutions, j'aurais jamais cru recevoir une solution "clé en main".
Sincèrement un immense merci à toi.

Bien sur je navais pas exposé ma problématique entière, mais plutot une version sommaire visant a obtenir des pistes de solutions "de logique de résolution". Je suis confiant de pouvoir adapter ta solution par moi-même.

Encore merci !!

[mercatog]

Bonsoir
Néanmoins, une petite modification dans ma procédure de regroupement

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
'procédure qui permet le regroupement des points successifs
'en respactant que la population globale =>15000 et >160000
Private Sub CLASSEMENT(ByVal Nb As Integer)
Dim i As Integer, Indx As Integer
Dim T As Long
 
Indx = 1
For i = 1 To Nb
    T = T + Tb(i, 4)
    Tb(i, 5) = "Groupe_" & Indx
    If T >= 15000 Then
        Indx = Indx + 1
        If T < 16000 Then
            T = 0
        Else
            T = Tb(i, 4)
            Tb(i, 5) = "Groupe_" & Indx
        End If
    End If
Next i
End Sub

[aldus_85]

Bonjour !

Voici une proposition, dans un style différent par rapport à Mercatog. Comme l'indique le titre, cette solution n'utilise ni macro ni VBA. Elle utilise cependant l'itération pour faire le job.

Moins de 40 s sur ma bécane pour traiter la base de données fournie.

P.S. le point de départ est le premier point donné. Si cela ne convenait pas, placer en premier le point qui va bien ou mettre "1" d'autorité à la ligne du point choisi.

[ZebreLoup]

Juste une petite remarque au passage. Etant donné les contraintes de ton problème, il n'y avait qu'une seule solution et donc aucune optimisation nécessaire. Tu étais parti sur des choses un peu trop compliquées avec le voyageur de commerce ou autre. Il suffisait d'implémenter l'algorithme que tu décrivais, ce qu'ont fait Mercatog et Aldus de 2 manières différentes.

[aldus_85]

En fait, compte tenu des règles, on ne peut pas établir dès le départ une hiérarchie des points à partir de laquelle on pourrait faire le regroupement.

Il suffit d'imaginer un chemin fait de petites distances pour aller par exemple au point le plus éloigné du départ. On passera d'abord sur le point le plus éloigné avant de passer sur des points plus proches.

Cette particularité est d'ailleurs étrange, car le trajet donc les frontières de regroupement vont dépendre du point de départ et de l'existence de chaines à maillons courts : mais là, on touche au sens des consignes choisies, ... " et cela ne nous regarde pas" (je cite les inconnus, un groupe d'humoristes, à l'attention de nos amis canadiens)

[ZebreLoup]

Il y a peut-être quelque chose que je n'ai pas saisi alors. Tu dis à chaque fois que tu passes par le lieu le plus proche. Donc ton trajet est complètement déterministe dès le début. Il suffit dans une deuxième passe de définir les regroupements.

Si je fais erreur, les solutions qui t'ont été proposées ne sont peut-être plus les bonnes du coup.

[mercatog]

Bonjour à tous
Si j'ai bien compris, c'est dans un premier temps chercher à optimiser la parcours entre deux points en passant par l'ensemble des points une seule fois (pas nécessairement passer par le point i et le point le plus proche de i)
Ensuite de faire le groupement.

Une remarque au passage, la distance entre 2 points connaissant leur latitude et longitude est donnée par

d=Arcos(cos(Lat1)cos(Lat2)cos(Lon1-Lon2)+sin(Lat1)sin(lat1))*R

avec R~6371 (rayon de la terre et les latitudes/longitudes en radian.

le code proposé plus haut permet d'utiliser l'algoritme 2-opt (définition), càd sommairement chercher à renverser la trajet entre les points i et j si cette opération permettrait de minimiser la distance globale du trajet (Calcul du gain apporté) et recommencer tant qu'il y a possibilité de renversement.

La principale limite de 2-opt réside dans le fait qu’il ne fournit pas de garantie satisfaisante quant à la qualité de la solution finale: l’algorithme est sujet à tomber dans des minima locaux assez rapidement. On note aussi que la nature de la solution initiale influe grandement sur les résultats

[flicky]

Bonjour à vous qui travaillé sur mon problème,

Dès qu'on a eu la proposition de mercatog, on a planché dessus pour voir les possibilités qu'elle nous offre on est très emballé, mais on a certaines intérogations que je vais partager plus tard une fois que j'aurai eu la possibilité d'échanger avec mon collègue.

J'ai aussi commencé a regarder la proposition d'aldus_85, également fort impressionnante, toutefois, lorsqu'appliqué à notre projet, certaines particularités émerge et je vais aussi faire part de mes questions d'ici quelques heures une fois que j'aurai cela sur "papier".

Un IMMENSE merci de votre collaboration.

[aldus_85]

Oui, tout-à-fait Mercatog.

En fait, je ne me suis pas fais suer : j'ai utilisé une "distance" au sens mathématique qui assure le même classement que la "vraie" distance. Autrement dit, il me suffit que d(A,B)<d(A,C) <=> d'(A,B)<d'(A,C) <=> d"(A,B)<d"(A,C) pour tous les points avec les différentes distances : corde, corde au carré, longueur d'arc. J'ai pris ce qui était le plus facile à calculer.

De plus, pour moins de 30 km sur un rayon de 6500 km, l'écart est très faible (erreur relative de 4.E-6). Sur des distances supérieures,l'approximation plane devient évidemment fausse et la formule de Mercatog nécessaire.

En terme d'algorithme, je calcule le point le plus proche parmi ceux qui restent, puis j'"inactive" ledit point. Et je recommence. Je ne connaissais pas opt-2 mais dans mon algorithme, il n'y a pas de dépendance par rapport à une configuration de départ, autre que la dépendance intrinsèque au premier point défini par flicky.

[mercatog]

Bonjour aldus_85
La question qui se pose est si la somme des distances minimales entre les points (point i et le point le plus proche parmi ceux qui restent, selon tes termes) donne la trajet optimal.

Trace un graphique "Nuage de point avec courbe droites) sur le résultat trouvé, tu constatera la forme du trajet global à suivre.

Ou bien fais le calcul de la distance globale à parcourir.

[aldus_85]

Bonjour Mercatog !

En fait, tu as du le lire pour réaliser le programme, on doit :
- partir du point le plus "à l'est" et "au nord" ... ce qui déjà pose problème puisque de mémoire, il n'y a pas de point qui occupe le coin en haut à gauche
- aller au point suivant le plus proche ... ce qui est, comme tu l'as remarqué, source

Comme tu le recommandais, j'avais regardé la trajectoire et observé son drôle de cheminement. En même temps, cela fait expressément partie du cahier des charges.

Je pense que flicky s'est peut-être aperçu de cela avec son collègue car il voulaient faire un point, et je pense qu'il s'agit notamment de la méthode d'agrégation des populations, et donc de la sélection des villes/villages à regrouper.

Let's wait and see !

[Noé_noir]

Bonjour à vous,
Je salue l’initiative de Flicky d’avoir lancé ma question sur votre site. Je suis impressionné par votre intérêt et votre implication dans la recherche d’une solution.
J’ai cartographié la proposition de Mercatog et de Aldus_85.
À la première lecture, je constate que la recherche du « plus proche voisin » peut mener :
1- à des regroupements qui sont moins compacts que ce qui était espéré (ex. : groupes 1, 2, 3, 4 et 8 de Mercatog et groupes 1, 2, 3, 7 et 13 d’Aldus_85)
2- à la formation de groupes constitués de sous-groupes disjoints (groupes 8, 13 et 16 de Mercatog et groupes 4, 9, 10, 13, 14, 15, 18 et 19 d’Aldus_85)
3- la gestion des résidus (groupes 17 et 18 d’Aldus)
Je m’interroge sur la possibilité d’utiliser le centroïde (valeur moyenne des X et valeur moyenne des Y) du groupe en formation (à partir de la recherche de la troisième coordonnée XY) comme point de départ pour la recherche du voisin le plus proche. Est-ce que cela réduirait ou annulerait les effets négatifs mentionnés en 1 et 2 ?

[aldus_85]

Bonjour Noé_Noir !

Fun de voir :
1 - le résultat de nos algorithmes en couleur !
2 - de voir à quel points les mêmes consignes donnent des résultats aussi dissemblables. Avons-nous, Mercatog et moi, vraiment bien respecté les consignes ? Je ne comprends pas qu'il puisse y avoir ainsi de telles différences de résultat pour un processus déterministe.

Je suis heureux de voir de visu l'effet de plus "courte chaine" présent dans la consigne. On voit très bien qu'à cause des petits territoires (et du mode d'agrégation) on peut faire le tour de la presqu'ile pour finalement revenir au point de départ.

Pour aller plus loin, et tenter de répondre à la question posée, quitte à abandonner provisoirement le strict champ de la programmation, peut-être devrais-tu nous expliquer, au moins superficiellement, ce que vous essayez de faire. Cela permettrait peut-être de trouver une métrique adaptée !

Trop cool la cartographie !!

Bonne soirée !

[mercatog]

Bonsoir
Suite à la nouvelle cartographie, je m'aperçois que j'avais répondu à un autre problème:
A partir d'un ensemble de points, chercher le trajet "optimal" passant une seule fois par chaque point.
Ensuite faire le groupement entre les points successif du trajet "optimal" trouvé.

En réalité, il ne s'agit pas de points (avec des coordonnées) , mais d'un ensemble de surfaces centrées ou non sur les points précités.

[Noé_noir]

Bonsoir,

Effectivement Mercatog, chacune des coordonnées correspond au centroide géométrique de secteur de résidence. J’ai été surpris du résultat de l’utilisation du cycle hamiltonien pour la construction de territoires.

Pour répondre à la demande d’Aldus_85, je vous explique le but de l’exercice. Il s’agit d’imaginer une analyse spatiale permettant l’identification d’aires de patientèle sur la base desquelles serait offert un service de proximité (dans le cas qui m’occupe, un service de santé ou un service social offert à l’ensemble ou à un sous-ensemble de la population). Comme il s’agit d’un service de proximité (géographique), ces aires doivent être les plus compactes possible afin d’occasionner un minimum d’effort pour y recourir.

Merci de votre patience

[aldus_85]

Tout est dans le titre !

Bonjour !

Noé_noir, qu'est-ce que tout cela a donné au final ?

Salut !