5.10 Conclusions et perspectives
Dans ce chapitre, nous avons proposé une
résolution heuristique du problème de Tournées de
Véhicules avec Contraintes de Chargement. De par la complexité
des contraintes de chargement, ce problème n'est pas résolu par
une approche exacte. Nous avons montré un aperçu des
possibilités qu'il existait pour tronquer la méthode de Branch
& Price, qui est une méthode a priori exacte. Les approches
heuristiques que nous proposons permettent d'accélérer la
résolution. Il est cependant clair que la qualité des
heuristiques de chargement est déterminante dans la qualité des
solutions. Malgré une utilisation de plusieurs heuristiques de
chargement, les résultats que nous proposons ne permettent pas de
dépasser les meilleurs résultats connus. Cependant, que ce soit
en terme de qualité de solution ou en temps d'éxécution,
nos résultats restent dans une moyenne des méthodes
publiées à ce jour.
Les perspectives de recherche sur ce chapitre sont nombreuses.
Les résultats que nous présentons pourraient être
améliorés par l'utilisation d'heuristiques de chargement plus
efficaces. Enfin, les résultats de la méthode de
génération de routes réalisables ne sont pas à la
hauteur de nos espérances. Cependant, on peut noter que cette
méthode peut être une base de futurs travaux de recherche, dans le
but de proposer une
Chapitre 5. Application au problème de Tournées de
Véhicules avec Contraintes de Chargement
|
I
|
n
|
Tabu Search
z CPU
|
z
|
ACO
CPU
|
Gap
|
z
|
HBP
CPU
|
Gap
|
|
1
|
15
|
295.01
|
9.2
|
291.83
|
7.2
|
-1.08
|
294.21
|
11.6
|
-0.27
|
|
2
|
15
|
343.18
|
3.5
|
343.22
|
0.6
|
0.01
|
343.2
|
4.4
|
0.01
|
|
3
|
20
|
380.19
|
18.9
|
378.18
|
3.1
|
-0.51
|
382.56
|
15.2
|
0.62
|
|
4
|
20
|
440.91
|
17
|
439.07
|
3
|
-0.41
|
440.51
|
18.7
|
-0.09
|
|
5
|
21
|
382.3
|
27.6
|
381.63
|
12.8
|
-0.17
|
382.68
|
27.5
|
0.1
|
|
6
|
21
|
501.4
|
19.5
|
499.77
|
4.3
|
-0.32
|
502.56
|
21.8
|
0.23
|
|
7
|
22
|
691.23
|
53
|
678.22
|
11.7
|
-1.79
|
690.11
|
31.3
|
-0.16
|
|
8
|
22
|
691.89
|
83.7
|
684.37
|
16.1
|
-1.02
|
690.85
|
37.2
|
-0.15
|
|
9
|
25
|
620.77
|
40
|
614.88
|
4.9
|
-0.93
|
618.65
|
31.8
|
-0.34
|
|
10
|
29
|
679.68
|
179.6
|
668.48
|
50.1
|
-1.64
|
680.56
|
73.5
|
0.13
|
|
11
|
29
|
719.76
|
199.4
|
690.22
|
57.8
|
-3.51
|
716.84
|
201.2
|
-0.41
|
|
12
|
30
|
627.59
|
99.5
|
615.9
|
7.4
|
-1.77
|
631.51
|
76.8
|
0.62
|
|
13
|
32
|
2550.89
|
312.8
|
2480.04
|
61.8
|
-2.6
|
2560.22
|
282.6
|
0.37
|
|
14
|
32
|
1048.72
|
439.5
|
1007.92
|
163.1
|
-3.69
|
1043.16
|
392.3
|
-0.53
|
|
15
|
32
|
1160.25
|
313.4
|
1145.96
|
138.8
|
-1.17
|
1161.65
|
315.2
|
0.12
|
|
16
|
35
|
703.6
|
157.2
|
701.09
|
8.3
|
-0.35
|
702.69
|
191.7
|
-0.13
|
|
17
|
40
|
865.72
|
226.2
|
864.92
|
7.2
|
-0.09
|
864.39
|
190.8
|
-0.15
|
|
18
|
44
|
1037.65
|
1167.8
|
1003.84
|
292.6
|
-3.03
|
1026.18
|
1745.8
|
-1.11
|
|
19
|
50
|
746.91
|
1521.5
|
728.89
|
122.1
|
-2.15
|
759.37
|
1429.1
|
1.67
|
|
20
|
71
|
513.84
|
3370.3
|
484.23
|
1073.8
|
-4.95
|
517.48
|
3251.2
|
0.71
|
|
21
|
75
|
1025.79
|
3561.2
|
987.54
|
1037.3
|
-3.4
|
1023.93
|
3600.1
|
-0.18
|
|
22
|
75
|
1052.39
|
3461.8
|
1018.76
|
738.9
|
-2.89
|
1053.1
|
3600
|
0.07
|
|
23
|
75
|
1121.18
|
3600
|
1051.16
|
1206.5
|
-5.71
|
1119.74
|
3600.2
|
-0.13
|
|
24
|
75
|
1208.52
|
3324.6
|
1134.9
|
323.4
|
-5.62
|
1211.34
|
3600.2
|
0.23
|
|
25
|
100
|
1350.56
|
3600.1
|
1309.98
|
2454.9
|
-2.74
|
1346.13
|
3600.5
|
-0.33
|
|
26
|
100
|
1341.3
|
3600.3
|
1306.24
|
3558.1
|
-2.52
|
1337.84
|
3600.5
|
-0.26
|
|
27
|
100
|
1439.37
|
3600
|
1341.25
|
1570.3
|
-6.3
|
1431.29
|
3600.4
|
-0.56
|
|
28
|
120
|
2502.48
|
3600.1
|
2417.89
|
8714.5
|
-2.16
|
2494.36
|
3600.5
|
-0.32
|
|
29
|
134
|
2296.03
|
3600.2
|
2131.54
|
8837.5
|
-6.02
|
2279.63
|
3600.5
|
-0.71
|
|
30
|
150
|
1873.27
|
3600.2
|
1734.46
|
8720.3
|
-6.9
|
1871.62
|
3600.2
|
-0.09
|
|
31
|
199
|
2366.54
|
3600.5
|
2219.34
|
8747.4
|
-6.27
|
2354.68
|
3600.9
|
-0.5
|
|
32
|
199
|
2354.6
|
3600.6
|
2191.97
|
8745.8
|
-6.21
|
2353.78
|
3600.4
|
-0.03
|
|
33
|
199
|
2360.74
|
3600.6
|
2245.46
|
8742.7
|
-4.45
|
2354.8
|
3600.5
|
-0.25
|
|
34
|
240
|
1408.64
|
3601
|
1160.98
|
8771.6
|
-17.51
|
1421.21
|
3600.8
|
0.89
|
|
35
|
252
|
1786.93
|
3600.2
|
1465.85
|
8942.2
|
-16
|
1798.55
|
3602
|
0.65
|
|
36
|
255
|
1693.1
|
3600.9
|
1603.86
|
9011.7
|
-5.46
|
1694.2
|
3600.8
|
0.06
|
|
moyenne
|
1171.75
|
1817
|
1111.77
|
2560.27
|
-3.65
|
1170.99
|
1832.17
|
-0.01
|
TABLE 5.5 - Résultats
expérimentaux : qualité des solutions sur l'ensemble des
instances
résolution exacte du problème de Tournées
de Véhicules avec Contraintes de Charge-
ment. Nous avons
montré que dans le cas d'une résolution exacte du
sous-problème,
cette méthode peut proposer une
résolution exacte. Cela pourrait permettre de trouver
|
I
|
n
|
HBP
z CPU
|
z
|
HCG
CPU
|
Gap
|
|
1
|
15
|
294.21
|
11.6
|
296.56
|
5.6
|
0.8
|
|
2
|
15
|
343.2
|
4.4
|
369.2
|
3.1
|
7.58
|
|
3
|
20
|
382.56
|
15.2
|
391.26
|
10.2
|
2.27
|
|
4
|
20
|
440.51
|
18.7
|
469.2
|
9.7
|
6.51
|
|
5
|
21
|
382.68
|
27.5
|
402.18
|
12.1
|
5.1
|
|
6
|
21
|
502.56
|
21.8
|
612.53
|
10.5
|
21.88
|
|
7
|
22
|
690.11
|
31.3
|
746.28
|
11.4
|
8.14
|
|
8
|
22
|
690.85
|
37.2
|
762.59
|
12.8
|
10.38
|
|
9
|
25
|
618.65
|
31.8
|
689.14
|
11.6
|
11.39
|
|
10
|
29
|
680.56
|
73.5
|
749.51
|
21.8
|
10.13
|
|
11
|
29
|
716.84
|
201.2
|
827.64
|
58.5
|
15.46
|
|
12
|
30
|
631.51
|
76.8
|
784.52
|
26.7
|
24.23
|
|
13
|
32
|
2560.22
|
282.6
|
2735.12
|
121.5
|
6.83
|
|
14
|
32
|
1043.16
|
392.3
|
1373.37
|
142.3
|
31.65
|
|
15
|
32
|
1161.65
|
315.2
|
1283.42
|
159.9
|
10.48
|
|
16
|
35
|
702.69
|
191.7
|
845.1
|
62.3
|
20.27
|
|
17
|
40
|
864.39
|
190.8
|
979.38
|
55.2
|
13.3
|
|
18
|
44
|
1026.18
|
1745.8
|
1592.17
|
458.9
|
55.16
|
|
19
|
50
|
759.37
|
1429.1
|
827.49
|
324.8
|
8.97
|
|
20
|
71
|
517.48
|
3251.2
|
742.54
|
1526.1
|
43.49
|
|
21
|
75
|
1023.93
|
3600.1
|
1217.26
|
1216.1
|
18.88
|
|
22
|
75
|
1053.1
|
3600.7
|
1239.37
|
1843.5
|
17.69
|
|
23
|
75
|
1119.74
|
3600.2
|
1296.41
|
1495.6
|
15.78
|
|
24
|
75
|
1211.34
|
3600.2
|
1427.49
|
2134.5
|
17.84
|
|
25
|
100
|
1346.13
|
3600.5
|
1489.81
|
2948.9
|
10.67
|
|
26
|
100
|
1337.84
|
3600.5
|
1502.24
|
2198.7
|
12.29
|
|
27
|
100
|
1431.29
|
3600.4
|
1678.52
|
1982.4
|
17.27
|
|
28
|
120
|
2494.36
|
3600.5
|
2845.12
|
1584.3
|
14.06
|
|
29
|
134
|
2279.63
|
3600.5
|
2589.41
|
1264.9
|
13.59
|
|
30
|
150
|
1871.62
|
3600.2
|
2413.27
|
1863.4
|
28.94
|
|
31
|
199
|
2354.68
|
3600.9
|
2938.71
|
1865.2
|
24.8
|
|
32
|
199
|
2353.78
|
3600.4
|
2947.99
|
1736.3
|
25.24
|
|
33
|
199
|
2354.8
|
3600.5
|
2981.26
|
3600.1
|
26.6
|
|
34
|
240
|
1421.21
|
3600.8
|
1784.51
|
3601.5
|
25.56
|
|
35
|
252
|
1798.55
|
3602
|
2251.47
|
3600.5
|
25.18
|
|
36
|
255
|
1694.2
|
3600.8
|
2145.21
|
3600.2
|
26.62
|
|
Moyenne
|
1170.99
|
1832.19
|
1395.2
|
1099.48
|
17.64
|
TABLE 5.6 - CRésultats
expérimentaux : comparaisons des deux heuristiques
les solutions optimales de certaines instances.
Chapitre 5. Application au problème de Tournées de
Véhicules avec Contraintes de Chargement
| 
