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

Adaptation de la méthode GRASP le Problème de
Tournées de Véhicules avec Fenêtres du Temps

Moncef BOURGU1BA

LAB. MQ Ins. Sup. de Gestion. Gabès 6000 Tunisie

Mots-clefs : Tournées de véhicules, coûts d'insertion, Métaheuristiques, GRASP, Recherche locale.

1 Introduction

Le Problème de Tournées de Véhicules avec fenêtres du temps (PTVFT): un problème d'optimisation combinatoire assez répandu vu les différentes contraintes qui les définissent. La réduction des coûts correspondants est l'une des grandes préoccupations des décideurs intéressés, ce qui fait de ce domaine un champ très fertile pour diverses recherches.

La complexité des tels problèmes montre généralement qu'il n'est efficace d'utiliser les méthodes exactes pour sa résolution, compte tenu des temps des calculs exigés et d'absence de la flexibilité suffisante pour l'intégration des diverses contraintes spécifiques. Les méthodes approchées; heuristiques et métaheuristiques ; constituent ainsi un processus de résolution qui devient de plus en plus distinct. Les méthodes approchées sont donc indispensables pour l'obtention d'une bonne solution en un temps du calcul raisonnable.

Dans ce travail nous décrivons une approche basée sur la méthode GRASP « Greedy Randomized Adaptive Search Procedure » pour la résolution du problème de tournées de véhicules avec contraintes de fenêtres du temps. Ce problème est présenté sous forme d'un ensemble de listes de visites de clients dont chacune correspond à un itinéraire simple de véhicules. A chaque véhicule est associé une capacité, qui doit être toujours supérieure ou égale à la somme des charges de ses livraisons.

Le principe de la méthode GRASP fait créer une première solution pendant une phase dite de construction, puis passe à la phase d'amélioration de la solution obtenue en faisant recours à la méthode de recherche locale.

2 Notations

Soit 1 = {1,..., n} l'ensemble de clients à servir ; le dépôt est indexé par 0 et 10 = 1 U {0} . Pour chaque client i, correspond une requête qi et une fenêtre du temps [ai ; bi; : ai (respectivement bi) est le premier (respectivement dernier) instant auquel le service du client i peut commencer. Le temps nécessaire du déplacement entre les clients i et j E 10 est dénoté par _t'ij. Le temps du départ du véhicule à partir du client i est dénoté par ti. Si un véhicule arrive chez un client avant le délai du service autorisé (fenêtre du temps), il doit attendre jusqu'à ce que la fenêtre du temps soit ouverte. Nous supposons également que les véhicules roulent avec une vitesse moyenne égale à V bien déterminée; Soit dij la distance entre deux clients i et j. On peut donc aisément déterminer le temps du trajet proportionnellement à la distance, soit :

tij= dij / V (1)

On suppose également que les clients et le dépôt sont situés sur un plan, et que les distances entre les points sont de type euclidien. Ceci implique que l'inégalité triangulaire est vérifié pour trois points quelconques. Tous les véhicules sont supposés d'une capacité égale désignée par Q. Nous dénotons aussi par Pi (respectivement Si) l'ensemble de clients précédents (respectivement successeurs) dans le même tour du client i. Le prédécesseur immédiat de i est dénoté par pi de même le client qui vient juste après i est noté si.

Pour chaque route la capacité restante est donnée par :

Q = Q

E q ie Pi

i

(2)

Dès le début on doit qu'un client ne peut être servi que si toi bi. La fenêtre du temps du dépôt est notée [a0 ; b0; et le temps du service pour tous les clients est une constante z # 0. Donc l'équation suivante et introduite :

tij = tij + z (3)

Pour la notation relative aux plages horaires et afin de faciliter les calculs horaires on considère comme si un chronomètre qui se déclanche au moment du commencement des services : si le chronomètre est mis à zéro à huit heure du matin (cette heure sera notée 0) ; et la notation horaire change donc en continue : par exemple 8H : 45min. sera notée 45 et 9H : 15 devient 75 ; le calcul du temps sera donc plus aisé.

L'équation (3) permet donc d'ignorer puis qu'il va être introduit dans la durée du parcours. De plus nous supposons que l'intervalle temporel du dépôt est si large qu'il n'impose aucune contrainte c'est à dire que le dépôt est disponible toute la journée. Afin de préserver la possibilité de réalisation du circuit, nous définissons la variable ti comme moment d'arriver chez le client i, l'instant ti varie entre ai et bi selon l'itinéraire pris en considération. Pour cette raison, nous ajoutons la contrainte suivante.

ai ? i ? bi (4)

Dans une tournée donnée, on doit vérifier la possibilité d'insertion d'un nouveau client en se basant sur l'équation ci-dessus. Nous ajoutons également les conditions des équations (5) et (6) comme contraintes garantissant que le véhicule arrive chez le client k avant la borne limite (bk), aussi le temps du départ de chez le client k additionné avec le temps de déplacement du client k au client j doit être inférieur ou égal au dernier délai (bj) pour que ce client j puisse être servi, c'est à dire :

(5)

(6)

ti+ tik bk

Sup{ _ak , ti+ tik}+tkj < bj

Quant aux exigences de la capacité, un client k n'est inséré que si sa demande q k vérifie l'équation :

(7)

q_k ? Q

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.

5 Coûts d'insertion

Cette section, illustre plus de détailles pour le calcul des coûts d'insertions. Le calcul du coût d'insertion du noeud k entre i et j est une pondération des trois fonctions des coûts: un coût lié à la capacité, un coût lié à la distance (ou bien le temps), et un coût lié à l'ordre :

1 1 2 2 3 3

c ijk = W c ijk + W c ijk + W c ijk

(9)

(10)

3

Où W t : coefficient de pondération du coût cijk Avec E W t = 1

t =1

1

Le premier coût cijk = F1 (t _ik + t _kj - tij ) correspond à la variation du temps suite à l'insertion du

2

k entre i et j cijk = F2 (qk) coût de la variation de la charge du véhicule à l'arrivée au client j suite à

3

)l'insertion du client k. Le troisième cijk =F3(t. - t J y J ._c est la variation du temps d'arrivée

J

au point j après avoir inséré k, où tj = Sup (tk + _tkj, aj) est le nouveau temps d'arrivée au point j, telle
que tk = Sup (ti + tik, ak) et yj est une variable binaire qui vaut 1 si le véhicule arrive en retard en j 0 sinon et c
une pénalité de retard ( si le retard n'est pas pris en considération il suffit donner à yi ou bien c une valeur
nulle)

cvk Le coût d'insertion du client k dans une position précise de la route v. c_vk = 1nf {cijk }

(i,j)E v

cv*k Le coût optimal d'insertion du client k dans la meilleure route donc la route est à repérer cv*k = 1nf {cvk}

v E V

6 Amélioration

Les solutions réalisables obtenues à la fin de l'étape de construction ne sont bien évidemment optimales. L'application d'une méthode de recherche du voisinage permet souvent de les améliorer. Cette méthode démarre à partir d'une solution réalisable qui est successivement remplacée par une meilleure solution appartenant à son voisinage. Un voisinage V associe à chaque solution un sous-ensemble V(S) de solutions. La solution S est un optimum local par rapport au voisinage V(S) s'il n'existe pas de solution strictement meilleure que S dans V(S). L'itération s'arrête lorsqu'un optimum local est atteint, c'est à dire, lorsque toutes les solutions voisines de la solution courante lui sont de qualité inférieure.

La clef du succès pour un algorithme de recherche locale consiste dans le choix convenable de la structure du voisinage, et aussi la solution du démarrage. En outre des méthodes classiques d'amélioration à savoir le recuit simulé, la recherche taboue, la méthode de descente, la méthode VNS...

Méthode d'éjection des chaînes

Ce processus permet de réduire le nombre des routes pour le VRPTW. 1l suffit d'utiliser un nouveau type de la structure du voisinage : échanger quelques clients (arcs successifs) d'une route donnée par d'autres clients d'une autre route distincte sans violer les contraintes du capacité ou bien d'intervalles du temps.

Méthode du transfert des chaînes.

Cette méthode consiste à choisir une succession des arcs pour les échanger d'une route à une autre tout en respectant les contraintes de précédences entre les clients ; une telle procédure est appliquée sauf si elle réduit la distance totale. Le choix de la chaîne à déplacer est guidé par des critères prédéfinis pour éviter les déplacements indésirables. Cependant on peut ne pas changer la route mais juste modifier l'ordre des chaînes.

Méthode du choix par villes

Durant cette méthode, on sélectionne une ville pour la permuter avec une autre afin de réduire la distance parcourue ou bien permettre l'insertion d'autres clients sans construire des sous tours.. 1l est à noter que la permutation des clients peut se faire dans une même route comme entre les routes on parle donc d'échange interne et d'échange externe. Cette dernière méthode est celle adoptée pour notre étude, vu son efficacité et son exécution simple

Soit Z*ipv coût total optimal de la réalisation si le client i est dans la position p dans une route v; aucune permutation n'est acceptée sauf si elle va améliorer le coût optimal de la solution finale

Si Ziqu < Z* ipv alors introduire le client j dans la position q de la route v. Lorsque u = v alors on parle d'un changement intra route alors que pour le cas où i = j et u # v il s'agit d'un changement du même client dans d'une route vers une autre. Si i # j et u # v alors il s'agit d'un échange de deux clients de routes différentes.

Algorithme 3 ~

Début

Une fois tous les clients sont affectés

Pour i = 1...n ; j= 1...n ; V p et V q

Soit Dij = Z^* ipv Z^*jqu

Tant que Dij > 0 introduire j dans la position q. Mettre à jours cijk .

Si Dij très faible arrêter le processus. Fin tant que

Fin

Pendant la permutation la formulation du coût d'insertion prend en considération les changements possibles quant à la charge et aussi les distances parcourues ce qui permet de vérifier la proximité entre les routes puisqu'un échange entre deux routes éloignées va engendrer un coût élevé qui bloquer la permutation.

i

i

u

u

0

Dépôt

0

Dépôt

v

v

Figure 1 : Procédure d'Amélioration

La discrimination des principes des méthodes de construction ainsi que ceux d'amélioration laisse les horizons ouverts pour plusieurs possibilités d'hybridation vu que la problématique commence à avoir autres extensions par l'introduction des nouvelles exigences.

Pour notre cas et afin de tester ses performances ; la méthode GRASP a été appliquée à quelques exemples de tailles différentes. L'objectif été la minimisation de la distance totale parcourue par l'ensemble des véhicules. Les résultats sont résumés ci-dessous.

Problèmes	Données		Solutions
	I	V	D*	V*	Z*
Exemple 1	10	5	67.9	3	136.25
Exemple 2	12	3	83.2	3	419.65
Problème 1	22	9	314.65	6	734.45
Problème2	145	15	2193.56	16	50 31.75

T1 Tableau récapitulatif des résultats

En plus de la minimisation du temps de la tournée totale D* la méthode permet aussi, et à travers son processus d'amélioration, de réduire le nombre V* de véhicules utilisés ce qui revient à réduire le coût total Z* ; parfois il s'agit de chercher un compromis entre la réduction du nombre de véhicules utilisés et la distance totale parcourue.

7 Conclusion

Dans notre travail on a introduit un concept qui simplifie le calcul du temps du passage entre deux clients par l'ajout de la notion de vitesse, aussi l'introduction du temps du service dans le temps de roulement. Pendant la construction des listes de clients à affecter, le processus introduit un principe qui permet de distinguer les points les plus distants et ceux les plus urgents, en termes du dernier temps du service, Au niveau de la phase de construction, la méthode adoptée vise à affecter deux clients voisins dans deux véhicules différents afin de réduire la distance parcourue. Pour la phase d'amélioration, on choisit un processus assez simple et qui traite toutes les permutations possibles.

Vu sa simplicité et son aspect adaptative, la méthode GRASP peut être aisément adoptée pour plusieurs extensions de la problématique et toucher au cas de dépôts multiples avec des légères modifications ; aussi pour le problème de transport civil la qualité du service à fournir est primordiale donc la minimisation du nombre des véhicules devient un objectif auxiliaire. Pour le cas du problème de chargement et de déchargement, une simple modification permet l'adaptation de cette méthode pour les exigences de la situation.

Références

[ 1 ]- C. Rebeiro «La métaheuristique GRASP » Université Catholique de département d'informatique RJ 22453-990 Rio de Janeiro Brésil.

[ 2 ]- C. Rebeiro «Heuristiques et métaheuristiques » Rapport 1S1MA Clermont-Ferrand, France 2002.

[ 3 ]- Chabrier, E. Danna et C.Lepape. « Coopération entre génération de colonnes avec tournées sans cycle et recherche locale appliquée au routage de véhicules » Acte JNPC'02.

[ 4 ]- Dimitris et D.Sichi-Levi «A new generation of vehicle routing research: robust algorithms, addressing uncertainty» Research By ONR December 1993.

[ 5 ]- Duhamel « Un Cadre Formel pour les Méthodes par Amélioration Itérative - Application à deux problèmes d'Optimisation dans les Réseaux » Ecole Doctorale des Sciences pour l'1ngénieur de Clermont-Ferrand, France Mars 2001.

[ 6 ]- É. Taillard «Principes d'implémentation des métaheuristiques » Métaheuristiques et outils nouveaux en R. O.

[ 7 ]- G. Kontoravdis G. et J. Bard «A GRASP for the VRPTW» ORSA Journal on Computing V 7 No 1 Winter 1995

[ 8 ]- J. Berger B. et M. Barkaoui «An improved hybrid genetic algorithm for the vehicle routing problem with time windows » Defence Research Establishment Valcartier, Decision Support Technology Section Val-Bélair, PQ, Canada.

[ 9 ]- J. Bramel. et D.Sichi-Levi. «Probabilistic Analysises and Practical Algorithms for the Vehicle Routing with Time Windows» Research supported in part by ONR et NSF July 1993.

[ 10 ]- Le Bouthelier «Modélisation UML pour une architecture coopérative appliquée au problème de tournées de véhicules avec fenêtres de temps » Département d'informatique et de recherche opérationnelle Faculté des arts et des sciences Université de Montréal (2000)

[ 1 1 ] - M. Baker Barrie, A.C. Carreto Carlos «A visual interactive approach to vehicle routing» Computers & Operations Research 30. 321-337 (2003).

[ 12 ]- M. G. C. Resende « Combinatorial Optimisation in Telecommunications » AT et T Labs Research technical Report: 01.15.3. July 2001.

[ 13 ]- M. G. C. Resende et C. C. Rebeiro . « Greedy randomized adaptive search procedures » AT et T Labs Research. Technical Report , Florham Park, NJ 07932 USA,August 2002.

[ 14 ]- M. G.C. Resende « Greedy Randomized Adaptive Search Procedures » AT et T Labs Research Technical Report: 98.41.1. Décembre 1998.

[ 15 ]- M. G.C. Resende et J. V. Luis Gonzalez « Greedy randomized adaptive search procedures ». 1nteligencia Artificial, Revista 1beroamericana de 1nteligencia Artificial. No.19 (2003).

[ 16 ]- M. Swihart, J. Papastavrou «A stochastic and dynamic model for the single-vehicle pick-up and delivery problem » European Journal of Operational Research 114 (1999) 447- 464.

[ 17 ]- M.Gendreau, Laporte G. et D. Yigo «Heuristics for the travelling salesman problem with pickup and delivery » Computers et Operations Research, 26 (1999) 699 -- ] 714.

[ 18 ]- P. Hansen et C. Ribeiro «Essays and Surveys in Metaheuristics » Operations Research / Computer Science 1nterfaces 15, October 2001.

[ 19 ]- Righini «approximation algorithms for VRPPD » Dipartimento di scienze dell _1nformazione Polo Didattico e di Ricerca di Crema Milano 2000.

[ 20 ]- S. R Thangiah, S. Tong et O. H. 1brahim « Hybrid genetic algorithm, simulated annealing and tabu search methods for VRPTW» Artificial 1ntelligence and Robotics Laboratory, Computer Science Department Slippery Rock University, Slippery Rock, PA 16057, U.S.A.

[ 21 ]- Solomon, and J. Desrosiers «Time window constrained routing and scheduling problems ». Transportation Science 22 1-13. (1988)

[ 221- T. Ralphs, L. Kopman, W. Pulleyblank et L. Trotter. « On the capacitated vehicle routing problem »

Resarch Report; University of Arkansas. December 2001

[ 23 1- T. Sexton and L. Bodin «The multiple-vehicle subscriber dial-a-ride problem» Working paper MS /S 83-009, College of Business and Management, University of Maryland (1983).

[ 24 1- X. Delorme, X. Gandibleux et J. Rodriguez. «GRASP for set packing problems». à paraître EJOR

[ 25 1- X. Gandibleux, D. Vancoppenolle . et D.Tuyttens. «A first making use of GRASP for solving MOCO

problems». 14th 1nternational Conference in Multiple Criteria Decision-Making, June 8-12, 1998.