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

 

                                   File Format

 

 

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.

 


Page last updated 25 February 2010.