|
Choose your language |
|
|
Instances classiques du LRP
Vous trouverez ici les 3 jeux d’instances utilisés
pour tester les algorithmes dédiés au problème de localisation-routage sous
contraintes de capacité, les résultats obtenus par différents chercheurs sur
ces instances ainsi que les meilleurs résultats connus.
Cliquez ici pour avoir des informations sur le
format des données utilisé pour les instances fournies.
Instances utilisées par Prins et al. pour problème avec capacité sur les véhicules et les dépôts. Jeux d’instances 1
Instances utilisées par Tuzun
et Burke pour problème sans capacité sur les dépôts. Jeux
d’instances 2
Instances utilisées par Barreto
pour problème avec capacité sur les véhicules et les dépôts. Jeux d’instances 3
Résultats connus
Les tableaux suivants donnent les meilleurs
résultats connus pour chaque instance (BKR), obtenus soit par les algorithmes
dans leur forme publiée soit lors des phases de test de paramétrage.
On y retrouve aussi une borne inférieure quand
celle-ci est connue (LB), et pour chaque algorithme, les colonnes ont les
significations suivantes :
-
Cost = coût
de la solution obtenue
-
nb dep = nombre de
dépôts utilisés dans la solution obtenue
-
nb veh = nombre de vehicules utilisés dans la solution obtenue
-
Cd = la partie du coût relative à l’ouverture des
dépôts
-
Cr = la partie du coût relative aux tournées
-
CPU = temps de calcul nécessaire pour obtenir la solution
(algorithmes codés sur Visual C++ et testés sur un Dell PC Optiplex
GX260, 2.4 GHz Pentium 4, 512 MB of RAM)
-
Gap/BKR = écart relatif de la solution obtenue
avec la meilleure solution connue
-
Gap/LB = écart relatif de la solution obtenue avec
la meilleure borne inférieure
Les nombres en gras indiquent les meilleures
solutions connues.
Les astérisques signalent les solutions optimales.
Références :
C. Prins, C. Prodhon, R. Wolfler-Calvo, Solving the Capacitated Location-Routing
Problem by a GRASP complemented by a Learning Process and a Path Relinking, 4OR - A Quarterly Journal of Operations
Research, 4(3), pp. 221-238, 2006.
C. Prins, C. Prodhon, R. Wolfler-Calvo, A Memetic
Algorithm with Population Management (MAjPM) for the
Capacitated Location-Routing Problem, dans J.
Gottlieb et G.R. Raidl (éd.),
Lecture Notes in Computer Science
3906, pp. 183-194, Springer, 2006.
C. Prins, C. Prodhon, P. Soriano, A.
Ruiz, R.Wolfler-Calvo, Solving the Capacitated LRP by
a Cooperative Lagrangean Relaxation-Granular Tabu
Search Heuristic, Transportation Science,
41(4), pp. 470-483, 2007.
Tuzun, D., L. I. Burke. A
two-phase tabu search approach to the location routing problem. 1999. European Journal of Operational
Research. 116 87–99.
Barreto,
S. S. Análise e Modelização
de Problemas de localização-distribuição.
Unpublished doctoral dissertation,
University of Aveiro, Portugal, 2004.
Jeux
d’instances 1 (capacités limitées sur les véhicules et les dépôts)
|
|
|
|
GRASP |
MAPM |
LRGTS |
|||||||||||||||||||||
|
|
BKS |
LB |
Cost |
nb dep |
nb veh |
Cd |
Cr |
CPU |
gap/BKS |
gap/LB |
Cost |
nb dep |
nb veh |
Cd |
Cr |
CPU |
gap/BKS |
gap/LB |
Cost |
nb dep |
nb veh |
Cd |
Cr |
CPU |
gap/BKS |
gap/LB |
|
20-5-1a |
*54793 |
*54793,00 |
55021 |
3 |
5 |
25549 |
29472 |
0,2 |
0,42 |
0,42 |
*54793 |
3 |
5 |
25549 |
29244 |
0,3 |
0,00 |
0,00 |
55131 |
3 |
5 |
25549 |
29582 |
0,4 |
0,62 |
0,62 |
|
20-5-1b |
*39104 |
*39104,00 |
*39104 |
2 |
3 |
15497 |
23607 |
0,2 |
0,00 |
0,00 |
*39104 |
2 |
3 |
15497 |
23607 |
0,3 |
0,00 |
0,00 |
*39104 |
2 |
3 |
15497 |
23607 |
0,2 |
0,00 |
0,00 |
|
20-5-2a |
*48908 |
*48908,00 |
*48908 |
3 |
5 |
24196 |
24712 |
0,1 |
0,00 |
0,00 |
*48908 |
3 |
5 |
24196 |
24712 |
0,4 |
0,00 |
0,00 |
*48908 |
3 |
5 |
24196 |
24712 |
0,5 |
0,00 |
0,00 |
|
20-5-2b |
*37542 |
*37542,00 |
*37542 |
2 |
3 |
13911 |
23631 |
0,2 |
0,00 |
0,00 |
*37542 |
2 |
3 |
13911 |
23631 |
0,3 |
0,00 |
0,00 |
*37542 |
2 |
3 |
13911 |
23631 |
0,1 |
0,00 |
0,00 |
|
50-5-1 |
90111 |
87109.64 |
90632 |
3 |
12 |
25442 |
65190 |
1,8 |
0,58 |
4,04 |
90160 |
3 |
12 |
25442 |
64718 |
2,6 |
0,05 |
3,50 |
90160 |
3 |
12 |
25442 |
64718 |
0,3 |
0,05 |
3,50 |
|
50-5-1b |
63242 |
61595.22 |
64761 |
2 |
6 |
15385 |
49376 |
1,8 |
2,40 |
5,14 |
63242 |
2 |
6 |
15385 |
47857 |
3,2 |
0,00 |
2,67 |
63256 |
2 |
6 |
15385 |
47871 |
1,0 |
0,02 |
2,70 |
|
50-5-2 |
88298 |
86055.01 |
88786 |
3 |
12 |
29319 |
59467 |
2,4 |
0,55 |
3,17 |
88298 |
3 |
12 |
29319 |
58979 |
3,4 |
0,00 |
2,61 |
88715 |
3 |
12 |
29319 |
59396 |
1,8 |
0,47 |
3,09 |
|
50-5-2b |
67340 |
65787.75 |
68042 |
3 |
6 |
29319 |
38723 |
2,5 |
1,04 |
3,43 |
67893 |
3 |
6 |
29319 |
38574 |
2,9 |
0,82 |
3,20 |
67698 |
3 |
6 |
29319 |
38379 |
1,8 |
0,53 |
2,90 |
|
50-5-2bis |
84055 |
83439.00 |
84055 |
3 |
12 |
19785 |
64270 |
1,7 |
0,00 |
0,74 |
84055 |
3 |
12 |
19785 |
64270 |
3,2 |
0,00 |
0,74 |
84181 |
3 |
12 |
19785 |
64396 |
2,0 |
0,15 |
0,89 |
|
50-5-2bbis |
*51822 |
*51822.00 |
52059 |
3 |
6 |
18763 |
33296 |
2,6 |
0,46 |
0,46 |
*51822 |
3 |
6 |
18763 |
33059 |
4,2 |
0,00 |
0,00 |
51992 |
3 |
6 |
18763 |
33229 |
0,9 |
0,33 |
0,33 |
|
50-5-3 |
86203 |
84075.08 |
87380 |
2 |
12 |
18961 |
68419 |
2,3 |
1,37 |
3,93 |
86203 |
2 |
12 |
18961 |
67242 |
3,1 |
0,00 |
2,53 |
86203 |
2 |
12 |
18961 |
67242 |
0,3 |
0,00 |
2,53 |
|
50-5-3b |
61830 |
61607.40 |
61890 |
2 |
6 |
18961 |
42929 |
2,0 |
0,10 |
0,46 |
61830 |
2 |
6 |
18961 |
42869 |
4,9 |
0,00 |
0,36 |
61830 |
2 |
6 |
18961 |
42869 |
0,5 |
0,00 |
0,36 |
|
100-5-1 |
275993 |
272082,37 |
279437 |
3 |
24 |
132890 |
146547 |
27,6 |
1,25 |
2,70 |
281944 |
3 |
24 |
144012 |
137932 |
26,3 |
2,16 |
3,62 |
277935 |
3 |
24 |
132890 |
145045 |
8,7 |
0,70 |
2,15 |
|
100-5-1b |
214392 |
207037,38 |
216159 |
3 |
12 |
132890 |
83269 |
23,2 |
0,82 |
4,41 |
216656 |
3 |
12 |
132890 |
83766 |
34,5 |
1,06 |
4,65 |
214885 |
3 |
11 |
132890 |
81995 |
8,3 |
0,23 |
3,79 |
|
100-5-2 |
194598 |
186916,59 |
199520 |
2 |
24 |
102246 |
97274 |
17,4 |
2,53 |
6,74 |
195568 |
2 |
24 |
102246 |
93322 |
35,8 |
0,50 |
4,63 |
196545 |
2 |
24 |
102246 |
94299 |
2,3 |
1,00 |
5,15 |
|
100-5-2b |
157173 |
153827,05 |
159550 |
2 |
11 |
102246 |
57304 |
22,4 |
1,51 |
3,72 |
157325 |
2 |
11 |
102246 |
55079 |
36,4 |
0,10 |
2,27 |
157792 |
2 |
11 |
102246 |
55546 |
3,3 |
0,39 |
2,58 |
|
100-5-3 |
200246 |
194202,03 |
203999 |
2 |
25 |
88287 |
115712 |
21,6 |
1,87 |
5,04 |
201749 |
2 |
24 |
88287 |
113462 |
28,7 |
0,75 |
3,89 |
201952 |
2 |
24 |
88287 |
113665 |
2,4 |
0,85 |
3,99 |
|
100-5-3b |
152586 |
149985,58 |
154596 |
2 |
11 |
88287 |
66309 |
20,3 |
1,32 |
3,07 |
153322 |
2 |
11 |
88287 |
65035 |
33,3 |
0,48 |
2,22 |
154709 |
2 |
12 |
88287 |
66422 |
2,9 |
1,39 |
3,15 |
|
100-10-1 |
290429 |
258242,64 |
323171 |
4 |
26 |
204071 |
119100 |
37,4 |
11,27 |
25,14 |
316575 |
4 |
25 |
202285 |
114290 |
24,7 |
9,00 |
22,59 |
291887 |
3 |
26 |
154942 |
136945 |
14,1 |
0,50 |
13,03 |
|
100-10-1b |
234641 |
218825,96 |
271477 |
4 |
12 |
196308 |
75169 |
29,5 |
15,70 |
24,06 |
270251 |
4 |
11 |
201010 |
69241 |
36,0 |
15,18 |
23,50 |
235532 |
3 |
12 |
154942 |
80590 |
14,0 |
0,38 |
7,63 |
|
100-10-2 |
244265 |
226904,99 |
254087 |
3 |
25 |
154400 |
99687 |
39,1 |
4,02 |
11,98 |
245123 |
3 |
24 |
145956 |
99167 |
24,6 |
0,35 |
8,03 |
246708 |
3 |
24 |
145956 |
100752 |
14,4 |
1,00 |
8,73 |
|
100-10-2b |
203988 |
194627,72 |
206555 |
3 |
11 |
149586 |
56969 |
29,8 |
1,26 |
6,13 |
205052 |
3 |
11 |
149586 |
55466 |
31,6 |
0,52 |
5,36 |
204435 |
3 |
11 |
145956 |
58479 |
10,1 |
0,22 |
5,04 |
|
100-10-3 |
253344 |
222353,23 |
270826 |
3 |
25 |
158791 |
112035 |
35,4 |
6,90 |
21,80 |
253669 |
3 |
24 |
139411 |
114258 |
29,0 |
0,13 |
14,08 |
258656 |
3 |
25 |
139411 |
119245 |
13,3 |
2,10 |
16,33 |
|
100-10-3b |
204597 |
189308,50 |
216173 |
3 |
11 |
144699 |
71474 |
39,8 |
5,66 |
14,19 |
204815 |
3 |
11 |
139411 |
65404 |
36,5 |
0,11 |
8,19 |
205883 |
3 |
11 |
139411 |
66472 |
10,8 |
0,63 |
8,76 |
|
200-10-1 |
479425 |
|
490820 |
3 |
48 |
266151 |
224669 |
517,5 |
2,38 |
|
483497 |
3 |
47 |
266151 |
217346 |
345,1 |
0,85 |
|
481676 |
3 |
47 |
253840 |
227836 |
62,0 |
0,47 |
|
|
200-10-1b |
378773 |
|
416753 |
3 |
22 |
285784 |
130969 |
379,1 |
10,03 |
|
380044 |
3 |
22 |
253840 |
126204 |
463,0 |
0,34 |
|
380613 |
3 |
22 |
253840 |
126773 |
60,3 |
0,49 |
|
|
200-10-2 |
450468 |
|
512679 |
3 |
49 |
307214 |
205465 |
554,3 |
13,81 |
|
451840 |
3 |
48 |
280370 |
171470 |
280,6 |
0,30 |
|
453353 |
3 |
48 |
280370 |
172983 |
60,3 |
0,64 |
|
|
200-10-2b |
374435 |
|
379980 |
3 |
23 |
280370 |
99610 |
367,4 |
1,48 |
|
375019 |
3 |
22 |
280370 |
94649 |
321,0 |
0,16 |
|
377351 |
3 |
23 |
280370 |
96981 |
76,9 |
0,78 |
|
|
200-10-3 |
472898 |
|
496694 |
3 |
46 |
243199 |
253495 |
424,8 |
5,03 |
|
478132 |
3 |
46 |
234660 |
243472 |
212,9 |
1,11 |
|
476684 |
3 |
47 |
272528 |
204156 |
77,2 |
0,80 |
|
|
200-10-3b |
364178 |
|
389016 |
3 |
22 |
261594 |
127422 |
290,2 |
6,82 |
|
364834 |
3 |
22 |
234660 |
130174 |
272,0 |
0,18 |
|
365250 |
3 |
22 |
234660 |
130590 |
73,3 |
0,29 |
|
|
MOY |
197323 |
134188 |
207322 |
2,8 |
17,2 |
|
|
96,5 |
3,4 |
6,3 |
200309 |
2,8 |
16,9 |
|
|
76,7 |
1,1 |
4,9 |
198552 |
2,7 |
17,1 |
|
|
17,5 |
0,5 |
4,1 |
Résultats obtenus par un Branch and Cut – Rapport interne: A branch-and-cut algorithm for the capacitated
location routing problem with depot and
vehicle capacities. LIPN, Internal report. Université Paris-Nord. Submitted for
publication.
Jeux
d’instances 2 (capacités limitées sur les véhicules)
|
|
|
Tuzun & Burke* |
GRASP |
MAPM |
LRGTS |
||||||||||||||||||||
|
|
BKR |
Cost |
CPU |
gap/BKS |
Cost |
nb dep |
nb veh |
Cd |
Cr |
CPU |
gap/BKS |
Cost |
nb dep |
nb veh |
Cd |
Cr |
CPU |
gap/BKS |
Cost |
nb dep |
nb veh |
Cd |
Cr |
CPU |
gap/BKS |
|
111112 |
1468,40 |
1556,64 |
6,01 |
6,01 |
1525,25 |
3 |
11 |
300 |
1225,25 |
32,4 |
3,87 |
1493,92 |
3 |
11 |
300 |
1193,92 |
31,5 |
1,74 |
1490,82 |
3 |
11 |
300 |
1190,82 |
3,3 |
1,53 |
|
111122 |
1449,20 |
1531,88 |
5,71 |
5,71 |
1526,90 |
3 |
11 |
300 |
1226,90 |
40,7 |
5,36 |
1471,36 |
2 |
11 |
200 |
1271,36 |
35,6 |
1,53 |
1471,76 |
3 |
11 |
300 |
1171,76 |
6,5 |
1,56 |
|
111212 |
1396,46 |
1443,43 |
3,36 |
3,36 |
1423,54 |
2 |
11 |
200 |
1223,54 |
27,6 |
1,94 |
1418,83 |
3 |
10 |
300 |
1118,83 |
36,2 |
1,60 |
1412,04 |
3 |
10 |
300 |
1112,04 |
4,2 |
1,12 |
|
111222 |
1432,29 |
1511,39 |
5,52 |
5,52 |
1482,29 |
2 |
11 |
200 |
1282,29 |
36,2 |
3,49 |
1492,46 |
2 |
11 |
200 |
1292,46 |
36,4 |
4,20 |
1443,06 |
2 |
11 |
200 |
1243,06 |
7,4 |
0,75 |
|
112112 |
1167,53 |
1231,11 |
5,45 |
5,45 |
1200,24 |
2 |
11 |
200 |
1000,24 |
27,7 |
2,80 |
1173,22 |
2 |
11 |
200 |
973,22 |
31,9 |
0,49 |
1187,63 |
2 |
11 |
200 |
987,63 |
6,9 |
1,72 |
|
112122 |
1102,70 |
1132,02 |
2,66 |
2,66 |
1123,64 |
3 |
11 |
300 |
823,64 |
34,3 |
1,90 |
1115,37 |
3 |
11 |
300 |
815,37 |
42,7 |
1,15 |
1115,95 |
3 |
11 |
300 |
815,95 |
6,8 |
1,20 |
|
112212 |
793,97 |
825,12 |
3,92 |
3,92 |
814,00 |
3 |
12 |
300 |
514,00 |
22,5 |
2,52 |
793,97 |
2 |
11 |
200 |
593,97 |
38,0 |
0,00 |
813,28 |
3 |
12 |
300 |
513,28 |
5,2 |
2,43 |
|
112222 |
728,30 |
740,54 |
1,68 |
1,68 |
747,84 |
3 |
11 |
300 |
447,84 |
37,3 |
2,68 |
730,51 |
2 |
11 |
200 |
530,51 |
49,3 |
0,30 |
742,96 |
3 |
11 |
300 |
442,96 |
5,9 |
2,01 |
|
113112 |
1238,49 |
1316,98 |
6,34 |
6,34 |
1273,10 |
3 |
11 |
300 |
973,10 |
21,5 |
2,79 |
1262,32 |
3 |
11 |
300 |
962,32 |
36,8 |
1,92 |
1267,93 |
3 |
11 |
300 |
967,93 |
4,3 |
2,38 |
|
113122 |
1246,34 |
1274,50 |
2,26 |
2,26 |
1272,94 |
2 |
11 |
200 |
1072,94 |
36,0 |
2,13 |
1251,32 |
3 |
11 |
300 |
951,32 |
47,7 |
0,40 |
1256,12 |
3 |
11 |
300 |
956,12 |
6,3 |
0,78 |
|
113212 |
902,38 |
920,75 |
2,04 |
2,04 |
912,19 |
3 |
12 |
300 |
612,19 |
20,3 |
1,09 |
903,82 |
3 |
12 |
300 |
603,82 |
35,1 |
0,16 |
913,06 |
3 |
12 |
300 |
613,06 |
4,0 |
1,18 |
|
113222 |
1021,31 |
1042,21 |
2,05 |
2,05 |
1022,51 |
3 |
11 |
300 |
722,51 |
38,4 |
0,12 |
1022,93 |
4 |
11 |
400 |
622,93 |
62,6 |
0,16 |
1025,51 |
3 |
11 |
300 |
725,51 |
4,9 |
0,41 |
|
131112 |
1866,75 |
2000,97 |
7,19 |
7,19 |
2006,70 |
3 |
16 |
300 |
1706,70 |
113,0 |
7,50 |
1959,39 |
3 |
16 |
300 |
1659,39 |
128,5 |
4,96 |
1946,01 |
3 |
16 |
300 |
1646,01 |
12,5 |
4,25 |
|
131122 |
1841,86 |
1892,84 |
2,77 |
2,77 |
1888,90 |
4 |
16 |
400 |
1488,90 |
161,4 |
2,55 |
1881,67 |
3 |
16 |
300 |
1581,67 |
144,2 |
2,16 |
1875,79 |
3 |
16 |
300 |
1575,79 |
18,5 |
1,84 |
|
131212 |
1981,37 |
2022,11 |
2,06 |
2,06 |
2033,93 |
3 |
17 |
300 |
1733,93 |
100,0 |
2,65 |
1984,25 |
3 |
16 |
300 |
1684,25 |
111,0 |
0,15 |
2010,53 |
3 |
16 |
300 |
1710,53 |
11,1 |
1,47 |
|
131222 |
1809,25 |
1854,97 |
2,53 |
2,53 |
1856,07 |
4 |
16 |
400 |
1456,07 |
132,4 |
2,59 |
1855,25 |
3 |
16 |
300 |
1555,25 |
144,1 |
2,54 |
1819,89 |
3 |
16 |
300 |
1519,89 |
15,8 |
0,59 |
|
132112 |
1448,27 |
1555,82 |
7,43 |
7,43 |
1508,33 |
3 |
16 |
300 |
1208,33 |
117,7 |
4,15 |
1448,27 |
2 |
16 |
200 |
1248,27 |
166,6 |
0,00 |
1448,65 |
2 |
16 |
200 |
1248,65 |
22,0 |
0,03 |
|
132122 |
1444,25 |
1478,80 |
2,39 |
2,39 |
1456,82 |
2 |
16 |
200 |
1256,82 |
166,1 |
0,87 |
1459,83 |
2 |
16 |
200 |
1259,83 |
154,8 |
1,08 |
1492,86 |
3 |
16 |
300 |
1192,86 |
28,0 |
3,37 |
|
132212 |
1206,73 |
1231,34 |
2,04 |
2,04 |
1240,40 |
2 |
16 |
200 |
1040,40 |
106,7 |
2,79 |
1207,41 |
3 |
17 |
300 |
907,41 |
161,4 |
0,06 |
1211,07 |
3 |
17 |
300 |
911,07 |
14,6 |
0,36 |
|
132222 |
931,94 |
948,28 |
1,75 |
1,75 |
940,80 |
3 |
17 |
300 |
640,80 |
142,4 |
0,95 |
934,79 |
3 |
17 |
300 |
634,79 |
196,1 |
0,31 |
936,93 |
3 |
17 |
300 |
636,93 |
13,7 |
0,54 |
|
133112 |
1699,92 |
1762,45 |
3,68 |
3,68 |
1736,90 |
3 |
17 |
300 |
1436,90 |
92,8 |
2,18 |
1720,30 |
3 |
16 |
300 |
1420,30 |
143,8 |
1,20 |
1729,31 |
3 |
16 |
300 |
1429,31 |
17,9 |
1,73 |
|
133122 |
1401,82 |
1488,34 |
6,17 |
6,17 |
1425,74 |
3 |
16 |
300 |
1125,74 |
128,4 |
1,71 |
1429,34 |
4 |
16 |
400 |
1029,34 |
155,7 |
1,96 |
1424,59 |
3 |
16 |
300 |
1124,59 |
18,5 |
1,62 |
|
133212 |
1199,51 |
1264,63 |
5,43 |
5,43 |
1223,70 |
3 |
17 |
300 |
923,70 |
88,5 |
2,02 |
1203,44 |
3 |
17 |
300 |
903,44 |
153,8 |
0,33 |
1216,32 |
3 |
16 |
300 |
916,32 |
14,5 |
1,40 |
|
133222 |
1152,86 |
1182,28 |
2,55 |
2,55 |
1231,33 |
4 |
17 |
400 |
831,33 |
134,9 |
6,81 |
1158,54 |
3 |
17 |
300 |
858,54 |
223,0 |
0,49 |
1162,16 |
3 |
17 |
300 |
862,16 |
14,3 |
0,81 |
|
121112 |
2281,78 |
2379,47 |
4,28 |
4,28 |
2384,01 |
3 |
21 |
300 |
2084,01 |
308,0 |
4,48 |
2293,99 |
3 |
21 |
300 |
1993,99 |
418,3 |
0,54 |
2296,52 |
3 |
22 |
300 |
1996,52 |
32,6 |
0,65 |
|
121122 |
2185,55 |
2211,74 |
1,20 |
1,20 |
2288,09 |
4 |
22 |
400 |
1888,09 |
410,0 |
4,69 |
2277,39 |
3 |
21 |
300 |
1977,39 |
458,4 |
4,20 |
2207,50 |
4 |
22 |
400 |
1807,50 |
39,6 |
1,00 |
|
121212 |
2234,78 |
2288,17 |
2,39 |
2,39 |
2273,19 |
3 |
21 |
300 |
1973,19 |
311,4 |
1,72 |
2274,57 |
3 |
21 |
300 |
1974,57 |
376,8 |
1,78 |
2260,87 |
4 |
21 |
400 |
1860,87 |
32,8 |
1,17 |
|
121222 |
2259,52 |
2355,81 |
4,26 |
4,26 |
2345,10 |
3 |
22 |
300 |
2045,10 |
418,9 |
3,79 |
2376,25 |
3 |
21 |
300 |
2076,25 |
436,3 |
5,17 |
2259,52 |
3 |
21 |
300 |
1959,52 |
40,2 |
0,00 |
|
122112 |
2101,90 |
2158,60 |
2,70 |
2,70 |
2137,08 |
3 |
22 |
300 |
1837,08 |
338,0 |
1,67 |
2106,26 |
3 |
21 |
300 |
1806,26 |
350,5 |
0,21 |
2120,76 |
3 |
21 |
300 |
1820,76 |
47,2 |
0,90 |
|
122122 |
1709,56 |
1787,02 |
4,53 |
4,53 |
1807,29 |
4 |
21 |
400 |
1407,29 |
370,0 |
5,72 |
1771,53 |
2 |
20 |
200 |
1571,53 |
377,0 |
3,62 |
1737,81 |
3 |
21 |
300 |
1437,81 |
59,3 |
1,65 |
|
122212 |
1467,54 |
1549,79 |
5,60 |
5,60 |
1496,75 |
2 |
21 |
200 |
1296,75 |
242,7 |
1,99 |
1467,54 |
2 |
21 |
200 |
1267,54 |
322,2 |
0,00 |
1488,55 |
2 |
21 |
200 |
1288,55 |
36,7 |
1,43 |
|
122222 |
1084,78 |
1112,96 |
2,60 |
2,60 |
1095,92 |
3 |
22 |
300 |
795,92 |
308,5 |
1,03 |
1088,00 |
3 |
22 |
300 |
788,00 |
505,0 |
0,30 |
1090,59 |
3 |
22 |
300 |
790,59 |
38,7 |
0,54 |
|
123112 |
1973,28 |
2056,11 |
4,20 |
4,20 |
2044,66 |
4 |
23 |
400 |
1644,66 |
282,8 |
3,62 |
1973,28 |
4 |
22 |
400 |
1573,28 |
412,8 |
0,00 |
1984,06 |
4 |
22 |
400 |
1584,06 |
41,6 |
0,55 |
|
123122 |
1957,23 |
2002,42 |
2,31 |
2,31 |
2090,95 |
4 |
22 |
400 |
1690,95 |
399,2 |
6,83 |
1979,05 |
5 |
21 |
500 |
1479,05 |
406,1 |
1,11 |
1986,49 |
4 |
22 |
400 |
1586,49 |
51,8 |
1,50 |
|
123212 |
1771,06 |
1877,30 |
6,00 |
6,00 |
1788,70 |
2 |
21 |
200 |
1588,70 |
199,0 |
1,00 |
1782,23 |
3 |
22 |
300 |
1482,23 |
352,8 |
0,63 |
1786,79 |
3 |
22 |
300 |
1486,79 |
34,0 |
0,89 |
|
123222 |
1393,62 |
1414,83 |
1,52 |
1,52 |
1408,63 |
5 |
22 |
500 |
908,63 |
296,3 |
1,08 |
1396,24 |
5 |
22 |
500 |
896,24 |
529,8 |
0,19 |
1401,16 |
5 |
22 |
500 |
901,16 |
43,2 |
0,54 |
|
|
1509,79 |
1566,77 |
3,7 |
3,7 |
1556,51 |
3,0 |
16,4 |
|
|
|
2,9 |
1532,19 |
2,9 |
16,2 |
|
|
|
1,3 |
1528,75 |
3,1 |
16,3 |
|
|
|
1,3 |
Jeux
d’instances 3 (capacités limitées sur les véhicules et les dépôts)
|
|
|
|
Barreto LB* |
LB |
Barreto Heuristic* |
GRASP |
MAPM |
LRGTS |
|||||||||||||||||||||||||
|
|
BKR |
Best LB |
Cost |
gap/LB |
Cost |
gap/LB |
Cost |
gap/BKS |
gap/LB |
Cost |
nb dep |
nb veh |
Cd |
Cr |
CPU |
gap/BKS |
gap/LB |
Cost |
nb dep |
nb veh |
Cd |
Cr |
CPU |
gap/BKS |
gap/LB |
Cost |
nb dep |
nb veh |
Cd |
Cr |
CPU |
gap/BKS |
gap/LB |
|
Christofides69-50x5 |
*565,6 |
*565.6 |
549,4 |
-0,3 |
551,1 |
-2,6 |
582,7 |
3,0 |
3,0 |
599,1 |
3 |
8 |
120 |
479,1 |
2,3 |
5,9 |
5,9 |
*565,6 |
2 |
6 |
80 |
485,6 |
3,8 |
0,0 |
0,0 |
586,4 |
2 |
6 |
80 |
506,4 |
2,4 |
3,7 |
3,7 |
|
Christofides69-75x10 |
861,6 |
798.7 |
744,7 |
-5,9 |
791,4 |
-0,9 |
886,3 |
2,9 |
11,0 |
861,6 |
3 |
9 |
120 |
741,6 |
9,8 |
0,0 |
7,9 |
866,1 |
3 |
9 |
120 |
746,1 |
9,4 |
0,5 |
8,4 |
863,5 |
3 |
10 |
120 |
743,5 |
10,1 |
0,2 |
8,1 |
|
Christofides69-100x10 |
842,9 |
818,1 |
788,6 |
-3,6 |
818,1 |
0,0 |
889,4 |
5,5 |
8,7 |
861,6 |
3 |
9 |
120 |
741,6 |
25,5 |
2,2 |
5,3 |
850,1 |
2 |
8 |
80 |
770,1 |
44,5 |
0,9 |
3,9 |
842,9 |
2 |
8 |
80 |
762,9 |
28,2 |
0,0 |
3,0 |
|
Daskin95-88x8 |
355,8 |
350.5 |
356,4 |
0,0 |
347,0 |
-1,0 |
384,9 |
8,2 |
9,8 |
356,9 |
2 |
8 |
84 |
273,3 |
17,3 |
0,3 |
1,8 |
355,8 |
2 |
7 |
84 |
272,2 |
34,2 |
0,0 |
1,5 |
368,7 |
2 |
6 |
84 |
285,1 |
17,5 |
3,6 |
5,2 |
|
Daskin95-150x10 |
44011,7 |
43406,0 |
43406,0 |
0,0 |
39470,5 |
-9,1 |
46642,7 |
6,0 |
7,5 |
44625,2 |
3 |
13 |
15000 |
29625,2 |
156,0 |
1,4 |
2,8 |
44011,7 |
3 |
11 |
15000 |
29011,7 |
255,0 |
0,0 |
1,4 |
44386,3 |
3 |
14 |
15000 |
29386,3 |
119,2 |
0,9 |
2,3 |
|
Gaskell67-21x5 |
*424,9 |
*424,9 |
*424,9 |
0,0 |
*424,9 |
0,0 |
435,9 |
2,6 |
2,6 |
429,6 |
2 |
5 |
100 |
329,6 |
0,2 |
1,1 |
1,1 |
*424,9 |
2 |
4 |
100 |
324,9 |
0,3 |
0,0 |
0,0 |
*424,9 |
2 |
4 |
100 |
324,9 |
0,2 |
0,0 |
0,0 |
|
Gaskell67-22x5 |
*585,1 |
*585,1 |
*585,1 |
0,0 |
*585,1 |
0,0 |
591,5 |
1,1 |
1,1 |
*585,1 |
1 |
3 |
50 |
535,1 |
0,2 |
0,0 |
0,0 |
611,8 |
2 |
3 |
100 |
511,8 |
0,3 |
4,6 |
4,6 |
587,4 |
1 |
3 |
50 |
537,4 |
0,2 |
0,4 |
0,4 |
|
Gaskell67-29x5 |
*512,1 |
*512,1 |
*512,1 |
0,0 |
*512,1 |
0,0 |
*512,1 |
0,0 |
0,0 |
515,1 |
2 |
4 |
100 |
415,1 |
0,4 |
0,6 |
0,6 |
*512,1 |
2 |
4 |
100 |
412,1 |
0,8 |
0,0 |
0,0 |
*512,1 |
2 |
4 |
100 |
412,1 |
0,4 |
0,0 |
0,0 |
|
Gaskell67-32x5 |
571,7 |
562,2 |
556,5 |
-1,0 |
*562,2 |
0,0 |
*571,7 |
0,0 |
1,7 |
571,9 |
2 |
4 |
100 |
471,9 |
0,6 |
0,0 |
1,7 |
571,9 |
2 |
4 |
100 |
471,9 |
0,8 |
0,0 |
1,7 |
584,6 |
2 |
4 |
100 |
484,6 |
0,6 |
2,3 |
4,0 |
|
Gaskell67-32x5 |
*504,3 |
*504,3 |
*504,3 |
0,0 |
*504,3 |
0,0 |
511,4 |
1,4 |
1,4 |
*504,3 |
1 |
3 |
50 |
454,3 |
0,5 |
0,0 |
0,0 |
534,7 |
2 |
3 |
100 |
434,7 |
1,0 |
6,0 |
6,0 |
504,8 |
1 |
3 |
50 |
454,8 |
0,5 |
0,1 |
0,1 |
|
Gaskell67-36x5 |
*460,4 |
*460,4 |
*460,4 |
0,0 |
*460,4 |
0,0 |
470,7 |
2,2 |
2,2 |
*460,4 |
1 |
4 |
50 |
410,4 |
0,8 |
0,0 |
0,0 |
485,4 |
2 |
4 |
100 |
385,4 |
1,4 |
5,4 |
5,4 |
476,5 |
1 |
4 |
50 |
426,5 |
0,7 |
3,5 |
3,5 |
|
Min92-27x5 |
*3062,0 |
*3062,0 |
*3062,0 |
0,0 |
*3062,0 |
0,0 |
*3062,0 |
0,0 |
0,0 |
*3062,0 |
2 |
4 |
544 |
2518,0 |
0,4 |
0,0 |
0,0 |
*3062,0 |
2 |
4 |
544 |
2518,0 |
1,0 |
0,0 |
0,0 |
3065,2 |
2 |
4 |
544 |
2521,2 |
0,3 |
0,1 |
0,1 |
|
Min92-134x8 |
5809,0 |
5423,0 |
|
|
5423,0 |
0,0 |
6238,0 |
7,4 |
15,0 |
5965,1 |
4 |
11 |
1072 |
4893,1 |
49,6 |
2,7 |
10,0 |
5950,1 |
4 |
10 |
1072 |
4878,1 |
110,5 |
2,4 |
9,7 |
5809,0 |
3 |
11 |
804 |
5005,0 |
48,3 |
0,0 |
7,1 |
|
|
|
|
|
-0,9 |
|
-1,0 |
4752,3 |
3,1 |
4,9 |
4569,1 |
2,2 |
6,5 |
|
|
20,3 |
1,1 |
2,9 |
4523,3 |
2,3 |
5,9 |
|
|
35,6 |
1,5 |
3,3 |
4539,4 |
2,0 |
6,2 |
|
|
17,6 |
1,1 |
2,9 |
Résultats obtenus par un Branch and Cut – Rapport interne: A branch-and-cut algorithm for the capacitated
location routing problem with depot and
vehicle capacities. LIPN, Internal report. Université Paris-Nord. Submitted for
publication.