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

2.3.2 Autres variantes de Problèmes de Tournées à Couverture Partielle

On trouve d'autres variantes du problème du Voyageur de Commerce relativement proches des problèmes présentés :

- Traveling Purchaser Problem (Ramesh, 1981) : dans ce problème, les villes sont remplacées par des marchés. Chaque marché fournit un sous-ensemble de produits. Le prix de vente de chaque produit est connu et les prix des produits sont dépendants du marché à partir duquel ils sont achetés. L'objectif consiste à trouver un tour qui part d'un dépôt, connectant un sous-ensemble de marchés, de telle sorte que l'ensemble des produits soit acheté et que la somme des coûts de transport et des coûts d'achat des produits soit minimisée (voir le chapitre 3 pour plus de détails sur ce problème).

- Covering Tour Problem (Gendreau et al., 1997) : dans ce problème, un ensemble T de sommets doit être visité et un ensemble W de sommets doit être couvert. L'objectif est de trouver un cycle hamiltonien de longueur minimale qui visite l'ensemble des sommets de T de telle sorte que chaque sommet de W ait une distance inférieure à une longueur prédéterminée avec au moins un sommet du cycle.

- Generalized Traveling Salesman Problem (Henry-Labordere, 1969) : dans ce problème, les sommets appartiennent à des groupes. L'objectif est de construire un tour qui visite exactement une fois chaque groupe tout en minimisant les coûts de transport (voir le chapitre 4 pour plus de détails sur ce problème).

2.3.3 Complexité des Problèmes de Tournées avec Couverture Partielle

L'ensemble des problèmes présentés, aussi bien dans leurs versions mono-véhicule que dans les versions avec une flotte de véhicules, sont NP-difficiles. Ceci est généralement facile à prouver : dans la plupart des cas, on peut se ramener à un problème de type Voyageur de Commerce qui est NP-difficile au sens fort.

2.3.4 Quelques opérateurs de recherche locale pour les Problèmes de Tournées avec Couverture Partielle

Il existe un certain nombre d'opérateurs de recherche locale, utilisés entre autres pour les problèmes de Tournées avec Gains. On peut classer les opérateurs de recherche locale en deux sous catégories:

- sans changement des sommets visités : ces opérateurs modifient l'ordre de visite des sommets dans un tour dans le cas où un seul véhicule est disponible (2-opt (Croes, 1958), heuristique de Lin et Kernighan (1973), ...) ou changent l'affection des sommets entre les tournées (croisement (Montané et Galvão, 2006), échange (Tan et al., 2001), repositionnement (Montané et Galvão, 2006), ...);

- avec changement des sommets visités : ces opérateurs tirent partie du fait que l'ensemble des sommets n'est pas visité (insertion d'un sommet -ou d'une chaîne de sommets- dans la tournée (Riera-Ledesma et Salazar-González, 2005), suppression d'un sommet (Pisinger et Ropke, 2007) ou d'une chaîne de sommets (RieraLedesma et Salazar-González, 2005)).

Nous nous sommes intéressés plus particulièrement à cette dernière catégorie de voisinages. Les quelques exemples qui suivent (figures 2.1-2.5) présentent un aperçu d'opérateurs connus.

9

6

8

5

2

10

3

7

0 4 1

2

1

3

0

4

5

6

FIGURE 2.1 - Exemple de solution initiale

FIGURE 2.2 - Application d'un échange entre les sommets 2 et 6

1

2

3

0

4

5

6

FIGURE 2.3 - Application de l'opérateur insertion

Chapitre 2. La recherche à grand voisinage : un nouvel opérateur

2

3

0

4

5

1

6

6

1

2

3

0

4

5

FIGURE 2.4 - Application de l'opérateur suppression

FIGURE 2.5 - Application d'un 2-opt entre les sommets 2 et 5 : le chemin entre ces sommets est inversé

2.4 Dropstar : une nouvelle structure de grand voisinage

2.4.1 Des opérateurs existants : drop, l-ConsecutiveDrop

Afin de présenter l'intérêt du nouvel opérateur de voisinage que nous proposons, nous nous appuierons sur un exemple simpliste du problème de Tour avec Profits (Profitable Tour Problem ou PTP). On définit le Profitable Tour Problem de la manière suivante. Soit G = (V, E) un graphe non orienté avec V = {v1, . . . , vn} un ensemble de sommets pour lequel v1 est le dépôt. On note cij le coût de l'arc (vi, vj). On associe à chaque sommet vi un gain supposé positif. L'objectif est de minimiser la différence entre la somme des distances parcourues et la somme des gains récoltés. Les chiffres situés sur les sommets de la figure 2.6 représentent le gain associé à chaque sommet et les chiffres situés sur les arcs, la distance entre deux sommets. Dans le cas où toutes les villes ne doivent pas être visitées, comme c'est le cas ici, on peut appliquer la procédure DROP utilisée par de nombreux chercheurs sur ces classes de problèmes (Ramesh et Brown, 1991; Mittenthal et Noon, 1992; Voß, 1996). Cet opérateur retire un sommet d'une solution initiale dans le cas où ce retrait permettrait de diminuer le coût de la fonction objectif.

Posons la solution initiale (Fig. 2.7), de coût égal à --1. Lorsqu'on applique la procédure DROP, la seule suppression qui permet de diminuer le coût de la fonction objectif est la suppression du sommet 4. On a alors la solution 0 1 2 3 0 de coût égal à --2, présentée dans la figure 2.8. Le but étant de minimiser la fonction objectif, on se rend compte que cette solution est un optimum local relativement à la procédure DROP. En effet, si l'on se limite à la suppression d'une seule ville de cette solution, on ne peut améliorer la solution courante.

Devant la limitation de la taille de l'espace de recherche défini par ce voisinage, Riera-Ledesma et Salazar-González (2005) ont proposé une extension de ce voisinage qu'ils ont appliquée au problème de l'Acheteur Itinérant. Ils ont nommé ce nouveau voisinage : l-ConsecutiveDrop. Ce voisinage peut se retrouver sous des formes similaires pour ces classes de problèmes (Keller, 1989; Renaud et Boctor, 1998b; Hachicha et al., 2000; Dell'Amico et al., 1998). Ce voisinage essaie de réduire la longueur d'un cycle initial en supprimant l sommets consécutifs. Si on applique cette procédure à la solution présentée dans la figure 2.8, en choisissant l = 2, on améliore la solution courante en obtenant la solution présentée dans la figure 2.9, de coût égal à --4. Cette solution aurait aussi pu être obtenue en supprimant dans un premier temps les sommets 1 et 2 de la solution initiale (la solution ainsi obtenue serait 0 3 4 0 de coût égal à -3), puis en supprimant de cette solution le sommet 4.

Néanmoins, cette procédure présente des limitations. Considérons l'exemple présenté dans la figure 2.10. Nous posons alors la solution initiale 0 1 2 3 4 5 0 de coût égal à --1 présentée dans la figure 2.11. Si on applique la procédure l-ConsecutiveDrop, on peut voir que cette solution initiale est un optimum local pour l fixé à 4.

En diminuant la valeur de l (l est alors égal à 3), on améliore la solution courante en obtenant la solution 0 4 5 0 de coût égal à --2 présentée dans la figure 2.12. Cette solution est de plus un optimum local relativement à la procédure l-ConsecutiveDrop. Cependant, on peut remarquer qu'en appliquant en premier lieu une procédure 2- ConsecutiveDrop, on aurait obtenu la solution optimale 0 3 4 5 0 de coût égal à --19, présentée dans la figure 2.13. On se rend compte ainsi que la valeur de l est déterminante dans l'efficacité de la procédure et que la limitation à la suppression de sommets consécutifs peut être un frein à l'efficacité de cette procédure.

10

10

10

24

10

10

13

FIGURE 2.6 - Exemple de Profitable Tour Problem

10

10

10

24

10

13

FIGURE 2.7 - Exemple de Profitable Tour Problem : Solution initiale

10

10

10

0

24

10

4

13

FIGURE 2.8 - Exemple de Profitable Tour Problem : Solution après un Drop

9

1

9

2

10

3 24

0

10

4

13

FIGURE 2.9 - Exemple de Profitable Tour Problem : Solution après un 2-ConsecutiveDrop

10

10

10

10

18

18

10

23

10

10

5

4

FIGURE 2.10 - Autre exemple de Profitable Tour Problem

10

10

10

23

10

10

10

4

18

18

5

FIGURE 2.11 - Autre exemple Profitable Tour Problem : Solution initiale

1

1

1

2

18

18

3 23

0

10

5

4

10

FIGURE 2.12 - Exemple de Profitable Tour Problem : Solution après un 3-ConsecutiveDrop

1

1

1

2

10

 

23

 

10

 
 
 

10

10

18

18

FIGURE 2.13 - Exemple de Profitable Tour Problem: Solution optimale

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








"Les esprits médiocres condamnent d'ordinaire tout ce qui passe leur portée"   François de la Rochefoucauld