WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

Techniques hybrides de recherche exacte et approchée: application à  des problèmes de transport

( Télécharger le fichier original )
par Boris BONTOUX
Université d'Avignon et des pays de Vaucluse - Doctorat spécialité informatique 2008
  

précédent sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

5.10 Conclusions et perspectives

Dans ce chapitre, nous avons proposé une résolution heuristique du problème de Tournées de Véhicules avec Contraintes de Chargement. De par la complexité des contraintes de chargement, ce problème n'est pas résolu par une approche exacte. Nous avons montré un aperçu des possibilités qu'il existait pour tronquer la méthode de Branch & Price, qui est une méthode a priori exacte. Les approches heuristiques que nous proposons permettent d'accélérer la résolution. Il est cependant clair que la qualité des heuristiques de chargement est déterminante dans la qualité des solutions. Malgré une utilisation de plusieurs heuristiques de chargement, les résultats que nous proposons ne permettent pas de dépasser les meilleurs résultats connus. Cependant, que ce soit en terme de qualité de solution ou en temps d'éxécution, nos résultats restent dans une moyenne des méthodes publiées à ce jour.

Les perspectives de recherche sur ce chapitre sont nombreuses. Les résultats que nous présentons pourraient être améliorés par l'utilisation d'heuristiques de chargement plus efficaces. Enfin, les résultats de la méthode de génération de routes réalisables ne sont pas à la hauteur de nos espérances. Cependant, on peut noter que cette méthode peut être une base de futurs travaux de recherche, dans le but de proposer une

Chapitre 5. Application au problème de Tournées de Véhicules avec Contraintes de Chargement

I

n

Tabu Search

z CPU

z

ACO

CPU

Gap

z

HBP

CPU

Gap

1

15

295.01

9.2

291.83

7.2

-1.08

294.21

11.6

-0.27

2

15

343.18

3.5

343.22

0.6

0.01

343.2

4.4

0.01

3

20

380.19

18.9

378.18

3.1

-0.51

382.56

15.2

0.62

4

20

440.91

17

439.07

3

-0.41

440.51

18.7

-0.09

5

21

382.3

27.6

381.63

12.8

-0.17

382.68

27.5

0.1

6

21

501.4

19.5

499.77

4.3

-0.32

502.56

21.8

0.23

7

22

691.23

53

678.22

11.7

-1.79

690.11

31.3

-0.16

8

22

691.89

83.7

684.37

16.1

-1.02

690.85

37.2

-0.15

9

25

620.77

40

614.88

4.9

-0.93

618.65

31.8

-0.34

10

29

679.68

179.6

668.48

50.1

-1.64

680.56

73.5

0.13

11

29

719.76

199.4

690.22

57.8

-3.51

716.84

201.2

-0.41

12

30

627.59

99.5

615.9

7.4

-1.77

631.51

76.8

0.62

13

32

2550.89

312.8

2480.04

61.8

-2.6

2560.22

282.6

0.37

14

32

1048.72

439.5

1007.92

163.1

-3.69

1043.16

392.3

-0.53

15

32

1160.25

313.4

1145.96

138.8

-1.17

1161.65

315.2

0.12

16

35

703.6

157.2

701.09

8.3

-0.35

702.69

191.7

-0.13

17

40

865.72

226.2

864.92

7.2

-0.09

864.39

190.8

-0.15

18

44

1037.65

1167.8

1003.84

292.6

-3.03

1026.18

1745.8

-1.11

19

50

746.91

1521.5

728.89

122.1

-2.15

759.37

1429.1

1.67

20

71

513.84

3370.3

484.23

1073.8

-4.95

517.48

3251.2

0.71

21

75

1025.79

3561.2

987.54

1037.3

-3.4

1023.93

3600.1

-0.18

22

75

1052.39

3461.8

1018.76

738.9

-2.89

1053.1

3600

0.07

23

75

1121.18

3600

1051.16

1206.5

-5.71

1119.74

3600.2

-0.13

24

75

1208.52

3324.6

1134.9

323.4

-5.62

1211.34

3600.2

0.23

25

100

1350.56

3600.1

1309.98

2454.9

-2.74

1346.13

3600.5

-0.33

26

100

1341.3

3600.3

1306.24

3558.1

-2.52

1337.84

3600.5

-0.26

27

100

1439.37

3600

1341.25

1570.3

-6.3

1431.29

3600.4

-0.56

28

120

2502.48

3600.1

2417.89

8714.5

-2.16

2494.36

3600.5

-0.32

29

134

2296.03

3600.2

2131.54

8837.5

-6.02

2279.63

3600.5

-0.71

30

150

1873.27

3600.2

1734.46

8720.3

-6.9

1871.62

3600.2

-0.09

31

199

2366.54

3600.5

2219.34

8747.4

-6.27

2354.68

3600.9

-0.5

32

199

2354.6

3600.6

2191.97

8745.8

-6.21

2353.78

3600.4

-0.03

33

199

2360.74

3600.6

2245.46

8742.7

-4.45

2354.8

3600.5

-0.25

34

240

1408.64

3601

1160.98

8771.6

-17.51

1421.21

3600.8

0.89

35

252

1786.93

3600.2

1465.85

8942.2

-16

1798.55

3602

0.65

36

255

1693.1

3600.9

1603.86

9011.7

-5.46

1694.2

3600.8

0.06

moyenne

1171.75

1817

1111.77

2560.27

-3.65

1170.99

1832.17

-0.01

TABLE 5.5 - Résultats expérimentaux : qualité des solutions sur l'ensemble des instances

résolution exacte du problème de Tournées de Véhicules avec Contraintes de Charge-
ment. Nous avons montré que dans le cas d'une résolution exacte du sous-problème,
cette méthode peut proposer une résolution exacte. Cela pourrait permettre de trouver

I

n

HBP

z CPU

z

HCG

CPU

Gap

1

15

294.21

11.6

296.56

5.6

0.8

2

15

343.2

4.4

369.2

3.1

7.58

3

20

382.56

15.2

391.26

10.2

2.27

4

20

440.51

18.7

469.2

9.7

6.51

5

21

382.68

27.5

402.18

12.1

5.1

6

21

502.56

21.8

612.53

10.5

21.88

7

22

690.11

31.3

746.28

11.4

8.14

8

22

690.85

37.2

762.59

12.8

10.38

9

25

618.65

31.8

689.14

11.6

11.39

10

29

680.56

73.5

749.51

21.8

10.13

11

29

716.84

201.2

827.64

58.5

15.46

12

30

631.51

76.8

784.52

26.7

24.23

13

32

2560.22

282.6

2735.12

121.5

6.83

14

32

1043.16

392.3

1373.37

142.3

31.65

15

32

1161.65

315.2

1283.42

159.9

10.48

16

35

702.69

191.7

845.1

62.3

20.27

17

40

864.39

190.8

979.38

55.2

13.3

18

44

1026.18

1745.8

1592.17

458.9

55.16

19

50

759.37

1429.1

827.49

324.8

8.97

20

71

517.48

3251.2

742.54

1526.1

43.49

21

75

1023.93

3600.1

1217.26

1216.1

18.88

22

75

1053.1

3600.7

1239.37

1843.5

17.69

23

75

1119.74

3600.2

1296.41

1495.6

15.78

24

75

1211.34

3600.2

1427.49

2134.5

17.84

25

100

1346.13

3600.5

1489.81

2948.9

10.67

26

100

1337.84

3600.5

1502.24

2198.7

12.29

27

100

1431.29

3600.4

1678.52

1982.4

17.27

28

120

2494.36

3600.5

2845.12

1584.3

14.06

29

134

2279.63

3600.5

2589.41

1264.9

13.59

30

150

1871.62

3600.2

2413.27

1863.4

28.94

31

199

2354.68

3600.9

2938.71

1865.2

24.8

32

199

2353.78

3600.4

2947.99

1736.3

25.24

33

199

2354.8

3600.5

2981.26

3600.1

26.6

34

240

1421.21

3600.8

1784.51

3601.5

25.56

35

252

1798.55

3602

2251.47

3600.5

25.18

36

255

1694.2

3600.8

2145.21

3600.2

26.62

Moyenne

1170.99

1832.19

1395.2

1099.48

17.64

TABLE 5.6 - CRésultats expérimentaux : comparaisons des deux heuristiques

les solutions optimales de certaines instances.

Chapitre 5. Application au problème de Tournées de Véhicules avec Contraintes de Chargement

précédent sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy








"Qui vit sans folie n'est pas si sage qu'il croit."   La Rochefoucault