Techniques hybrides de recherche exacte et approchée: application à des problèmes de transport

5.4 Modèle classique du problème du 2|RO|L-VRP

Dans cette section, nous présentons le modèle du 2|RO|L-VRP. Soit G = (V, E) un graphe complet non-orienté pour lequel V est un ensemble de n + 1 noeuds, correspondant au dépôt (noeud v0) et aux clients ({v1, . . . , v_n}). E est l'ensemble des arêtes (vi, vj) entre chaque paire de noeuds et _cij est le coût associé pour (vi, vj) E V.

Un ensemble de K véhicules identiques est disponible depuis le dépôt. Chaque véhicule a une limite de capacité en poids D et une surface de chargement rectangulaire dont les dimensions sont caractérisées par une hauteur H et une largeur W. Chaque véhicule possède une seule ouverture pour le chargement et le déchargement des objets. On note A = W x H la surface totale de chargement.

À chaque client i (i = v1, . . . , v_n), on associe un ensemble de mi objets rectangulaires, dont la somme des poids est égal à di. Chaque objet a une largeur et une hauteur spécifique, notées respectivement _wil ^et _hil avec l = {1, . . . , mi}. Chaque objet est désigné

mi

par une paire d'indices (i, l). On note ai =

? wil x _hil l'aire totale des objets du client i.

l=1

n

Enfin, soit M = ? mi le nombre total d'objets.

i=1

Nous partons du principe que l'ensemble des objets d'un client peut être chargé dans un véhicule. Ainsi, pour chaque client, on suppose que di = D et qu'il existe un chargement à deux dimensions réalisable pour les mi objets dans la surface de chargement d'un seul véhicule. On suppose aussi que la demande de l'ensemble des clients peut être satisfaite en utilisant au maximum K véhicules. La livraison partagée n'est pas autorisée, c'est-à-dire que chaque client n'est servi qu'en une seule fois.

Les objets ont une orientation fixe et doivent être chargés parallèlement aux côtés de la surface de chargement. De plus, le déchargement des objets ne peut se faire que par un côté du véhicule (rear unloading). Dans notre notation, le déchargement se fait par le côté situé le plus en haut. Enfin, le chargement est dit séquentiel : lors du déchargement des objets d'un client, aucun objet appartenant à un client situé sur la suite de la tournée ne doit bloquer le déchargement des objets du client actuel. La figure 5.1 illustre la surface de chargement, ainsi que la zone de déchargement.

Nous donnons maintenant une définition plus formelle de la réalisabilité d'une route dans le problème de tournées de véhicules. On associe à une route réalisable un sous-ensemble S de clients et un ordre noté ó. ó(i) est l'ordre dans lequel chaque client

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

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

(0,0)

H

5.4. Modèle classique du problème du 2|RO|L-VRP

W

FIGURE 5.1 - Surface de chargement

i ? S est visité lors de la tournée. La condition 5.1 porte sur la contrainte de capacité des véhicules :

? di = D (5.1)

i?S

Les conditions qui suivent portent sur le chargement. Dans un souci pratique, on représente la surface de chargement selon des coordonnées cartésiennes. Le point (0,0) représente le coin situé en bas à gauche. L'axe des abscisses et l'axe des ordonnées correspondent respectivement au côté bas et au côté gauche. Le côté par lequel se fait le déchargement correspond au côté allant du point (0, H) au point (W, H). La position d'un objet (i, l) dans la surface de chargement peut être définie par deux variables xil et _yil. Ces deux variables représentent les coordonnées du coin de l'objet situé en bas à gauche. Nous avons donc les conditions suivantes :

0 = xil = W - wil et 0 = yil = H - hil ?i ? S l ? {1, . . . , mi} (5.2)

Les objets ne doivent pas se chevaucher. On a donc les contraintes suivantes :

xil + wil = xjl^{i ou} _xjl0 + wjlⁱ = xil ^ou _yil + hil = yjl' ^ou _yjl' + hjl⁰ = yil (5.3) ?i, j ? S, l ? {1, . . . , mi}, l' ? {1, . . . , mj} et (i, l) =6 (l, l')

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

Enfin, il existe des contraintes concernant le chargement séquentiel :

yil = yjl' + _hjl ^ou _xil + wjl = xjl^{0 ou} _xjl0 + wjl⁰ = xil (5.4)

?i, j ? S : ó(i) < ó(j), l ? {1, . . . , mi}, l' ? {1, . . . , mj}

En effet, tout objet appartenant à un client i doit être soit situé au-dessus, soit à droite, soit à gauche de l'ensemble objets des clients j visités après i.

Étant donné un sous-ensemble de clients S, on note ä(S) l'ensemble des arcs dont une extrémité appartient à S et l'autre extrémité appartient à V\S. ä(i) est utilisé au lieu de ä({i}). De plus, on note E(S, ó) l'ensemble des arcs empruntés par la route définie par le couple (S, ó). Enfin, étant donné un sous-ensemble de clients S, on note Ë(S) l'ensemble des séquences ó telles que (S, ó) est une route réalisable.

Posons z_e une variable binaire pour chaque e ? E qui prend la valeur 1 si un véhicule emprunte l'arête e. Iori et al. (2007) proposent le modèle suivant du 2|RO|L-VRP:

min? ceze (5.5)

e?E

s.c.q.

? z_e = 2 ?i ? V\{v0} (5.6)

e?ä(i)

? z_e = 2 × K (5.7)

e?ä(0)

? z_e = 2 × r(S) ?S ? V\{v0}, S =6 Ø (5.8)

e?ä(S)

? z_e = |S| - 1 ?S ? V\{v0} ?(S, ó) tel que ó ?/ Ë(S) (5.9)

e?E(S,ó)

z_e ? {0,1} ?e ? E\ä(v0) (5.10)

z_e ? {0,1,2} ?e ? ä(v0) (5.11)

Les contraintes 5.6 et 5.7 imposent la visite des sommets et les départs du dépôt. Les contraintes 5.8 imposent la réalisabilité du chargement (r(S) est le nombre minimum de véhicules nécessaires pour servir les clients dans l'ensemble S). Les contraintes 5.9 imposent une réalisabilité relativement au chargement séquentiel. Enfin, les contraintes 5.10 imposent aux variables associées aux arcs connectant deux clients d'être binaires. Les variables associées aux arcs connectant les clients au dépôt peuvent prendre la valeur 2 (dans le cas d'une route à client unique) 5.11.