Laboratoire de Génie Informatique et d’Automatique de l’Artois

Thèse de Xin ZHAO

Une méthode génétique pour la résolution du problème dynamique de routage de véhicules avec temps de parcours variables

Date de début : 1er octobre 2004
Mots clés : Problème de tournées de véhicules, PTV, VRPTW, PDTRP, Algorithme génétique, simulations, temps réel, temps de trajets dépendant du temps, profil de vitesse
Encadrement :

Le problème de tournées de véhicules (PTV ou VRP pour Vehicle Routing Problem) est un problème rencontré en logistique qui se situe à un niveau important : la planification opérationnelle qui concerne l’optimisation d’une flotte de véhicules. C’est un nom générique pour désigner une classe de problèmes dans laquelle un certain nombre de clients doit être visité par un certain nombre de véhicules. Les tournées de véhicules doivent être organisées de façon à équilibrer ou à optimiser un certain nombre de critères tels que la distance totale parcourue, le nombre de véhicules utilisés et les temps d’attente des clients.

Le PTV est l’un des problèmes les plus populaires et donc les plus étudiés de la communauté Recherche Opérationnelle. Il y a de nombreuses variantes de ce problème intégrant une ou plusieurs des contraintes suivantes : capacité des véhicules, fenêtres de temps pour visiter les clients, etc. Le VRP permet de modéliser de nombreux types d’applications. Les exemples peuvent concerner la conception, la reconfiguration d’un réseau de transport, ainsi que la gestion quotidienne de la collecte et de la livraison de marchandises, organisation des services de messageries ou de soins à domicile.

La majorité des études effectuées sur le VRP suppose que les données sont parfaitement connues et disponibles au moment où l’on effectue la planification des tournées. Dans la réalité, nous avons beaucoup de causes externes qui peuvent remettre en question cette hypothèse : congestions du réseau routier, pannes de véhicule, arrivées de nouveaux clients, etc.

Dans nos travaux, nous nous sommes placés dans un cadre dit dynamique c’est-à-dire que nous considérons que des informations nouvelles vont apparaître au cours du temps et influer sur la planification en cours. Les problèmes de décision en temps réel jouent un rôle de plus en plus important car les technologies de communication et d’information permettent aujourd’hui d’obtenir et de traiter rapidement l’information en temps réel. Par conséquent, nous traitons plus précisément le problème de l’élaboration dynamique de tournées de véhicules avec fenêtres de temps (DVRPTW) et le problème de la tournée du réparateur partiellement dynamique (PDTRP) où la prise en compte de nouveaux clients en cours de l’exécution des tournées est possible. De plus, dans une résolution classique de ce problème, les valeurs moyennes issues d’historiques sont généralement considérées pour déterminer le temps de trajet entre deux clients. On suppose généralement qu’elles ne sont pas sujettes à des variations stochastiques, la vitesse est considérée constante pour toute la journée.

Dans une première approche, nous considérons des profils de vitesse basés sur des temps de trajet moyens qui varient selon la période de temps (matin, midi, après midi) pour tenir compte de l’évolution du trafic routier. En fonction du type de connexion entre les deux clients, plusieurs profils peuvent être considérés. Dans une seconde approche, nous intégrons des informations trafic obtenues en temps réel pour modifier le profil de vitesse par rapport aux aléas du réseau routier (congestions, etc.). Nous adoptons un lissage exponentiel amélioré pour prévoir le temps de trajet en fonction des vitesses mesurées sur le parcours considéré.

Axes scientifiques impliqués :

Domaines d'application impliqués :

Aucun partenaire n'est associé à ces travaux.

Soutenance

Soutenance ayant eu lieu le 12/12/2008 à 14:00 Salle Prestige - FSA - Béthune

Jury :