Adaptation de la méthode GRASP (« Greedy Randomized Adaptive Search Procedure » ). Le problème de tournées de véhicules avec fenêtres du temps

3 Formulation

La fonction objectif modélisée pour notre étude est de minimiser le coût des distances parcourues qui est en corrélation avec le nombre de véhicules utilisés ; on peut donc aisément écrire la formulation suivante :

R n n

Min

c ij Xijr

E E E

r = 1 i = 1 j = 1

				(1)
		(2)
		(3)		r
		(4)
		(5)
		(6)		V i, j
E	}V r	(7)
		(8)

Sous les contraintes :

n n

E E ₄ iQ V ^r

i 4

= =

n

E Xoir =1 V r

i1=
n

E X jor = 1 V r

=1

n n

E X ^--EX = 0 VhE1Vihr

i =1

E E _Ljr = l V i

r j

aitibi Vi E 1

tj ti + t'ij -- (1-- X ijr) M

X ijr E { 0 , 4 }

j

j

Où _Xijv est une variable binaire qui vaut 1 si le véhicule v parcourt l'arrête (i, j) et 0 sinon. _cij est le coût du parcours de l'arête (i, j), le moment d'arrivée chez le client i est noté par ti c'est aussi l'instant du début du service et M est une variable aussi grand que l'on veut.

Les contraintes (1) garantissent le respect de la charge du véhicule; les contraintes (2), (3) assurent que tous les véhicules partent et retournent au dépôt; les contraintes (4) imposent que le même véhicule arrive et parte de chaque point visité; chaque client doit être affecté à un et un seul véhicule (contrainte (5)) ; les contraintes (6) respectent le temps du service chez le client i alors que les contraintes (7) illustrent que le véhicule ne peut pas fournir son service auprès du client j avant d'y arriver.

.

4 Construction

1l est préférable de commencer la phase de la recherche locale par une bonne solution vu que ceci améliore la qualité du processus d'amélioration et mènera à une durée d'exécution plus courte. En outre, on suppose que les clients voisins géographiquement seront affectés dans un même itinéraire et que les clients lointains et qui sont situés dans des sites opposés par rapport au dépôt, ont une très faible chance d'être dans le même véhicule.

Tout d'abord on commence par affecter un unique client pour chaque véhicule ; le choix est guidé par des la notion de la distance et de la flexibilité ; une fois terminer l'affectation on insère ensuite le reste des clients selon les exigences des contraintes.

On traduire les étapes dans l'algorithme suivant.

Algorithme 1 ~

Début

G = 0

1. a. Arranger les clients dans l'ordre toi décroissant dans une liste L.

b. Réarranger dans F les (I-V) derniers clients de L selon (bi/toi) croissant.

2. Choisir un client parmi les trois premiers dans L et l'affecter à nouveau véhicule. Tant que IGI<V alors ~

3. a- Choisir un client f parmi les trois premiers dans F.

b- Choisir un client l parmi les trois premiers dans L.

c- Le plus distant par rapport aux éléments du G sera choisi comme nouveau germe g.

4. G = G U {g}

Fin Tant que

Fin

La méthode de la sélection de premiers clients à affecter (germes) consiste en le choix du V clients les plus distants par rapport au dépôt (t_oi élevé) puis les classer dans une liste L selon t_oi décroissant (a) ; les restes seront ordonnés selon un indice calibrant la flexibilité (bi/t_oi) décroissant dans une liste F: ces clients sont caractérisé par leur souplesse ce qui facilite l'insertion des prédécesseurs. La sélection du premier client est assurée par (2).Durant l'étape (3) on choisit un nouveau germe maximisant les distances par rapport aux éléments du G pour éviter d'avoir des clients dispersés dans une même route. Puis G et L ou F (selon l'appartenance du nouveau client germe) sont mis à jour. Le but de ce processus est de réduire la possibilité de choisir deux clients germes susceptibles d'être dans le même itinéraire de la solution finale

Pendant la construction des tournées, et pour chaque client k non encore affecté, on cherche tout d'abord la meilleure position d'insertion dans chaque itinéraire puis on choisit aléatoirement une position parmi les trois possibilités donnant le coût d'insertion minimum. Le coût d'insertion du client k entre les

clients i et j dans une solution quelconque est dénoté par cijk Avant de procéder à la phase de construction on définit :

- U ensemble des clients libres

- A ensembles des clients affectés.

Au départ A = G

Donc la phase de construction peut être traduite par :

L'algorithme 2 :

Début

Initialiser A, U , G et X

Tant que U > X Faire :

1. Calculer cijk pour chaque client encore libre.

a. Repérer les trois clients ayant cijk le plus faible

b. Choisir aléatoirement un client k et l'insérer comme prédécesseur du j. U={U\k}

A=1AUk1

2. Si l'insertion est impossible améliorer la solution construite.

3. Mettre à jours la table des coûts c ijk

Fin Tant que.

4. Si U = X alors affecter les clients libres dans les positions les moins chères.

Fin

L'utilisation de la liste restreinte de candidat (LRC), de clients non encore affectés, introduit un aspect probabiliste pour la construction des tournées luttant contre la divergence vers des situations bloqées

causées par les choix successifs des meilleurs possibilitées. La valeur de X ; taille de la liste restreinte de
candidats ; est un paramètre à déterminer avant l'exécution. Selon les résultats expérimentaux, une valeur de

X = 3 semble être la meilleure. Au fur et au mesure que 2 augmente, le nombre d'itérations requis pour l'obtention des bonnes solutions augmente aussi, ce qui est logique puisque plus la valeur 2 est grande, plus la construction de la fonction gloutonne est solide.