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

5.7.2 Construction de routes réalisables dans le sous-problème

Nous proposons dans cette méthode de construire dans le problème esclave des routes réalisables, respectant donc les contraintes de chargement séquentiel. Pour cela, nous modifions les données sauvegardées pour chaque chemin partiel. Tel que présenté précédemment, sont associés à un chemin partiel un coût, un poids, une aire restante et

Chapitre 5. Application au problème de Tournées de Véhicules avec Contraintes de Chargement

(5,4)

(4,6)

4

2

2

5

4

2

2

3

~~~~~~~~ ~~~~~~~~ ~~~~~~~~ ~~~~~~~~

FIGURE 5.13 - Mise à jour des coordonnées des objets après insertion sur un autre exemple

FIGURE 5.14 - Bottom Left
FIGURE 5.15 - Improved Bottom Left

une liste de sommets non accessibles. À cela, nous ajoutons une liste des positions possibles telle que présentée dans les figures 5.10 et 5.11. Chaque fois qu'un chemin partiel est étendu vers un sommet, la liste des objets proposés par le sommet est crée. On essaie alors d'ajouter les objets dans le chargement existant, ce chargement étant représenté par la liste des positions possibles. Pour cela, nous faisons appel aux algorithmes heu-

(7,5)

4

5

4

(3,1)

3

2

~

~

~

~~
~~

~~
~~

~~
~~

~~

~

~~

~

3

(2,2)

2

2

(0,2)

FIGURE 5.16 - Max Touching Perimeter

5

1

0

6

7 8

2

FIGURE 5.17 - Structure d'un annuaire

ristiques présentés dans la section 5.6.5. Ainsi, toutes les routes de coût négatif trouvées
157

Chapitre 5. Application au problème de Tournées de Véhicules avec Contraintes de Chargement

par le problème esclave sont nécessairement des routes réalisables. Cependant, dans le cas où l'heuristique utilisée ne trouve pas de chargement réalisable, la route est éliminée, bien qu'un chargement réalisable puisse exister. La méthode proposée est donc une méthode heuristique.

Chaque heuristique peut calculer l'aire restante à partir de la liste des positions disponibles. Soit wni et hni la largeur et la hauteur correspondant aux point ni de la liste des points disponibles et H la hauteur de la surface de chargement. Soit T la taille de la liste des points possibles. L'aire restante est égale à :

T

airerestante = ? wni × (H - hni) (5.43)

i=0

La figure 5.18 présente le calcul de l'aire restante appliquée sur l'exemple présenté par la figure 5.11.

2

~~~~~~~~~~ ~~~~~~~~~~ ~~~~~~~~~~ ~~~~~~~~~~ ~~~~~~~~~~ ~~~~~~~~~~ ~~~~~~~~~~ ~~~~~~~~~~ ~~~~~~~~~~ ~~~~~~~~~~ ~~~~~~~~~~ ~~~~~~~~~~ ~~~~~~~~~~ ~~~~~~~~~~

(7,5)

~~~~~~~~~~

~ (3,1)

~ ~~~~~ ~ ~~~~~ ~ ~~~~~ ~ ~~~~~ ~ ~~~~~ ~ ~~~~~ ~ ~~~~~ ~ ~~~~~ ~ ~~~~~ ~ ~~~~~ ~ ~~~~~ ~ ~~~~~ ~ ~~~~~ ~ ~~~~~ ~ ~~~~~ ~ ~~~~~ ~ ~~~~~ ~ ~~~~~ ~ ~~~~~ ~~~~~ ~ ~~~~~ ~~~~ ~~~~ ~~~~~

~~~~~ ~~~~~ ~~~~~ ~~~~~ ~~~~~ ~~~~~ ~~~~~ ~~~~~ ~~~~~ ~~~~~ ~~~~~ ~~~~~ ~~~~~ ~~~~~ ~~~~~ ~~~~~ ~~~~~ ~~~~~ ~~~~~ ~~~~~ ~~~~~

(2,2) ~~~~~

~~~~

(0,2)

~~~~

~~~

~~~~~

~~~~~~~~~~

3

4

4

 

2

3

2

FIGURE 5.18 - Calcul de l'aire restante d'un chargement

Cette aire peut être utilisée pour vérifier en prétraitrement si les objets du sommet j peuvent être ajoutés. Lorsque les routes sont construites dans le sous-problème, l'heuristique de chargement reste tout le temps la même. Ainsi, l'aire occupée peut être utilisée de manière heuristique afin de renforcer les règles de dominance. Néanmoins, il faut garder en mémoire que dans ce cas, les régles de dominance sont trop fortes et risquent donc de supprimer des chemins partiels non véritablement dominés.

5.8. Branch & Price heuristique

Cette méthode présente l'intérêt de laisser tout le calcul de réalisabilité des routes dans le problème esclave. On peut donc garantir l'optimalité de la méthode, sous réserve d'avoir défini une règle de chargement exacte.

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








"Tu supportes des injustices; Consoles-toi, le vrai malheur est d'en faire"   Démocrite