Previous Contents Next

Chapter 3   Expérimentation : comportement de GRASP sur le SCP

Afin de mesurer l'efficacité de GRASP pour résoudre des problèmes de type SCP, celui-ci a été testé sur une famille de problèmes de référence [Or library]. D'autres algorithmes ont aussi été testés sur ces problèmes afin de pouvoir comparer l'efficacité de GRASP par rapport à eux [Barr et al.95].

3.1   Algorithmes testés et critères d'évaluation

Trois types d'algorithmes ont été testés : des algorithmes gloutons, différentes variations de GRASP et un algorithme de Branch & Bound. Pour chacun d'eux la valeur du coût obtenue a été notée ainsi que le temps nécessaire à son obtention. De plus, pour l'algorithme de Branch & Bound, l'impact des tests de réduction (dimensions du problème réduit et temps utilisé) ainsi que le nombre d'itérations réalisées, de noeuds explorés et d'appels à l'algorithme du simplexe réalisés par l'algorithme ont aussi été notés. Enfin, le résultat de la relaxation linéaire des problèmes (et le temps nécessaire pour l'obtenir) a aussi été rapporté.
Trois variantes de l'algorithme glouton ont été utilisées. La première correspond à l'heuristique seule, alors que la deuxième inclus une relaxation linéaire (pour fixer des variables à 0) et la troisième une relaxation linéaire et des tests de réduction. Cette dernière version correspond donc à celle utilisée au début de l'algorithme de Branch & Bound.
Les deux premières versions de GRASP testées sont celles sans intensification de la recherche locale (GRASP 1), et avec l'intensification (GRASP 2) proposée par [Vancoppenolle98]. Une troisième version (GRASP 3) inclut l'amélioration de la recherche locale intensifiée. Les paramètres retenus pour ces trois versions sont les suivants : Une dernière version (GRASP5) a été réalisée suite aux premiers résultats enregistrés sur les autres versions de GRASP. Celle-ci favorise l'obtention de solutions initiales nombreuses et assez diverses mais n'essaye d'améliorer que peu de solutions en raison du coût en temps de ces recherches locales intensifiées. Ses paramètres sont les suivants :


Enfin, l'algorithme du Branch & Bound faisait au départ appel au solveur en continu LPAKO [Lpako] afin d'effectuer les relaxations linéaires dont il avait besoin. En effet, ne disposant pas de produit commercial, nous avons choisi un code du domaine public et, ce solveur avait montré de bonnes performances (rapidité et robustesse face aux problèmes difficiles). Malheureusement il ne libère pas entièrement la mémoire qu'il utilise à chaque appel, ce qui pose des problèmes lors d'un grand nombre d'appels. Il a donc été remplacé par un autre solveur du domaine public, LPSOLVE [Lpsolve], qui s'il se révèle moins sophistiqué (et donc moins performant) se révèle stable au niveau de sa gestion de la mémoire. LPAKO a cependant été conservé pour les algorithmes gloutons qui ne nécessitent qu'une seule relaxation linéaire.

3.2   Matériel utilisé

L'ensemble des tests a été réalisé sur un Pentium III cadencé à 600 Mhz et disposant de 192 Mo de RAM et de 256 Ko de mémoire cache. Le système d'exploitation installé sur ce poste est Windows 98.

La plupart des algorithmes testés ont été implémentés dans le langage Ada 95 (Gnat v3.10) excepté les algorithmes LPAKO et LPSOLVE qui eux étaient écrits en langage C. Ce langage est celui qu'avait utilisé [Vancoppenolle98] en raison de la sécurité du code produit. Nous l'avons conservé pour les mêmes raisons.

3.3   Instances utilisées

Les instances utilisées ont été récupérées sur le site [Or library]. Celles-ci sont régulièrement utilisées pour réaliser des benchmarks. Le lecteur intéressé pourra trouver ces problèmes (et beaucoup d'autres) sur ce site ainsi que des références à des articles rapportant les résultats obtenues sur ces instances.


Nom Variables Contraintes Densité (%) Max-Uns
SCP41 1000 200 2.0 30
SCP41r 500 100 2.0 16
SCP61 1000 200 5.0 68
SCP61r 500 100 4.9 38
SCPA1 3000 300 2.0 81
SCPA1r1 500 50 1.8 17
SCPA1r2 1000 100 2.0 30
SCPE1 500 50 20.0 116
SCPE1r1 200 20 24.8 67
SCPE1r2 100 10 29.3 41
SCPNRE1 5000 500 10.0 560
SCPNRE1r1 200 20 10.7 31
SCPNRE1r2 100 10 11.2 14
SCPCYC6 192 240 2.1 4-4
SCPCLR10 210 511 12.3 10-126

Table 3.1: Caractéristiques numériques des instances sélectionnées


Les caractéristiques numériques prises en compte sont les dimensions de la matrice des contraintes (nombre de variables et de contraintes du problème), sa densité (c'est-à-dire le pourcentage de 1 dans la matrice) et aussi le nombre maximum de 1 par ligne. Nous avons sélectionné des instances parmi 7 familles (41, 61, a1, e1, nre1, cyc6, clr10) en nous assurant de couvrir une vaste gamme de caractéristiques numériques (voir Tableau 3.1).

Cependant, la taille de ces problèmes étant suffisamment importante pour mettre à mal, voire compromettre une méthode exacte, des versions réduites de ces instances ont aussi été produites. Dans ce cas un 'r' a été ajouté à la fin du nom de l'instance (voir même 'r1' et 'r2' dans le cas de différentes réductions). Ces versions ont été obtenues en préservant au maximum les caractéristiques numériques de ces problèmes (rapport du nombre de variable sur le nombre de contraintes, densité).

De plus, les problèmes dont les coûts n'étaient pas unitaires ont aussi été testés avec des coûts unitaires. Un 'U' a alors été ajouté à la fin du nom de l'instance. Enfin, deux instances ayant des structures particulières et connues pour être difficiles ont été retenues. Au total 25 instances ont ainsi été utilisées.

3.4   Résultats obtenus

Afin d'évaluer le potentiel de GRASP, les résultats obtenus avec ses différentes variations ont été comparés, puis ont été successivement comparés à ceux obtenus avec les autres algorithmes et aux meilleurs résultats trouvés dans la littérature. Dans la suite, seuls les exemples caractéristiques des différents cas de figure rencontrés sont discutés. Cependant la liste exhaustive des résultats obtenus sur chacun des problèmes traités est rapportée en annexe V.

Du fait de son caractère non déterministe, toutes les expérimentations mettant en oeuvre GRASP ont été répétées 10 fois afin de pouvoir considérer un comportement moyen.

3.4.1   Comparaison des différentes versions de GRASP

Les paramètres pris en compte pour comparer les différentes versions de GRASP sont les temps d'exécution et les valeurs obtenues.

Temps d'exécution

Des différences de temps significatives ont pu être observées sur la plupart des instances. Ces différences peuvent souvent être considérées comme négligeables sur les instances de petite taille. Par contre, sur les instances de plus grande taille, ce n'est plus le cas. Ainsi, si l'on prend les temps réalisés par GRASP 1 comme référence on obtient les rapports de temps suivants avec les autres versions : De plus, si les temps obtenus avec GRASP 1, 2 et 3 varient peu d'une expérimentation à l'autre, ce n'est pas le cas pour GRASP 5 en raison du nombre variable de recherche locale réalisé. L'instance SCP41U caractérise bien ce phénomène avec des temps de résolution allant de 182.5 à 314 secondes suivant les expérimentations.

Qualité des solutions obtenues

Dans un certain nombre d'instances (comme le SCPNRE1 par exemple), la qualité des solutions obtenues est approximativement identique. Par contre, des différences peuvent être relevées sur les autres problèmes. On observe ainsi quatre cas différents (Figures 3.1 à 3.4).




Figure 3.1: SCP41



Figure 3.2: SCPCLR10



Dans tous ces cas, GRASP 1 se montre systématiquement le moins bon alors que GRASP 2 est plus nuancé en obtenant dans certains cas des résultats de bonne qualité (voir Figure 3.1). Dans le cas général, GRASP 3 et GRASP 5 fournissent des solutions de meilleure qualité que GRASP 1 et GRASP 2 (voir Figure 3.2).




Figure 3.3: SCPA1



Figure 3.4: SCPNRE1U



Par contre il est difficile de prendre position entre GRASP 3 et GRASP 5. En effet, suivant les instances les meilleurs résultats sont obtenus soit avec l'un, soit avec l'autre (voir Figure 3.3 et 3.4).

Synthèse

Il n'existe pas une version de GRASP strictement dominante par rapport à une autre. Malgré tout, la version GRASP 5 présente un bon compromis entre la qualité de la solution obtenue et le temps de calcul. Pour une utilisation avec un temps de calcul très limité, GRASP 1 peut présenter une bonne alternative avec des résultats corrects et des temps d'exécution plus réduits. Les deux autres versions ont par contre moins d'intérêt. Ainsi, GRASP 2 présente des temps de réponse trop proches de GRASP 5 étant donné la différence de qualité des solutions obtenues et n'améliore que peu les solutions obtenues par GRASP 1 (notamment pour les problèmes à coûts unitaires). Quant à GRASP 3, il se montre beaucoup trop lent sans pour autant assurer une meilleure qualité que GRASP 5.

3.4.2   Comparaison de GRASP avec des algorithmes gloutons

Tout d'abord, aucun des trois algorithmes gloutons essayés n'est clairement plus performant que les autres en terme de qualité de solutions obtenues. Par contre, les temps d'exécution peuvent différer de manière assez importante, principalement entre le premier dont les temps de réponse ne dépassent pas 10 secondes et le troisième qui peut utiliser jusqu'à 3 minutes. Cette différence s'explique par le coût en temps des tests de réduction.
Par rapport à GRASP, les algorithmes gloutons sont beaucoup plus rapides (de l'ordre de quelques secondes contre quelques minutes pour GRASP). Au niveau de la qualité des solutions obtenues, on s'aperçoit que dans certains cas particuliers l'un des algorithmes glouton peut se révéler meilleur que GRASP (voir Figure 3.5 et 3.6).




Figure 3.5: SCPCYC6



Figure 3.6: SCP41 (2)



Ces cas apparaissent soit pour des problèmes dont la structure semble bien adaptée à l'un des algorithmes gloutons (SCPCYC6), soit quand la solution obtenue après relaxation linéaire du problème est entière. Les algorithmes gloutons 2 et 3 parviennent alors à trouver la solution optimale et sont donc au moins aussi performants que GRASP (cas du SCP41 et de cinq problèmes réduits). Toutefois, il s'agit d'une situation isolée car les résultats obtenus par les autres algorithmes gloutons sont largement moins bons que ceux fournis par GRASP. Cependant, ces deux cas ne se présentent que rarement (7 instances sur 25 dont 2 seulement qui correspondent à des instances non réduites).

Dans le cas général (voir Figure 3.7 et 3.8), les solutions gloutonnes sont moins bonnes que celles de GRASP (SCPCLR10) et peuvent même en être très éloignées (SCP61).




Figure 3.7: SCPCLR10 (2)



Figure 3.8: SCP61



3.4.3   Comparaison de GRASP avec un algorithme exact

Comme cela a déjà été mentionné, lorsque le problème relâché conduit à une solution entière, l'algorithme exact s'est montré plus rapide que GRASP. Hormis ce cas particulier de <<faux problème>>, l'algorithme exact s'est révélé beaucoup plus lent voir incapable de résoudre la plupart des instances non réduites en un temps raisonnable (c'est-à-dire pour nous inférieur à deux ou trois jours) alors que GRASP pouvait fournir des solutions à ces instances en quelques minutes. De plus, il s'avère que les meilleurs résultats trouvés par GRASP sont souvent assez proches voir même égaux à la solution optimale. Ainsi, sur le SCPA1Ur2 (par exemple), la meilleure solution trouvée par GRASP a une valeur de 25. C'est une solution optimale. Le temps de réponse de GRASP sur cette instance est de 60 secondes alors que celui du Branch & Bound est de plus de 172 000 secondes (environ 48 heures). Notons aussi que l'algorithme de Branch & Bound est mis à mal pour résoudre les problèmes à coûts unitaires.

3.4.4   Comparaison de GRASP avec les meilleurs résultats connus

Nos résultats peuvent être comparés aux valeurs des solutions optimales lorsque celles-ci sont connues (voir Tableau 3.2). Ces solutions optimales proviennent soit de la résolution de ces instances par l'algorithme de Branch & Bound, soit sont rapportées dans [Beasley 87]. Les résultats obtenus par GRASP se révèlent très proches des solutions optimales (pas plus d'1 % de différence).


  SCP41 SCP61 SCPA1 SCPE1
Solution Optimale 429 138 253 5
GRASP 433 138 255 5
Différence 0.9 % 0 % 0.8 % 0 %

Table 3.2: Comparaison de GRASP avec les solutions optimales connues


Lorsque les solution optimales ne sont pas connues, les résultats peuvent malgré tout être confrontés avec les meilleurs solutions connues rapportées dans [Grossman et al.97]. La comparaison (voir Tableau 3.3) présente GRASP comme étant aussi performant que les autres heuristiques sur pratiquement toutes les instances, se révélant même parfois meilleur. La seule instance pour laquelle GRASP trouve un moins bon résultat est le SCPCYC6. Notons malgré tout que ce problème est particulier étant donné que la meilleure solution trouvée par [Grossman et al.97] a été obtenue à l'aide d'un simple algorithme glouton (et a d'ailleurs aussi été trouvée par l'un de nos algorithmes gloutons).


  SCP41U SCP61U SCPA1U SCPE1 SCPNRE1U SCPCYC6 SCPCLR10
Littérature 41 21 40 5 17 60 28
GRASP 40 21 40 5 17 61 25

Table 3.3: Comparaison de GRASP avec les meilleurs résultats de la littérature


3.5   Conclusion de l'étude du comportement de GRASP sur le SCP

Au vu des expérimentations réalisées, GRASP se montre tout à fait capable de fournir des solutions de bonne qualité au contraire d'algorithmes moins sophistiqués comme les gloutons. De plus, il permet d'obtenir des solutions sur des problèmes de grande taille avec des temps de calculs réalistes alors que les algorithmes exacts montrent leurs limites. Ces résultats valident donc l'intérêt de GRASP.

Nous allons donc maintenant pouvoir nous intéresser à un problème de capacité ferroviaire et à sa résolution par un algorithme basé sur GRASP.


Previous Contents Next