5.3 État de l'art
5.3.1 Résolution du 2L-VRP
Le problème de Tournées de Véhicules avec
Contraintes de Capacité ou Capacited Vehicle Routing Problem
(CVRP) est un des problèmes d'optimisation combinatoire les plus
fréquemment étudiés. L'objectif est de minimiser la
distance totale parcourue par une flotte de véhicules d'une
capacité limitée, sous la contrainte de satisfaire l'ensemble des
demandes de livraisons des clients. L'application de ce modèle à
des cas pratiques est limitée par la présence d'une multitude de
contraintes additionnelles. En particulier, dans le CVRP, les demandes des
clients sont exprimées par des valeurs entières,
résumant le poids total ou le volume total des objets
devant être livrés. Pour des applications pratiques, les demandes
consistent en un ensemble d'objets, caractérisés par un poids et
une forme.
Dans le domaine des transports, il est souvent
nécessaire de manipuler des objets de formes rectangulaires. Dans
certains cas, ces objets ne peuvent être empilés les uns au-dessus
des autres (par exemple, pour cause de fragilité). Dans ce cas, on peut
se limiter à caractériser les objets à livrer en deux
dimensions : largeur et hauteur. On part alors du principe que la hauteur de
chacun des objets est inférieure à la hauteur de la surface de
chargement des véhicules (de même que la largeur). De plus, chaque
client peut avoir une demande représentée par plusieurs objets.
On parle alors de problème de Tournées de Véhicules avec
Contraintes de Chargement à Deux Dimensions.
Le problème de Tournées de Véhicules avec
Contraintes de Chargement Tri-Dimensionnelles ou three-dimensional loading
capacitated vehicle routing problem (3L-CVRP) a été
étudié par Gendreau et al. (2006). L'algorithme
proposé est une généralisation au cas à trois
dimensions de la méthode par recherche tabou publiée
postérieurement (Gendreau et al., 2008). Dans le
problème tel qu'il est présenté, la demande des clients
est représentée par des objets en trois dimensions avec un poids.
Ce problème a été moins étudié que la
version à deux dimensions.
Dans le domaine de l'optimisation combinatoire, le chargement
d'objets et les problèmes de Tournées de Véhicules ont
été intensément étudiés, mais dans la
plupart des cas, de manières séparées. Ce n'est que
récemment que les chercheurs se sont penchés sur la
résolution de problèmes combinant les deux aspects.
Le 2L-VRP a une décomposition naturelle en trois
sous-problèmes:
1. Un problème d'affectation, qui consiste à
déterminer par quel véhicule les clients sont servis,
2. Un problème de Tournées, qui consiste à
déterminer l'ordre dans lequel les clients sont visités,
3. Un problème de chargement qui consiste à
vérifier si les tournées sont réalisables vis-à-vis
des contraintes de séquentialité, de capacité et de
surface.
Ces trois problèmes peuvent être traités de
manière globale, par coopération d'algorithmes ou par une
succession d'algorithmes.
Le problème 2L-VRP consiste donc à proposer des
routes avec des chargements réalisables. Nous allons maintenant
détailler le concept de réalisabilité pour une route. Dans
le problème 2L-VRP, le chargement est restreint à être
orthogonal, c'est-à-dire que chaque objet doit être chargé
avec ses côtés parallèles aux cotés du
véhicule dans lequel il est chargé. Pour chaque véhicule,
tous les objets transportés doivent être entièrement
compris dans la surface de livraison et ne peuvent se chevaucher. De plus, la
somme totale des poids des objets ne peut dépasser la capacité en
poids des véhicules.
Une contrainte d'ordre pratique assez courante est la suivante
: lorsqu'un client est visité, tous les objets devant lui être
livrés doivent être déchargés à l'aide d'un
chariot élévateur, sans avoir à déplacer les objets
qui seront livrés aux prochains clients sur la
Chapitre 5. Application au problème de Tournées de
Véhicules avec Contraintes de Chargement
tournée du véhicule. Cela implique donc que la
portion de surface de chargement située entre chaque objet du client qui
est en train d'être servi et l'arrière du véhicule doit
être vide (ou utilisée par d'autres objets du même client,
qui seront déchargés en premier). Cette contrainte est
notée dans la littérature comme un chargement séquentiel,
ou une contrainte de chargement arrière (rear loading
constraint, (Iori et al., 2007)). Le terme de chargement libre ou
unrestricted loading (voir (Gendreau et al., 2008) pour plus
de détails) est utilisé lorsque des arrangements du chargement
d'objets dans le véhicule sont autorisés à chaque
livraison.
Enfin, dans certains cas, les objets peuvent être
tournés de 90°. Il existe néanmoins des cas pratiques pour
lesquels cette rotation n'est pas autorisée. Ce cas est appelé un
chargement orienté (oriented loading). Il peut avoir lieu, par
exemple, lorsque les objets sont placés sur des palettes d'ancienne
génération qui ne sont accessibles pour les chariots
élévateurs que depuis une seule direction, ou encore, lorsque le
poids de l'objet est mal réparti sur les palettes. Dans la plupart des
cas de la littérature, le problème du 2L-VRP a été
étudié dans le cas où les objets ne peuvent être
tournés et dont l'orientation est fixe. Le chargement pour lequel on
autorise la rotation des objets est appelé non-orienté.
En se référant aux classifications
présentées ci-dessus concernant les configurations de chargement,
on peut distinguer quatre cas :
- 2|RO|L : chargement par l'arrière orienté
à deux dimensions (two-dimensional rear oriented loading);
- 2|UO|L : chargement par l'arrière non-orienté
à deux dimensions (two-dimensional unrestricted oriented
loading);
- 2|RN|L : chargement libre orienté à deux
dimensions (two-dimensional rear non-oriented loading);
- 2|UN|L : chargement libre non-orienté à deux
dimensions (two-dimensional unrestricted non-oriented loading).
Iori et al. (2007) ont résolu le
problème du 2|RO|L-VRP de manière exacte, à l'aide d'une
procédure de séparation et coupe (Branch & Cut). Leur
algorithme est basé sur une formulation de type problème de flot,
avec une procédure de séparation additionnelle, afin de
vérifier la réalisabilité des routes par rapport aux
contraintes de chargement. Cette vérification de chargement est
réalisée à l'aide de calculs de bornes inférieures,
une heuristique de placement des objets, ainsi qu'un algorithme de type Branch
& Bound, dans lequel l'arbre de recherche suit les principes
proposés par Martello et Vigo (1998) et Martello et al. (2000).
L'approche qu'ils ont proposée a permis de résoudre optimalement
toutes les instances du 2|RO|L-VRP, avec un nombre de clients allant
jusqu'à 25 et un nombre d'objets allant jusqu'à 91 (chaque client
pouvant avoir plusieurs objets), en limitant les temps de calcul à une
journée par instance.
Gendreau et al. (2008) ont proposé un
algorithme permettant de résoudre aussi bien le cas 2|RO|L que le cas
2|UO|L, basé sur une recherche tabou, qui est une adaptation de
l'algorithme Taburoute (voir (Gendreau et al., 1994) pour plus de
détails sur cet algorithme). Dans leur algorithme, les routes
irréalisables, que ce soit à cause d'un dépassement de
capacité ou d'un chargement trop important en terme de surface, sont
acceptées mais avec une pénalité ajoutée dans la
fonction objectif. Le voisinage utilisé
par la recherche tabou consiste à enlever un client
d'une tournée et à l'insérer dans une tournée d'un
autre véhicule, en optimisant les deux routes concernées par le
mouvement. La vérification de réalisabilité du chargement
a lieu au moyen de bornes inférieures, d'algorithmes heuristiques,
d'opérateurs de recherche locale et d'une recherche arborescente
tronquée. La méthode proposée a été
testée sur des instances comprenant jusqu'à 255 clients et 768
objets.
Fuellerer et al. (2008) ont proposé une
méthode heuristique efficace basée sur un algorithme
d'optimisation par Colonie de Fourmis. Leur point de départ est
l'algorithme Saving based ACO développé pour le CVRP
(voir (Reimann et al., 2004) pour plus de détails sur cet
algorithme). Cet algorithme est modifié et étendu afin
d'intégrer les heuristiques de chargement. L'algorithme cherche dans
l'espace des solutions de tournées, tout en vérifiant la
réalisabilité du chargement en deux dimensions de chaque route au
moyen de calculs de bornes inférieures, d'algorithmes heuristiques et de
recherches arborescentes tronquées. Leur but était de fournir de
bonnes solutions pour des instances de grandes tailles.
La littérature portant sur les problèmes de
tournées de véhicule et les problèmes de chargement pris
séparement est conséquente. En ce qui concerne le Capacited
Vehicle Routing Problem, le lecteur intéressé peut lire l'ouvrage
récent consacré à ce sujet par Toth et Vigo (2002), ainsi
que les travaux de Cordeau et Laporte (2004) et Cordeau et al.
(2005).
Pour le cas du chargement multi-dimensionnel, nous conseillons au
lecteur de lire les récents travaux de Wäscher et al.
(2007).
| 
