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.4.2 L'opérateur de grand voisinage : Dropstar

La procédure Dropstar définit un opérateur de grand voisinage. Il est basé sur le sous-problème suivant : trouver une sous-séquence optimale à partir d'une séquence initiale donnée. Cet opérateur détermine ainsi l'ensemble optimal des sommets (consécutifs ou non) à supprimer d'une séquence.

On peut penser que la calcul de la sous-séquence optimale est coûteux. En effet, la recherche d'une sous-séquence optimale peut être un problème NP-difficile, comme

nous le verrons par exemple dans le chapitre 3. Cette recherche est ici effectuée par le biais d'un algorithme de programmation dynamique récursif.

On construit un graphe selon la procédure suivante. Comme exemple de solution initiale, nous reprenons la solution présentée dans la figure 2.8. Un sommet est créé pour chaque ville de la séquence, le premier sommet de la séquence est dupliqué et placé en fin de séquence. Des arcs sont ensuite ajoutés entre chaque sommet et les sommets qui le suivent dans la séquence initiale (cf. Fig. 2.14). La procédure dropstar consiste alors à trouver le plus court chemin dans le graphe entre le premier sommet et le dernier sommet, en respectant certaines contraintes de ressources. Le coût du chemin est alors égal à la somme des coûts des distances, à laquelle on peut avoir à ajouter le coût des ressources (par exemple, les coûts d'achat des produits dans le cas du problème de l'Acheteur Itinérant).

0 1 2 3 0

9 9 24

10

14

10

10

10

0

10

10

10

10

FIGURE 2.14 - Graphe résultant de la procédure Dropstar, appliqué sur la solution de la figure 2.8

La complexité de la recherche d'une sous-séquence optimale dépend en partie de la présence ou non de ressources. Dans le cas par exemple du Problème de Tour avec Profits, en l'absence de ressource, la recherche d'une sous-séquence optimale et donc d'un plus court chemin est polynomiale. Par contre, la consommation en cours de chemin des ressources disponibles en quantités limitées peut rendre le problème NP-difficile (voir par exemple le chapitre 3 pour plus de détails).

L'algorithme de programmation dynamique que nous utilisons pour trouver le plus court chemin dans le graphe est inspiré de l'algorithme développé par Feillet et al. (2004) pour le Problème du Plus Court Chemin Élémentaire avec Contraires de Res-sources. Cet algorithme est une extension du célèbre algorithme de Bellman (1957).

Un important travail est à effectuer afin d'accélérer cette procédure pour la rendre applicable pour les instances de taille importante. Ce travail porte essentiellement sur les conditions de dominances et sur l'analyse des solutions initiales, afin d'essayer de réduire la taille du graphe sur lequel appliquer la procédure Dropstar.

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








"Et il n'est rien de plus beau que l'instant qui précède le voyage, l'instant ou l'horizon de demain vient nous rendre visite et nous dire ses promesses"   Milan Kundera