|
Choose your language |
|
|
PLRP
instances
You will find here the benchmarks of instances
used to test the algorithms dedicated to the periodic 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 and the data of the instances.
To mimic a working week, each instance is made of a 7-day cyclic horizon
H with 2 idle days (Saturday and Sunday).
The visit frequency of the customers is between once and three times a
week.
The allowed set of combinations of visit days is given in Table 1 and
forbids visits on two consecutive days.
The demand of customer j on each day l depends on the chosen service
combination r. It varies with the number of days separating two visits, but it
can be pre-calculated.
Table
1. Allowed
set of combinations of visit days
|
Frequency |
Combinations of visit days |
|
1 |
Monday Tuesday Wednesday Thursday Friday |
|
2 |
Monday - Thursday Monday - Friday Tuesday - Friday |
|
3 |
Monday - Wednesday - Friday |
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
-
CPU = running time to obtain
the solution (algorithm coded in Visual C++ and tested on a Dell Latitude D420,
with a 1.2 GHz Intel Centrino Duo, 1 GB of RAM, and Windows XP).
-
Gap/BKR = gap in percentage
between the solution and the best known solution
Numbers in bold indicate the best known
results.
Benchmarks (capacities on
vehicles and depots)
|
|
|
IM* |
MAPM** |
ELSxPath Relinking*** |
||||||
|
|
BKS1 |
Cost2 |
CPU |
gap/BKS |
Cost2 |
CPU |
gap/BKS |
Cost3 |
CPU |
gap/BKS |
|
20-5-1a |
78851 |
84448 |
0,61 |
7,10 |
85519 |
0,33 |
8,46 |
80546,3 |
1,1 |
2,15 |
|
20-5-1b |
75727 |
78201 |
0,67 |
3,27 |
76662 |
0,38 |
1,23 |
78564,7 |
1,3 |
3,75 |
|
20-5-2a |
80538 |
84102 |
0,61 |
4,43 |
84729 |
0,33 |
5,20 |
81827,6 |
1,1 |
1,60 |
|
20-5-2b |
62987 |
68777 |
0,63 |
9,19 |
64969 |
0,38 |
3,15 |
63492,1 |
1,1 |
0,80 |
|
50-5-1 |
157632 |
189219 |
5,45 |
20,04 |
172479 |
2,45 |
9,42 |
158675,6 |
5,5 |
0,66 |
|
50-5-1b |
142359 |
159656 |
7,3 |
12,15 |
159472 |
3,42 |
12,02 |
144072,4 |
9,1 |
1,20 |
|
50-5-2 |
152376 |
174001 |
5,99 |
14,19 |
159182 |
2,64 |
4,47 |
153138,6 |
6,6 |
0,50 |
|
50-5-2b |
119925 |
129385 |
7,09 |
7,89 |
122579 |
2,66 |
2,21 |
122152,8 |
8,3 |
1,86 |
|
50-5-2bis |
177649 |
213426 |
6,64 |
20,14 |
201040 |
3,11 |
13,17 |
180679,9 |
7,5 |
1,71 |
|
50-5-2bbis |
102824 |
150134 |
6,75 |
46,01 |
115585 |
3,72 |
12,41 |
103866,5 |
7,6 |
1,01 |
|
50-5-3 |
162640 |
201368 |
6,25 |
23,81 |
184369 |
3,14 |
13,36 |
163986,4 |
7,4 |
0,83 |
|
50-5-3b |
114931 |
127032 |
6,97 |
10,53 |
130163 |
2,94 |
13,25 |
116288,4 |
7,7 |
1,18 |
|
100-5-1 |
364324 |
391857 |
48,5 |
7,56 |
376857 |
30,05 |
3,44 |
371290,7 |
40 |
1,91 |
|
100-5-1b |
239235 |
252937 |
51,97 |
5,73 |
247511 |
23,63 |
3,46 |
239804,2 |
41,2 |
0,24 |
|
100-5-2 |
287093 |
287093 |
68,94 |
0,00 |
306784 |
51,95 |
6,86 |
292208,9 |
49,1 |
1,78 |
|
100-5-2b |
174963 |
226817 |
52,67 |
29,64 |
190201 |
40,36 |
8,71 |
177294,5 |
41,4 |
1,33 |
|
100-5-3 |
238031 |
323875 |
40,61 |
36,06 |
260567 |
25,72 |
9,47 |
240650 |
32,4 |
1,10 |
|
100-5-3b |
181334 |
209797 |
52,02 |
15,70 |
205891 |
31,7 |
13,54 |
182130,2 |
41,9 |
0,44 |
|
100-10-1 |
281896 |
318582 |
95,8 |
13,01 |
317390 |
28,33 |
12,59 |
284559,8 |
56 |
0,94 |
|
100-10-1b |
224751 |
237064 |
115,47 |
5,48 |
239659 |
34 |
6,63 |
227180,9 |
78,9 |
1,08 |
|
100-10-2 |
282437 |
288222 |
119,22 |
2,05 |
315764 |
61,09 |
11,80 |
286286,7 |
70,1 |
1,36 |
|
100-10-2b |
179047 |
196934 |
121,19 |
9,99 |
204853 |
39,56 |
14,41 |
181069,6 |
84,7 |
1,13 |
|
100-10-3 |
272463 |
338819 |
106,69 |
24,35 |
314942 |
42,11 |
15,59 |
277844,9 |
72,4 |
1,98 |
|
100-10-3b |
208890 |
219830 |
147,94 |
5,24 |
225198 |
37,8 |
7,81 |
211735,2 |
92,3 |
1,36 |
|
200-10-1 |
464596 |
564173 |
781,48 |
21,43 |
558309 |
497,13 |
20,17 |
480716,3 |
351,1 |
3,47 |
|
200-10-1b |
401901 |
432396 |
1221,27 |
7,59 |
445103 |
519,2 |
10,75 |
406137 |
547,3 |
1,05 |
|
200-10-2 |
410514 |
421012 |
711,8 |
2,56 |
464433 |
1461,47 |
13,13 |
414964,3 |
298,5 |
1,08 |
|
200-10-2b |
324121 |
324121 |
1283,7 |
0,00 |
354458 |
915,8 |
9,36 |
334163,3 |
644,3 |
3,10 |
|
200-10-3 |
574398 |
599822 |
834,67 |
4,43 |
618414 |
701,89 |
7,66 |
575764 |
426,7 |
0,24 |
|
200-10-3b |
356618 |
356618 |
871,02 |
0,00 |
382912 |
433,64 |
7,37 |
366447,6 |
460,1 |
2,76 |
|
MOY |
229835 |
254991 |
226 |
12,32 |
252866 |
166,7 |
9,37 |
233251,3 |
116,4 |
1,45 |
1 BKS is the minimal cost obtained during the 5 runs performed for the ELSxPath Relinking method
2 Cost is the solution cost obtained during the single run performed for the IM et MAPM algorithms
3 Cost is the average solution cost obtained during the 5 runs performed
for the ELSxPath Relinking method
* C. Prodhon, A
Metaheuristic for the Periodic Location-Routing Problem, GOR'07
(Operations Research 2007,
** C. Prodhon,
C. Prins. A Memetic Algorithm with Population Management (MA|PM) for the
Periodic Location-Routing Problem, In Hybrid Metaheuristics (Hybrid
Metaheuristics 2008 Proceedings, September 2008, Málaga, Spain), M.J. Blesa et
al. (éd.), Lecture Notes in Computer Science 5296, pp. 43-57, Springer, 2008.
ISBN 978-3-540-88438-5.
***
C. Prodhon. An ELSxPath Relinking Hybrid for the
Periodic Location-Routing Problem, In Hybrid
Metaheuristics (actes de Hybrid Metaheuristics 2009, October 2009, Udine, Italy),
M.J. Blesa et al.
(éd.), Lecture Notes in Computer Science 5818, pp. 15-29, Springer, 2009. ISBN
978-3-642-04917-0.