Groupe d’études et de recherche en analyse des décisions

Problème de tournées de véhicules avec cueillettes et livraisons, fenêtres de temps et politique de dernier entré premier sorti

Marilène Cherkesly Northwestern University, Université du Québec à Montréal, Canada

Le PDPTWL consiste à trouver des routes réalisables minimisant les coûts et permettant de compléter toutes les requêtes avec une flotte de véhicules à capacité identique. Une requête est définie par un point de collecte et un point de livraison: une quantité de marchandise est transportée du point de collecte au point de livraison... Chaque point de collecte ou de livraison spécifie une plage horaire de visite pendant laquelle on peut collecter ou livrer la marchandise. Il s'agit d'une fenêtre de temps. De plus, les routes doivent respecter la politique dernier entré premier sorti (LIFO). Cette politique stipule que lorsqu'un point de cueillette est visité, la quantité chargée est mise sur le dessus d'une pile. On pourra alors visiter un point de livraison si et seulement si la marchandise à livrer est sur le dessus de la pile. Une route est dite réalisable si la charge du véhicule en tout temps ne dépasse pas sa capacité, si pour une requête on visite le point de collecte avant le point de livraison avec le même véhicule, si chaque point est visité à l'intérieur de la fenêtre de temps spécifiée et si l'ordre des points visités respecte la politique LIFO. Les coûts sont associés au nombre de véhicules utilisés et à la distance totale parcourue. En général, il est donc intéressant de minimiser le nombre de véhicules puis de minimiser la distance.

Dans ce séminaire, nous présenterons les algorithmes de l'état de l'art développés pour résoudre le PDPTW (PDPTWL sans politique LIFO). Nous présenterons également plusieurs algorithmes proposés pour résoudre le TSPPDL (PDPTWL sans fenêtres de temps et avec un seul véhicule). Nous proposerons ensuite trois méthodes pour résoudre le PDPTWL. Ces méthodes n'ont pas encore été implantées. L'objectif de ce séminaire est de pouvoir discuter des pistes de recherche envisagées.