|
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 :
(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)
qk ? Q
| 
