5.9.3 Analyses des résultats
Les algorithmes présentés ont été
codés en C++ et exécutés sur un processeur AMD X2 3800+
cadencé à 2 Ghz avec 1 Go de mémoire vive. Les 17
premières séries d'instances contiennent jusqu'à 40
clients et 127 objets. Chaque série contient 5 instances. Ces instances
ont été résolues de manière exacte par une
méthode de séparation et génération de coupe (Iori
et al., 2007). Par rapport aux instances originales du CVRP, les arcs
sont arrondis à la prochaine valeur entière. Dans la plupart des
cas, les solutions optimales sont connues.
Le tableau 5.4 présente les résultats
agrégés par série d'instances obtenus sur les 85 instances
de taille moyenne. Nos résultats (HBP) sont comparés avec la
méthode Branch & Cut proposée par Iori et al.
(2007), la recherche Tabou proposée par Gendreau et al.
(2008) et l'algorithme d'optimisation par Colonie de Fourmis de Fuellerer
et al. (2008).
Inst
|
client
|
Class 2 obj. vh r%
|
Class 3 obj. vh r%
|
Class 4 obj. vh
|
r%
|
Class 5 obj. vh r%
|
1
|
15
|
24
|
3
|
78
|
31
|
3
|
82
|
37
|
4
|
70
|
45
|
4
|
61
|
2
|
15
|
25
|
5
|
52
|
31
|
5
|
59
|
40
|
5
|
53
|
48
|
5
|
39
|
3
|
20
|
29
|
5
|
68
|
46
|
5
|
77
|
44
|
5
|
62
|
49
|
5
|
54
|
4
|
20
|
32
|
6
|
58
|
43
|
6
|
58
|
50
|
6
|
63
|
62
|
6
|
47
|
5
|
21
|
31
|
4
|
72
|
37
|
4
|
75
|
41
|
4
|
76
|
57
|
5
|
53
|
6
|
21
|
33
|
6
|
54
|
40
|
6
|
63
|
57
|
6
|
72
|
56
|
6
|
46
|
7
|
22
|
32
|
5
|
71
|
41
|
5
|
66
|
51
|
5
|
67
|
55
|
6
|
49
|
8
|
22
|
29
|
5
|
63
|
42
|
5
|
71
|
48
|
5
|
68
|
52
|
6
|
38
|
9
|
25
|
40
|
8
|
57
|
61
|
8
|
61
|
63
|
8
|
60
|
91
|
8
|
53
|
10
|
29
|
43
|
6
|
74
|
49
|
6
|
66
|
72
|
7
|
73
|
86
|
7
|
63
|
11
|
29
|
43
|
6
|
77
|
62
|
7
|
74
|
74
|
7
|
83
|
91
|
7
|
63
|
12
|
30
|
50
|
9
|
62
|
56
|
9
|
52
|
82
|
9
|
66
|
101
|
9
|
58
|
13
|
32
|
44
|
7
|
69
|
56
|
7
|
68
|
78
|
7
|
77
|
102
|
8
|
59
|
14
|
32
|
47
|
7
|
65
|
57
|
7
|
65
|
65
|
7
|
61
|
87
|
8
|
49
|
15
|
32
|
48
|
6
|
76
|
59
|
6
|
84
|
84
|
8
|
72
|
114
|
8
|
72
|
16
|
35
|
56
|
11
|
55
|
74
|
11
|
57
|
93
|
11
|
64
|
114
|
11
|
49
|
17
|
40
|
60
|
14
|
46
|
73
|
14
|
42
|
96
|
14
|
51
|
127
|
14
|
40
|
18
|
44
|
66
|
9
|
72
|
87
|
10
|
75
|
112
|
10
|
77
|
122
|
10
|
58
|
19
|
50
|
82
|
11
|
77
|
103
|
11
|
83
|
134
|
12
|
79
|
157
|
12
|
61
|
20
|
71
|
104
|
14
|
84
|
151
|
15
|
83
|
178
|
16
|
81
|
226
|
16
|
69
|
21
|
75
|
114
|
14
|
84
|
164
|
17
|
82
|
168
|
17
|
70
|
202
|
17
|
61
|
22
|
75
|
112
|
15
|
82
|
154
|
16
|
81
|
198
|
17
|
82
|
236
|
17
|
66
|
23
|
75
|
112
|
14
|
86
|
155
|
16
|
83
|
179
|
16
|
83
|
225
|
16
|
72
|
24
|
75
|
124
|
17
|
81
|
152
|
17
|
77
|
195
|
17
|
82
|
215
|
17
|
66
|
25
|
100
|
157
|
21
|
83
|
212
|
21
|
85
|
254
|
22
|
83
|
311
|
22
|
65
|
26
|
100
|
147
|
19
|
84
|
198
|
20
|
82
|
247
|
20
|
87
|
310
|
20
|
75
|
27
|
100
|
152
|
19
|
84
|
211
|
22
|
82
|
245
|
22
|
78
|
320
|
22
|
71
|
28
|
120
|
183
|
23
|
83
|
242
|
25
|
83
|
299
|
25
|
84
|
384
|
25
|
72
|
29
|
134
|
197
|
24
|
85
|
262
|
26
|
83
|
342
|
28
|
85
|
422
|
28
|
74
|
30
|
150
|
225
|
29
|
83
|
298
|
30
|
87
|
366
|
30
|
86
|
433
|
30
|
70
|
31
|
199
|
307
|
38
|
84
|
402
|
40
|
85
|
513
|
42
|
86
|
602
|
42
|
70
|
32
|
199
|
299
|
38
|
84
|
404
|
39
|
85
|
497
|
39
|
86
|
589
|
39
|
73
|
33
|
199
|
301
|
37
|
85
|
407
|
41
|
84
|
499
|
41
|
87
|
577
|
41
|
71
|
34
|
240
|
370
|
46
|
85
|
490
|
49
|
86
|
604
|
50
|
86
|
720
|
50
|
72
|
35
|
252
|
367
|
45
|
85
|
507
|
50
|
85
|
634
|
50
|
90
|
762
|
50
|
74
|
36
|
255
|
387
|
47
|
86
|
511
|
51
|
86
|
606
|
51
|
83
|
786
|
51
|
74
|
TABLE 5.3 -
Caractéristiques des classes d'instances
Les en-têtes sont les suivants :
- I : numéro de l'instance,
- n : nombre de clients,
- Branch & Cut : valeur des solutions (z) et temps
d'exécution en secondes (CPU),
Chapitre 5. Application au problème de Tournées de
Véhicules avec Contraintes de Chargement
- Tabu Search : valeur des solutions (z), temps
d'exécution en secondes (CPU) et différence avec les solutions
proposées par Iori et al. (2007),
- ACO : valeur moyenne des solutions (z) sur 5 essais, temps
d'exécution en se-
condes (CPU) et différence avec les solutions
proposées par Iori et al. (2007),
- HBP : valeur des solutions (z), temps d'exécution en
secondes (CPU) et différence
avec les solutions proposées par Iori et al.
(2007).
La lecture des résultats nous permet de dire que notre
méthode semble intéressante. Elle est en moyenne moins efficace
que la méthode ACO proposée par Fuellerer et al. (2008),
mais permet d'obtenir de bons résultats en des temps d'exécutions
raisonnables. En limitant le temps à une heure (limite de temps qui
n'est jamais atteinte pour ces instances), elle permet d'améliorer
certaines instances non résolues à l'optimum dans la limite de
temps de 24 heures par la méthode de Branch & Bound de Iori et
al. (2007) (ce qui explique que dans certains cas le pourcentage de
différence avec les solutions optimales soit négatif). Les temps
d'exécution sont similaires au temps des autres méthodes.
Néanmoins, il semble que les heuristiques de chargement utilisées
ne permettent pas de retrouver toutes les routes réalisables
relativement aux contraintes de chargement, ce qui explique des
résultats inférieurs aux méthodes les plus
performantes.
I
|
n
|
Branch & Cut
z CPU
|
Tabu search z CPU
|
Gap
|
ACO z CPU
|
gap
|
z
|
HBP CPU
|
gap
|
1
|
15
|
281
|
29.9
|
281.4
|
7.6
|
0.14
|
286.4
|
8.9
|
1.92
|
285
|
12.1
|
1.42
|
2
|
15
|
336.6
|
14.7
|
337.2
|
3.9
|
0.18
|
337.4
|
0.7
|
0.24
|
337.8
|
4.5
|
0.36
|
3
|
20
|
375.4
|
25.4
|
377.6
|
18
|
0.59
|
376.6
|
7
|
0.32
|
378.2
|
15.6
|
0.75
|
4
|
20
|
430
|
17
|
433.8
|
14
|
0.88
|
431
|
4.1
|
0.23
|
433.6
|
15.1
|
0.84
|
5
|
21
|
377.2
|
597.8
|
387
|
28.8
|
2.6
|
378
|
19.5
|
0.21
|
385
|
27.3
|
2.07
|
6
|
21
|
490.4
|
67.4
|
494.6
|
23.1
|
0.86
|
491.7
|
5.6
|
0.27
|
495.2
|
22.4
|
0.98
|
7
|
22
|
687.2
|
676.3
|
699.8
|
39.2
|
1.83
|
690
|
11.9
|
0.41
|
698.6
|
31.5
|
1.66
|
8
|
22
|
705.8
|
261.6
|
717.4
|
45
|
1.64
|
713.1
|
16.6
|
1.03
|
718.6
|
38.7
|
1.81
|
9
|
25
|
614.2
|
469.9
|
616.6
|
38.2
|
0.39
|
616
|
8.3
|
0.29
|
616.6
|
32.8
|
0.39
|
10
|
29
|
676
|
51791.2
|
684
|
150.8
|
1.18
|
666.9
|
48.6
|
-1.35
|
678
|
72.9
|
0.3
|
11
|
29
|
725.6
|
69120.4
|
718.4
|
175.7
|
-0.99
|
691.7
|
134
|
-4.67
|
724.2
|
183.5
|
-0.19
|
12
|
30
|
609.4
|
86400.4
|
612
|
87.3
|
0.43
|
602.3
|
12.9
|
-1.17
|
610.4
|
74.2
|
0.16
|
13
|
32
|
2713.6
|
58268
|
2588.4
|
296.2
|
-4.61
|
2540.7
|
59
|
-6.37
|
2653.6
|
259.4
|
-2.21
|
14
|
32
|
1233.4
|
74228.8
|
1157.8
|
343.3
|
-6.13
|
1146
|
131.9
|
-7.09
|
1181.4
|
354.8
|
-4.22
|
15
|
32
|
1252.6
|
69124.2
|
1191.6
|
308
|
-4.87
|
1182.4
|
235.2
|
-5.6
|
1201.6
|
291.8
|
-4.07
|
16
|
35
|
683.8
|
10098.1
|
686.4
|
161.8
|
0.38
|
684.9
|
11.1
|
0.16
|
687.4
|
212.5
|
0.53
|
17
|
40
|
854.6
|
86400.3
|
844.4
|
234.7
|
-1.19
|
846.2
|
9.4
|
-0.98
|
848.8
|
176.3
|
-0.68
|
Moyenne
|
767.46
|
29858.32
|
754.61
|
116.21
|
-0.39
|
745.96
|
42.63
|
-1.3
|
760.82
|
107.38
|
-0.01
|
TABLE 5.4 - Résultats
expérimentaux : qualité des solutions sur instances
moyennes
Le tableau 5.5 présente les résultats
agrégés par série d'instances obtenus sur les 180
instances de grande taille. Dans ces instances, les distances ne sont pas
arrondies à la prochaine valeur entière. Les en-têtes des
colonnes sont les mêmes que les en-têtes
du tableau précédent, à la
différence que la qualité des solutions est calculée
relativement aux solutions fournies par la recherche Tabou de Gendreau et
al. (2008). À ce jour, aucune méthode de résolution
exacte n'a été proposée.
Les résultats présentés dans le tableau
5.5 sont similaires aux résultats des solutions sur les instances de
taille moyenne. Notre méthode est moins performante que la
méthode d'Optimisation par Colonie de Fourmis de Fuellerer et al.
(2008), que ce soit en terme de qualité des solutions ou de temps
d'éxécution. Cependant, les résultats obtenus par notre
méthode sont comparables en terme de qualité et de temps avec la
méthode de Recherche Tabou de Gendreau et al. (2008).
Enfin, le tableau 5.6 présente les résultats
agrégés sur les 180 instances pour nos deux méthodes
heuristiques. La différente de qualité de solution de la
méthode de génération de routes réalisables est
calculée relativement aux valeurs de solutions de la méthode de
Branch & Price heuristique.
Très clairement, la méthode de
génération de routes réalisables (HCG) est de moins bonne
qualité que la méthode de Branch & Price heuristique(HBP)
avec en moyenne un pourcentage de différence proche de 20%. Cela
s'explique par le fait que la méthode de génération de
routes réalisables ne fait appel qu'à une seule heuristique de
chargement. De plus, une fois que les objets sont insérés, le
chargement de ceux-ci n'est jamais remis en question. Ainsi, un nombre
important de routes réalisables ne sont pas ajoutées. On peut
cependant noter que cette méthode est plus rapide que la méthode
de Branch & Price heuristique, ce qui s'explique encore une fois par
l'utilisation limitée des heuristiques de chargement.
|