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.
| 
