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

3.4 Résultats expérimentaux

Cette section évalue les performances de notre algorithme. Nous utilisons les instances symétriques euclidiennes sans capacité proposées par Riera-Ledesma et SalazarGonzález (2005). Ces instances vont de m = 50 à 350 marchés et de n = 50 à 200 produits. Cinq instances sont générées pour chaque combinaison du nombre de marchés et du nombre de produits, ce qui amène à un ensemble de 140 instances. Les solutions optimales sont connues pour 89 instances, par l'approche par séparation et génération de coupes proposée par Laporte et al. (Laporte et al., 2003). En ce qui concerne les 51 instances restantes, la valeur de la meilleure solution connue est fournie par l'algorithme LS de Riera-Ledesma et Salazar-González (2005). Les expérimentations sont exécutées en C++ sur un PC Pentium IV 2 Ghz et 1 Go de mémoire vive sous Linux/Debian.

Tous les paramètres présentés dans ce chapitre (par exemple, le nombre de niveaux de phéromone) ont été sélectionnés par des expériences préliminaires.

Nous comparons plusieurs variantes de notre algorithme avec l'algorithme de recherche locale (Local Search (LS)) proposé par Riera-Ledesma et Salazar-González (2005) lorsque les solutions optimales ne sont pas connues et avec l'approche par séparation et

génération de coupes proposée par Laporte et al. (2003) lorsque leur algorithme fournit les solutions optimales. Les résultats sont présentés dans les tableaux 3.1 et 3.2, respectivement pour les instances pour lesquelles la solution optimale est connue et celles où la solution optimale n'est pas connue. Les algorithmes sont :

- LS : algorithme Local Search proposé par Riera-Ledesma et Salazar-González (2005).

- IN (Improved Neighborhood) : une approche par construction stochastique simple, améliorée par nos opérateurs de recherche locale. La construction consiste à choisir aléatoirement un marché pour lequel au moins un nouveau produit peut être acheté, puis l'insérer dans le tour courant avec une approche de plus faible insertion, jusqu'à ce que tous les produits soient achetés, et ainsi obtenir une solution réalisable. Des marchés choisis aléatoirement sont ensuite ajoutés à la solution. Le nombre de marchés à ajouter est un nombre aléatoire compris entre 0 et 4. La procédure se termine avec des séquences d'insertion, suppression, dropstar et 2-opt, jusqu'à ce qu'aucune amélioration ne puisse être obtenue. Une nouvelle solution est alors générée. L'algorithme s'arrête lorsqu'il a atteint une limite de temps fixée à 300 secondes.

- DMD-ATA-LS : notre algorithme sans la procédure Dropstar, avec une limite de temps fixée à 300 secondes.

- DMD-ATA-300 : notre algorithme, avec une limite de temps fixée à 300 secondes. - DMD-ATA : les résultats moyens de notre algorithme pour cinq essais, avec une limite de temps fixée à 3600 secondes.

Les en-têtes de colonnes et des lignes sont les suivants :

- m : nombre de marchés dans les instances,

- n : nombre de produits dans les instances,

- %gap : écart exprimé en pourcentage entre la solution optimale (Table 3.1) ou la meilleure solution connue (Tableau 3.2) et la solution renvoyée par l'algorithme DMD-ATA,

- CPU : Temps en secondes pour finir l'algorithme (LS) ou pour trouver la meilleure solution,

- #best : nombre d'instances sur 89 pour lesquelles la solution optimale connue a été trouvée (Tableau 3.1),

- #improved : nombre d'instances sur 51 pour lesquelles la meilleure solution connue a été atteinte ou améliorée (Tableau 3.2).

Dans le tableau 3.2, le temps CPU pour l'algorithme LS n'est pas disponible.

Les tableaux 3.3 et 3.4 présentent les instances pour lesquelles la meilleure solution connue (fournie par Riera-Ledesma et Salazar-González (2005)) a été améliorée par l'algorithme DMD-ATA (avec 5 essais). La première colonne des tableaux est le nom de l'instance.

La première conclusion qui peut être tirée à la lecture de ces tableaux est que l'algorithme DMD-ATA est compétitif lorsqu'on le compare avec les meilleures méthodes connues, notamment la méthode LS de Riera-Ledesma et Salazar-González (2005). Sur de petites instances, l'algorithme DMD-ATA est parfois moins performant que la méthode LS. Sur les instances de tailles plus importantes, notre algorithme se montre plus efficace en terme de qualité de la solution que la méthode LS et améliore 48 instances

m n

Methodes #best

50 100 150 200 250 50 100 150 200

%Gap 0.07 0.14 0.03 0.32 0.06 0.07 0.24 0.10 0.08 82/89

LS CPU 3 10 14 19 25 5 13 20 21

%Gap 0.00 0.08 5.4 2.13 2.1 0.15 0.3 3.51 4.13 62/89

IN CPU 5 30 93 71 76 12 44 73 90

DMD-ATA-LS %Gap 0.00 0.00 0.21 0.36 0.51 0.05 0.03 0.34 0.35 75/89

CPU 4 22 60 97 123 36 73 60 51

DMD-ATA-300%Gap 0.00 0.01 0.13 0.03 0.39 0.05 0.15 0.00 0.12 79/89

CPU 5 6 75 66 97 20 53 31 81

DMD-ATA %Gap 0.00 0.00 0.08 0.02 0.01 0.00 0.05 0.00 0.03 86.50/89

CPU 2 20 172 232 154 37 154 96 165

TABLE 3.1 - Résultats expérimentaux, instances fermées

m n

Methodes 50 100 150 200 #improved

200 250 300 350

%Gap 2.05 6.00 6.66 10.99 0.78 5.43 8.77 8.04 14/51

IN CPU 9 100 88 111 104 85 98 59

DMD-ATA-LS %Gap 0.88 1.61 1.30 1.22 -0.29 1.00 1.49 1.37 32/51

CPU 53 88 165 125 80 124 127 105

DMD-ATA-300%Gap 0.56 1.30 2.08 1.25 -1.16 0.23 1.77 2.46 34/51

CPU 105 83 134 160 61 106 172 105

DMD-ATA %Gap -0.30 -0.33 -0.38 -0.75 -1.27 -0.49 -0.31 -0.09 48/51

CPU 973 470 834 651 133 394 515 909

TABLE 3.2 - Résultats expérimentaux, instances ouvertes

sur 51 pour lesquelles les solutions optimales ne sont toujours pas connues. Cependant, on peut noter que notre algorithme se montre plus coûteux en temps de calcul que LS. En effet celui-ci est basé sur une descente stratégique et converge donc rapidement vers un optimum local.

La comparaison entre la méthode DMD-ATA-300 et la méthode DMD-ATA est intéressante pour un point en particulier. Sur les instances de grandes tailles, la méthode DMD-ATA s'avère beaucoup plus efficace en un heure qu'en 300 secondes. La raison pour cela semble être qu'une partie importante du temps de calcul est consommée par les opérateurs de recherche locale et donc que la limite de 300 secondes ne semble pas être un temps assez conséquent pour tirer entièrement avantage du composant d'optimisation par Colonies de Fourmis.

Les résultats présentés dans le tableau 3.1 et les tableaux 3.3 et 3.4 sont les moyennes des résultats sur cinq essais, afin de montrer l'efficacité et la robustesse de l'algorithme. Les résultats sont très proches d'un essai à l'autre.

D'autres conclusions peuvent être déduites à partir des comparaisons entre l'algorithme DMD-ATA et l'algorithme Improved Neighborhood. Les résultats montrent que

Instance	DMD-ATA	LS	CPU	%gap
EEuclideo.200.150.4	2419	2426	1216,92	-0,29
EEuclideo.200.200.4	2344	2353	527,03	-0,38
EEuclideo.250.100.1	1301	1309	33,84	-0,61
EEuclideo.250.100.4	1673	1677	10,23	-0,24
EEuclideo.250.100.5	1641	1648	550,24	-0,42
EEuclideo.250.150.4	1836	1840	45,24	-0,22
EEuclideo.250.150.5	1531	1539	21,1	-0,52
EEuclideo.250.200.2	2785	2787	1137,65	-0,07
EEuclideo.250.200.3	1924	1934	281,88	-0,52
EEuclideo.250.200.4	2116	2128	83,83	-0,56
EEuclideo.250.200.5	1797	1807	930,03	-0,55
EEuclideo.300.50.1	1477	1483	160,00	-0,40
EEuclideo.300.50.2	813	816	116,01	-0,37
EEuclideo.300.50.3	1117	1123	20,00	-0,53
EEuclideo.300.50.4	1176	1183	2,11	-0,59
EEuclideo.300.50.5	1257	1262	276,00	-0,40
EEuclideo.300.100.1	1035	1040	55,54	-0,48
EEuclideo.300.100.2	1179	1184	617,22	-0,42
EEuclideo.300.100.3	1498	1507	103,42	-0,60
EEuclideo.300.100.4	1749	1759	312,16	-0,57
EEuclideo.300.100.5	1774	1781	2,74	-0,39
EEuclideo.300.150.1	1457	1459	756,71	-0,14
EEuclideo.300.150.2	1656	1667	483,32	-0,66
EEuclideo.300.150.3	2485	2492	663,24	-0,28

TABLE 3.3 - Résultats expérimentaux, instances ouvertes améliorées (1)

les opérateurs de recherche locale que nous proposons sont assez performants tant que les instances sont de tailles modérées. Néanmoins, l'intérêt de coupler de l'optimisation par Colonie de Fourmis avec de la recherche locale est évident pour les instances de plus grandes tailles. Cela démontre que le schéma d'optimisation par Colonies de Fourmis permet de diriger la recherche vers de bonnes régions de l'espace de solutions.

Enfin, la comparaison entre l'algorithme DMD-ATA-300 et l'algorithme DMD-ATALS montre que la procédure Dropstar apporte un avantage considérable à notre méthode. Elle permet de résoudre 4 instances à l'optimum qui n'étaient pas résolubles sans cette procédure. De plus, la procédure permet d'améliorer les meilleures solutions connues de 34 instances, alors que la méthode DMD-ATA-LS (sans la procédure Drops-tar) n'en améliorait que 32 dans le même temps imparti. Comme on peut le constater à la lecture des temps de calcul, la procédure Dropstar nécessite un temps de calcul raisonnable et fournit une exploration intensive d'une nouvelle définition de voisinage, qui n'était pas exploré par les autres procédures de recherche locale.

				3.5. Conclusion
Instance	DMD-ATA	LS	CPU	%gap
EEuclideo.300.150.4	1801	1809	95,93	-0,44
EEuclideo.300.150.5	1816	1825	309,25	-0,49
EEuclideo.300.200.2	1791	1798	1918,52	-0,39
EEuclideo.300.200.3	2442	2450	2852,05	-0,33
EEuclideo.300.200.4	1815	1829	2946,79	-0,77
EEuclideo.350.50.1	723	727	46,04	-0,55
EEuclideo.350.50.2	736	739	25,71	-0,41
EEuclideo.350.50.3	942	946	6,00	-0,42
EEuclideo.350.50.4	805	809	379,39	-0,49
EEuclideo.350.50.5	1125	1230	26,35	-8,54
EEuclideo.350.100.1	1317	1321	1698,48	-0,30
EEuclideo.350.100.2	962	965	155,48	-0,31
EEuclideo.350.100.3	796	804	839,65	-1,00
EEuclideo.350.100.4	1059	1065	13,94	-0,56
EEuclideo.350.100.5	1566	1576	464,86	-0,63
EEuclideo.350.150.1	1457	1459	1986,42	-0,14
EEuclideo.350.150.2	1315	1322	159,12	-0,53
EEuclideo.350.150.3	2553	2566	257,69	-0,51
EEuclideo.350.150.4	1239	1248	595,85	-0,72
EEuclideo.350.150.5	2288	2297	8,93	-0,39
EEuclideo.350.200.1	1503	1505	1033,39	-0,13
EEuclideo.350.200.2	1374	1377	3085,09	-0,22
EEuclideo.350.200.3	1873	1889	368,66	-0,85
EEuclideo.350.200.5	2336	2347	2385,65	-0,47

TABLE 3.4 - Résultats expérimentaux, instances ouvertes améliorées (2)