Choose your language

Instances PLRP

 

 

Vous trouverez ici le jeu d’instances utilisé pour tester les algorithmes dédiés au problème de localisation-routage périodique 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é et pour les instances fournies.

 

Pour représenter une semaine de travail, chaque instance est composée d’un horizon de 7 jours dont 2 jours non ouvrés (samedi et dimanche).

La fréquence de visite des clients est comprise entre 1 à 3 fois par semaine.

Les jours de visites permis sont donnés dans le tableau 1 et interdisent les visites sur 2 jours consécutifs.

En supposant un besoin quotidien des clients, la demande du client j pour chaque jour l dépendra de la combinaison de jour de service choisi. En effet, cette demande varie selon le nombre de jours séparant 2 visites. Cependant, il est possible de pré-calculer les demandes.

 

Tableau 1. Combinaisons de jours permises pour les visites des clients

Fréquence

Combinations de jours de visite

1

Lundi

Mardi

Mercredi

Jeudi

Vendredi

2

Lundi - Jeudi

Lundi - Vendredi

Mardi - Vendredi

3

Lundi – Mercredi - Vendredi

 

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

-          CPU = temps de calcul nécessaire pour obtenir la solution (algorithmes codés sur Visual C++ et testés sur un Dell Latitude D420, 1.2 GHz Intel Centrino Duo, 1 GB de RAM, et Windows XP)

-          Gap/BKR = écart relatif de la solution obtenue avec la meilleure solution connue

 

Les nombres en gras indiquent les meilleures solutions connues.

 

 

Jeu d’instances (capacités limitées sur les véhicules et les dépôts)

 

 

 

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 est la solution minimale obtenue lors des 5 exécutions de la méthode ELSxPath Relinking

2 Cost est la solution obtenue lors d’une seule exécution des algorithmes IM et MAPM

3 Cost est la solution moyenne obtenue lors des 5 exécutions de la méthode ELSxPath Relinking    

 

* C. Prodhon, A Metaheuristic for the Periodic Location-Routing Problem, GOR'07 (Operations Research 2007, Saarbrücken, Allemagne, 5-7/09/2007. Springer, 2008, 6p

** C. Prodhon, C. Prins. A Memetic Algorithm with Population Management (MA|PM) for the Periodic Location-Routing Problem, dans Hybrid Metaheuristics (actes de Hybrid Metaheuristics 2008, Septembre 2008, Málaga, Espagne), 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, dans Hybrid Metaheuristics (actes de Hybrid Metaheuristics 2009, Octobre 2009, Udine, Italie), M.J. Blesa et al. (éd.), Lecture Notes in Computer Science 5818, pp. 15-29, Springer, 2009. ISBN 978-3-642-04917-0.

Page last updated 06 January 2009.