Study on the TDCVRP
Auteurs:
 |
Maxime Chassaing |
Laboratoire : LIMOS, UMR CNRS 6158 Campus des Cézeaux 63177 Aubière Cedex (France) |
 |
Christophe Duhamel |
|
 |
Philippe Lacomme |
Introduction :
Avec le développement des applications de guidage par GPS, il est de plus en plus facile d’obtenir des informations précises sur les conditions de circulation à différents moments de la journée et ce partout sur la planète. Ces nouvelles données peuvent être prises en compte dans les problèmes de tournées de véhicules classiques.
TDCVRP : Time Dependent Capacitated Vehicle Routing Problem
Dans ce problème au lieu du nombre de km parcourus, la solution recherchée
est celle qui minimise deux valeurs différentes qui sont : le temps de trajet total et le temps de conduite
des véhicules.
La distinction entre ces deux durées vient
du fait que les véhicules peuvent être autorisés à attendre sur des sommets des moments
plus propices pour emprunter un arc. Ces attentes peuvent être réalisées
à la fois sur les sommets clients mais aussi sur des sommets
intermédiaires représentés par des carrés dans la Figure 2.
Ces sommets intermédiaires constituent la première différence
avec les instances classiques du TDCVRP.
Figure 1 : Instance classique du TDCVRP.
Figure 2 : Instance du TDCVRP avec sommets intermédiaires.
Fluctuation de la vitesse au court du temps
La journée de travail est découpée en plusieurs périodes.
Chaque arc du graphe possède une valeur pour chaque période.
Ces valeurs représentent les différentes vitesses du véhicule
lorsqu'il emprunte l'arc.
La contrainte FIFO implique qu'un véhicule qui emprunte un arc ne peut pas arriver plus tôt qu'un autre véhicule enpruntant le même arcs et dont le départ aurait précédé le sien.
Pour respecter cette contrainte la fonction proposée par Ichoua,
Gendreau et Potvin [1] a été utilisée.
[1] S. Ichoua, M. Gendreau, J.-Y. Potvin. Vehicle dispatching with time-dependent travel time. European Journal of Operational Research, 144:379-396, 2003.
Fluctuation dans les plus courts chemins et fluctuation dans les solutions
Dans les instances comportant des sommets intermédiaires, pour voyager d'un client
à un autre, le véhicule doit emprunter un ensemble de sommets intermédiaires.
Et comme les temps de trajet sur les arcs évoluent, même si le véhicule
n'est pas autorisé à attendre, les plus courts chemins entre les clients
vont évoluer.
Si l'attente n'est pas autorisé alors, il existe pour chaque heure de départ possible un unique plus court chemin qui pourrait être pré-calculé. Mais lorsque le véhicule peut attendre sur les sommets intermédiaires,
nous obtenons, non plus un unique plus court chemin, mais un ensemble qui sont incomparables. C'est pourquoi le pré-calule est alors plus difficile voire impossible.
Figure 4 : Plus court chemin entre 2 et 39 départ à t = 0.
Figure 5 : Plus court chemin entre 2 et 39 départ à t = 660.
Conséquence les tournées au temps de trajet minimum (sans autoriser l'attente), c'est à dire l'ordre de ramassage des clients eux même des véhicules, vont eux aussi évoluer en fonction des différentes périodes de la journée.
Figure 6 : Evolution de la tournée qui minimise le temps de trajet pour les différentes périodes (sans attente).
Autoriser le véhicule à attendre
On sait que si le véhicule est autorisé à attendre durant sa tournée pour emprunter un arc à une période plus favorable alors le temps total de la tournée va augmenter mais son temps de conduite va diminuer (contrainte FIFO).
L’objectif est de mettre en évidence que prendre en compte
cette possibilité permettrait d’améliorer la qualité du service proposé à plusieurs niveaux notamment:
- en réduisant la consommation de carburant
- en participant à l'amélioration de la fluctuation sur l'ensemble du réseau
- en diminuant le temps de conduite du chauffeur dans les bouchons (qui sont des périodes stressantes)
- en permettant de respecter les différentes règles sur la limitation du temps de conduite
C'est pourquoi une distinction est faite entre temps d'attente et temps de conduite.
Avec l'attente autorisée, il est donc nécessaire de traiter le problème comme un problème bi-critère.
Le premier est le temps de conduite et le deuxième représente le temps totale de trajet c'est à dire le temps de conduite plus le temps d'attente.
Il n'existe donc pas une solution optimale mais un ensemble de solutions incomparables situées sur un front de Pareto.
La solution la plus à droite du front représente la solution où le chauffeur n'a pas fait de pause. Son temps de trajet est alors minimum égale à son temps de conduite. Et la solution la plus à gauche représente la solution qui a un temps de conduite minimum mais un temps d'attente élevé
Figure 7 : Front de Pareto des solutions incomparables.
