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

4.4 Résultats expérimentaux

L'algorithme a été codé en C++ et exécuté sur un Pentium IV 2.00 Ghz. Les instances utilisées proviennent de la librairie GTSPLIB² qui propose un ensemble de 65 instances. Parmi ces instances, nous avons sélectionné 54 instances utilisées dans plusieurs articles (Fischetti et al., 1997; Renaud et Boctor, 1998a; Snyder et Daskin, 2006; Silberholz et Golden, 2007) afin de pouvoir nous comparer à d'autres algorithmes.

Fischetti et al. (1997) ont proposé un algorithme de séparation et génération de coupes pour résoudre le GTSP. Dans leur article, ils ont créé des instances pour le GTSP en appliquant un partitionnement déterministe à 65 instances de TSP issues de la libraire TSPLIB. Pour une instance donnée, le nombre de groupes est fixé à m = [n/5i. Ensuite, m centres sont déterminés en considérant les m noeuds les plus éloignés les uns des autres. Les groupes sont finalement obtenus en affectant chaque noeud à son centre le plus proche. La méthode qu'ils ont développée a permis d'obtenir les valeurs des solutions optimales pour ces instances, avec 10 < m < 89, où m est le nombre de groupes.

La solution optimale est toujours connue (fournis par l'algorithme de séparation et de génération de coupes de Fischetti et al. (1997)) pour les instances sélectionnées avec 10 < m < 89. Pour les instances restantes (99 < m < 217), Silberholz et Golden (2007) fournissent les meilleurs résultats connus, qui sont en fait les moyennes des résultats pour 5 essais de leur algorithme et de l'algorithme de Snyder et Daskin (2006). Il est important de noter que la valeur de la meilleure solution trouvée par ces algorithmes pour ces instances n'est pas disponible.

Pour tous les résultats expérimentaux, nous avons fixé le nombre d'individus par population (N) à 50 (ce qui est un nombre retenu dans plusieurs articles, par exemple dans (Silberholz et Golden, 2007)), le nombre de croisements (2 * k) est égal à 30, le nombre maximum d'itérations (N1) à 100 et le nombre maximum d'itérations pendant lesquelles la meilleure solution peut rester inchangée (N2) égal à 10 (ce nombre est assez bas, mais suffisant vu la taille des voisinages définis par les opérateurs de recherches

2. GTSPLIB est disponible à l'adresse http :// www.cs.rhul.ac.uk/home/zvero/GTSPLIB/

locales appliqués à chaque itération). Les résultats fournis sont les résultats moyens obtenus avec 5 essais par instance.

Les résultats présentés dans les tableaux 4.1 et 4.2 montrent les performances de notre algorithme en terme d'écart avec les solutions optimales fournies par le Branch & Cut de Fischetti et al. (1997) (tableau 4.1). Pour les instances restantes (pour 99 m
217), nous présentons nos résultats dans le tableau 4.2, comparés avec les meilleurs résultats fournis par Silberholz et Golden (2007).

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

- instance : le nom de l'instance testée; le premier nombre dans le nom indique le nombre de groupes, le deuxième donne le nombre de villes.

- opt : la valeur de la solution optimale ou la meilleure solution moyenne connue. - ]best : le nombre de fois où la meilleure solution (lorsqu'elle est connue) a été atteinte sur 5 essais.

- mean gap : l'écart moyen de notre algorithme à l'optimal ou la meilleure solution moyenne connue (pourcentage).

- min gap : l'écart minimal de notre algorithme à l'optimal ou la meilleure solution moyenne connue (pourcentage).

- max gap : l'écart maximal de notre algorithme à l'optimal ou la meilleure solution moyenne connue (pourcentage).

- CPU time : le temps d'exécution moyen en secondes.

Les chiffres écrits en gras représentent les cas où la solution trouvée est égale à la solution optimale, ou meilleure que la meilleure solution connue.

Le tableau 4.1 montre que, avec 5 essais, toutes les solutions obtenues sur les 41 instances sont égales aux solutions optimales et que pour 37 instances sur 41, les solutions sont égales aux solutions optimales pour chaque essai. L'écart entre le meilleur et le moins bon résultat trouvé sur les 5 tests pour chaque instance est toujours relativement limité, ce qui tend à montrer que l'algorithme est robuste. Enfin, dans le pire des cas, le pourcentage d'écart ne dépasse jamais 0,75 % pour les instances les plus importantes.

Pour les instances de grandes tailles (tableau 4.2), pour lesquelles les solutions optimales ne sont pas connues, les résultats montrent que pour certaines instances, nos pires résultats parmi les cinq essais sont meilleurs que la moyenne des solutions produites par la méthode proposée par Silberholz et Golden (2007) (par exemple, l'instance 207si1032 qui contient 1032 noeuds). Dans le pire cas, les solutions produites par notre algorithme ne dépassent jamais un écart de plus de 0,66 % par rapport au meilleur résultat moyen entre l'algorithme de Silberholz et Golden et l'algorithme de Snyder et Daskin. Enfin, la moyenne de nos solutions est de plus mauvaise qualité que celles proposées par les algorithmes cités précédemment pour seulement 3 instances.

Le tableau 4.3 présente nos meilleurs résultats parmi cinq essais pour douze instances ouvertes pour lesquelles la solution optimale n'est pas connue. Les résultats présentés sont les solutions produites par notre algorithme et les meilleures moyennes des solutions sur cinq essais entre l'algorithme de Silberholz et Golden et l'algorithme de Snyder et Daskin.

Afin de mesurer plus précisément l'efficacité de l'opérateur de croisement que nous proposons, nous avons aussi implémenté un opérateur de croisement plus simple, connu sous le nom de croisement à un point (One-point crossover, (Goldberg, 1989)). Les paramètres sont les mêmes pour les deux opérateurs de croisement. Les tableaux 4.4 et 4.5 donnent des informations sur les différences en terme de qualité des solutions et de rapidité d'exécution entre l'opérateur de croisement dropstar et l'opérateur de croisement One-Point pour les instances fermées 4.4 et les instances ouvertes 4.5. Les en-têtes des colonnes sont les suivants :

- instance : le nom de l'instance testée; le premier nombre dans le nom indique le nombre de groupes, le deuxième donne le nombre de villes.

- opt : la valeur de la solution optimale pour l'instance ou la meilleure solution moyenne connue.

- mean gap : l'écart moyen de notre algorithme à l'optimal ou la meilleure solution moyenne connue (pourcentage).

- CPU time : le temps d'exécution moyen en secondes.

Des expérimentations ont été conduites afin de déterminer les avantages de l'opérateur de croisement dropstar comparé à l'opérateur de croisement One-Point. L'opérateur de croisement dropstar se montre nettement plus efficace en ce qui concerne la qualité des solutions. Pour les instances de petites tailles (pour lesquelles la solution optimale est connue, tableau 4.4), l'écart moyen sur l'ensemble des instances pour l'opérateur de croisement One-Point est égal à 0,26% alors que l'écart moyen est réduit à 0,02 % avec l'opérateur de croisement dropstar. Les temps d'exécution pour l'opérateur de croisement Dropstar sont néanmoins beaucoup plus importants, l'opérateur de croisement One-Point étant en moyenne six fois plus rapide.

Pour les instances de grandes tailles présentées dans le tableau 4.5, l'opérateur de croisement Dropstar produit de biens meilleures solutions que l'opérateur de croisement One-Point, tout en conservant un même ordre de grandeur de différence pour les temps de calcul.

Le tableau 4.6 présente une comparaison entre l'algorithme génétique mrOX proposé par Silberholz et Golden (2007), l'algorithme génétique de Snyder et Daskin (2006), le GI³ de Renaud et Boctor (1998a) et enfin, l' algorithme de Branch & Cut de de Fischetti et al. (1997).

Les résultats des différents algorithmes présentés ont été obtenus sur les machines suivantes :

- mrOX et Snyder et Daskin : Pentium IV 3.0 GHz et 1 Go de RAM.

- GI³ : Sun Sparc Station LX.

- B& C. : HP 9000/720.

Pour chaque algorithme, deux colonnes sont présentées:

- Gap : l'écart moyen de l'algorithme à l'optimal (pourcentage).

- CPU : le temps mis par l'algorithme en secondes.

La colonne B&C ne présente pas d'écart, puisque cet algorithme est un algorithme exact, qui propose des solutions optimales.

Les résultats présentés dans le tableau 4.6 montrent que notre algorithme est plus performant que les autres algorithmes heuristiques. Pour l'ensemble des solutions pour lesquelles les solutions optimales sont connues, notre algorithme retourne en moyenne un taux d'erreur égal à 0,02 %. De plus, les solutions renvoyées peuvent être très proches des solutions optimales et ce, même pour les instances de grandes tailles.

On peut remarquer par ailleurs que les instances de petites tailles sont résolues à l'optimum très rapidement par l'ensemble des algorithmes.

Les comparaisons de temps de calcul avec les autres algorithmes heuristiques sont complexes car différentes machines ont été utilisées pour tester les algorithmes. Les expérimentations montrent tout de même que notre algorithme est plus lent que l'algorithme mrOX ou l'algorithme de Snyder et Daskin. Cependant, le but de notre algorithme était d'obtenir les meilleurs résultats possibles en terme d'écart avec les solutions optimales. On peut cependant noter que notre algorithme peut proposer des solutions de bonne qualité en des temps relativement courts.

Nous proposons aussi nos propres instances, basées sur les instances classiques du problème du Voyageur de Commerce, tirées de la librairie TSPLIB³. Pour une instance donnée, le nombre de groupes est fixé à m = [n/51. Les groupes sont numérotés de 0 à m - 1. Chaque ville vi est associée au groupe Wj pour lequel j est égal à i mod m. Puisque les instances du problème du Voyageur de Commerce proposées par la librairie TSPLIB sont construites de telle façon que les villes sont placées aléatoirement, le partitionnement que nous proposons ne simule pas de régions géographiques. Dans ce partitionnement de villes, un groupe de villes peut représenter un ensemble de villes dans lequel chaque ville propose un service identique ou un même produit. L'objectif du problème du Voyageur de Commerce Généralisé est alors de trouver un tour qui minimise la somme des distances, tout en respectant la contraintes d'obtenir une fois chaque service ou chaque produit. Le partitionnement que nous proposons est déterministe, il peut donc être facilement reproduit.

Les tableaux 4.7 et 4.8 donnent des informations sur les différences en terme de qualité des solutions et de rapidité d'exécution entre l'opérateur de croisement dropstar et l'opérateur de croisement One-Point pour les instances que nous proposons. Les entêtes des colonnes sont les suivants :

- instance : le nom de l'instance testée; le premier nombre dans le nom indique le nombre de groupes, le deuxième donne le nombre de villes.

- min : la valeur minimale trouvée par l'algorithme.

- mean : la moyenne des valeurs trouvées par l'algorithme.

- CPU time : le temps d'exécution moyen en secondes.

Les conclusions tirées à la lecture des tableaux 4.7 et 4.8 sont similaires à celles énoncées pour les tableaux 4.4 et 4.5. L'opérateur de croisement dropstar se montre nettement plus efficace en ce qui concerne la qualité des solutions. Pour les instances de petites tailles, les meilleures solutions pour l'opérateur de croisement One-Point sont à peine supérieures à celles trouvées avec l'opérateur de croisement dropstar. Les temps d'exécution pour l'opérateur de croisement Dropstar sont néanmoins beaucoup plus impor-

3. http :// www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/

tants, l'opérateur de croisement One-Point étant en moyenne onze fois plus rapide. Par contre, pour les instances de grandes tailles, l'écart se creuse, mais les temps de calcul nécessaires pour l'opérateur de croisement Dropstar sont beaucoup plus importants. On remarque néanmoins que les instances que nous proposons semblent plus difficiles à résoudre, même pour l'opérateur de croisement One-Point. On peut donc en déduire que les opérateurs de recherche locale semblent être plus efficaces avec le partitionnement proposé par Fischetti et al. (1997).