|
Choose your language |
|
|
Classical
instances for LRP
You will find here the 3 benchmarks of instances
used to test the algorithms dedicated to the capacitated location-routing
problem, the results obtained by the researchers on these instances and the
best known results.
Click here to see information on the files
containing the data of the instances.
Instances used by Prins
et al. for the problem with capacities on vehicles and depots. Benchmark 1
Instances used by Tuzun
and Burke for the problem with capacities on vehicles. Benchmark 2
Instances used by Barreto
for the problem with capacities on vehicles and depots. Benchmark 3
Known
results
The following tables give the best known
results for each instance (BKR), obtained either by the algorithm in their
published version, or during the parameterization phase.
We can also see a lower bound when one is
available (LB), and for each algorithm, the columns have the following meanings:
- Cost = cost of the solution
-
nb dep = number of depots used in the solution
-
nb veh = number of vehicles used in the solution
-
Cd = part of the cost corresponding to the setup costs of the depots
-
Cr = part of the cost
corresponding to the routing
-
CPU = running time to obtain
the solution (algorithm coded in Visual C++ and tested on a Dell PC Optiplex GX260, with a 2.4 GHz Pentium 4, 512MB of RAM, and
Windows XP).
-
Gap/BKR = gap in percentage
between the solution and the best known solution
-
Gap/LB = gap in percentage
between the solution and the best lower bound
Numbers in bold indicate the best known
results.
Asterisks indicate the optimal solutions
References :
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, in 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.
Benchmark 1 (capacities on vehicles and depots)
|
|
|
|
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 |
Results from a Branch and Cut – Internal
Report: 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.
Benchmark 2 (capacities on vehicles)
|
|
|
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 |
Benchmark 3 (capacities on vehicles and depots)
|
|
|
|
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 |
Results from a Branch and Cut – Internal
Report: 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.