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

4.2 État de l'art

Le GTSP fut introduit en premier par Srivastava et al. (1969) et Henry-Labordere (1969), qui ont proposé chacun une résolution par un algorithme de programmation dynamique. Laporte et Nobert (1984) et Laporte et al. (1984) ont proposé une approche par programmation en nombres entiers afin de résoudre le GTSP de manière exacte. Plus récemment, Fischetti et al. (1997) ont proposé une résolution efficace basée sur une procédure de séparation et génération de coupes, qui a permis de fournir des résultats optimaux pour des instances contenant jusqu'à 442 noeuds.

4.2. État de l'art

Plusieurs travaux ont été menés pour transformer le GTSP en TSP (Lien et al., 1993; Noon et Bean, 1993; Dimitrijevic et Saric, 1997; Laporte et Semet, 1999; Ben-Arieh et al., 2003). Certaines des instances de TSP issues de ces transformations ont un nombre similaire de noeuds comparé au nombre de noeuds de l'instance de GTSP initiale. De plus, certaines transformations de GTSP en TSP (Noon et Bean, 1993) ont une propriété importante : une solution optimale du TSP créé peut être transformée en une solution optimale du GTSP. Malheureusement, une solution réalisable non optimale pour le TSP créé peut ne pas être réalisable pour le GTSP. De plus, certaines heuristiques très efficaces pour le TSP ont eu des résultats peu convaincants pour le GTSP (Slavík, 1997; Dror et Haouari, 2000)

Deux algorithmes d'approximations ont été proposés pour le GTSP. Slavík (1997) a présenté une approximation en 3p/2, pour laquelle p est le nombre de villes dans le plus grand groupe (p = max (|Vm|)). Cependant, la borne dans le pire cas peut être de

i=1,...,m

piètre qualité, la borne supérieure de p étant égale au nombre de noeuds. Garg et Konjevod (2000) ont proposé un algorithme d'approximation pour le problème d'arbre de Steiner, amenant à un algorithme d'approximation en O(log2(|V|) log log(|V|)) log(m)) pour le GTSP. Dans les deux cas, les inégalités triangulaires doivent être respectées.

Noon et Bean (1991) ont proposé plusieurs heuristiques, en particulier une adaptation de l'heuristique du plus proche voisin utilisée pour le TSP. Des adaptations similaires ont été proposées par Fischetti et al. (1997), telles que la plus lointaine insertion, la plus proche insertion ou encore l'insertion à plus faible coût. Plus récemment, Renaud et Boctor (1998a) ont proposé l'heuristique GI3 (Generalized Initialization, Insertion and Improvement), qui est une généralisation de l'heuristique I3, présentée dans (Renaud et al., 1996). Cette heuristique se déroule en trois phases : une phase d'initialisation du-rant laquelle on construit un tour qui peut ne pas être valide, une phase d'insertion qui complète les tours incomplets en insérant au plus faible coût les villes provenant de groupes non visités et une phase d'amélioration qui utilise des modifications de voisinages de type 2-opt et 3-opt, appelées ici G2-opt et G3-opt. Cet article présente aussi l'algorithme ST (pour Shortest Tour). Cet algorithme détermine la séquence de villes de plus petit coût qui visite les groupes dans un ordre fixé. Ils montrent que ce problème peut être résolu en un temps polynomial.

Snyder et Daskin (2006) ont proposé récemment une résolution par un algorithme génétique utilisant un encodage par clé aléatoire, encodage qui assure que les solutions construites par croisement ou mutation sont des solutions valides. Cet algorithme génétique est couplé avec des améliorations par recherche locale, définissant un algorithme mémétique, une procédure d'échange et un voisinage de type 2-opt (voir (Moscato et Cotta, 2005) pour plus de détails sur les algorithmes mémétiques). Leurs résultats expérimentaux montrent que leur algorithme est performant, que ce soit en terme de qualité de solution ou de temps de calcul. Un algorithme basé sur l'optimisation par essaims particulaires a été récemment présenté par Shi et al. (2007). Une procédure pour supprimer les croisements dans les tours a été utilisée pour accélérer la vitesse de convergence, appuyée par deux techniques de recherche locale. Malgré cela, les résultats présentés ne parviennent pas à dépasser les meilleures heuristiques connues.

Enfin, Silberholz et Golden (2007) ont proposé un algorithme génétique avec plusieurs nouvelles techniques, entre autres, des populations initiales isolées, ainsi qu'une nouvelle procédure de reproduction, basé sur l'opérateur de croisement ordonné pour le TSP. Cette nouvelle procédure est appelée mrOX, pour croisement ordonné de rotation modifié (modified rotational ordered crossover). Les procédures d'améliorations locales associées à cet opérateur de croisement, définissant un algorithme mémétique, ont permis d'obtenir de très bons résultats sur de nouvelles instances de taille importante et de dépasser les autres solutions heuristiques en ce qui concerne la qualité des solutions obtenues. L'algorithme proposé par Silberholz et Golden (2007) peut être considéré comme l'algorithme le plus compétitif publié à ce jour.

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








"Ceux qui vivent sont ceux qui luttent"   Victor Hugo