5.7 Deux approches différentes pour la
réalisabilité du chargement
Nous avons développé deux approches
résolument différentes : dans la première, le
problème esclave de recherche de plus court chemin renvoie des routes
réalisables du point de vue de la contrainte de capacité, mais,
dont la réalisabilité en ce qui concerne le chargement à
deux dimensions n'est pas assurée. Cette réalisabilité est
vérifiée a posteriori. La seconde approche, quant
à elle, construit des routes entièrement réalisables
(capacité et chargement séquentiel en deux dimensions) pendant la
résolution du sousproblème.
5.7.1 Vérification de la
réalisabilité a posteriori
Dans la méthode telle que nous l'avons
présentée, le problème esclave trouve des routes de
coûts réduits négatifs et insère les colonnes
correspondant à ces routes dans 1). Par contre, on a montré que,
si les routes renvoyées par le problème esclave respectent les
contraintes de capacités, elles ne respectent pas nécessairement
les contraintes de chargement. Il est donc nécessaire de vérifier
ces contraintes avant d'insérer les colonnes dans 1). Dans cette
méthode, l'aire occupée par le chargement n'est pas prise en
Chapitre 5. Application au problème de Tournées de
Véhicules avec Contraintes de Chargement
(7,5)
5
(3,1)
4
(2,2)
2
4
2
3
2
(0,2)
~~~~~~~~~~
~~~~~~~~~~
~~~~~~~~~~
~~~~~~~~~~ 3
~~~~~~~~~~ ~~~~~~~~~~ ~~~~~~~~~~ ~~~~~~~~~
FIGURE 5.11 -
Représentation des coordonnées des objets
après insertion
considération pour les règles de dominances,
puisque le chargement n'est déterminé qu'a posteriori. La borne
inférieure sur l'aire occupée (définie comme la somme des
aires des objets chargés) est néanmoins utilisée pour
vérifier la réalisabilité de l'extension d'un chemin
partiel vers un client.
Si le calcul des bornes inférieures montre que le
chargement n'est pas réalisable, la route est ajoutée dans
l'annuaire de routes non-réalisables. Dans le cas contraire, nous
appliquons les algorithmes dans l'ordre dans lequel ils ont été
présentés dans la section 5.6.5. Les heuristiques de chargement
sont appelées, avec des listes d'objets triées selon des ordres
différents (ordre décroissant sur la largeur, ordre
décroissant sur la hauteur, ordre croissant sur la largeur et ordre
croissant sur la hauteur). Dès qu'un algorithme indique que le
chargement est réalisable, la route est ajoutée. Si aucun
algorithme ne trouve un chargement réalisable, la route est
ajoutée à l'annuaire des routes non-réalisables. Enfin,
dans le cas où le sous-problème ne trouve aucune route de
coût réduit négatif respectant les contraintes de
chargement, la résolution du problème esclave est
arrêtée et la relaxation linéaire du problème
maître restreint est alors résolue.
(5,4)
4
5
(3,2)
2
3
(2,2)
2
2
(4,2)
4
2
FIGURE 5.12 - Représentation
des coordonnées des objets sur un autre exemple
Gestion efficace des chargements
Nous avons ajouté une gestion efficace des routes non
réalisables. Le calcul de réalisabilité d'une route est un
calcul complexe, nécessitant d'être appelé un nombre
important de fois. Ainsi, dès qu'une route est désignée
comme non-réalisable par les méthodes de calculs de bornes
inférieures, cette route est stockée dans un annuaire de routes.
Cet annuaire a une structure d'arbre n-aire classé, pour lequel
l'insertion d'une route et la vérification de la présence d'une
route sont des méthodes rapides et peu complexes. L'annuaire a la
structure décrite par la figure 5.17.
Dans cet annuaire, nous ne stockons que les routes non
réalisables. En effet, les routes réalisables ne sont
vérifiées qu'une seule fois, puisqu'elle sont ensuite
ajoutées dans 1) et qu'elles ne sont jamais supprimées de cet
ensemble. On ne vérifie donc jamais deux fois la même route, si
celle-ci est réalisable.
| 
