Problèmes «

riches

»

de tournées de véhicules

Michel GendreauCIRRELT et DIRO, Université de Montréal

Journée scientifique de la Chaire de recherche industrielle du CRSNG en management logistique5 décembre 2007 −

ESG-UQÀM

Chaire industrielle de management logistique 5 décembre 2007 2

Plan

La notion de problème « riche » en tournées de véhiculesQuelques travaux antérieursLe projet CRSNG-RDC de la ChaireAutres activités de la chaire dans le domainePerspectives

Chaire industrielle de management logistique 5 décembre 2007 3

Le PTV classique

On dispose d’une flotte de véhicules homogènes de capacité donnée basée à un dépôt.On veut livrer un bien homogène à un ensemble de clients qui ont des demandes connues.Il faut trouver un ensemble de tournées àmoindre coût permettant de livrer les quantités demandées aux clients et telles que:

chaque tournée part et revient au dépôt;chaque client est desservi par un seul véhicule;les quantités livrées par un véhicule respectent les contraintes de capacité des véhicules.

Chaire industrielle de management logistique 5 décembre 2007 4

Les variantes traditionnelles

Contraintes de longueur sur les tournées.Fenêtres de temps.Tournées sur les arcs, plutôt que les sommets

Postier chinoisPostier ruralCapacitated Arc Routing Problem

Chaire industrielle de management logistique 5 décembre 2007 5

Les PTV «

riches

»

Les problèmes classiques de tournées de véhicules correspondent à des versions épurées (abstraites) des problèmes réels.

Les problèmes de la pratique impliquent presque toujours des éléments « complicants ».

Ceci a amené une réflexion dans la communauté de recherche en PTV.

Chaire industrielle de management logistique 5 décembre 2007 6

Travaux antérieurs

Des ateliers, sessions et autres manifestations.

Deux articles par Braÿsy, Gendreau, Hasle et Lokketangen font un survol des heuristiques pour les problèmes complexes de PTV:

extensions sur le plan de l’offre,extensions sur le plan de la demande.

Chaire industrielle de management logistique 5 décembre 2007 7

Extensions sur le plan de l’offre

Flottes hétérogènes

Temps de parcours variables

Réutilisation des véhicules (plusieurs routes par jour)

Présence de dépôts multiples

Problèmes de localisation (de dépôts) -tournées.

Chaire industrielle de management logistique 5 décembre 2007 8

Extensions sur le plan de la demande

Problèmes avec retours (« backhauls »)

Problèmes avec ramassage et livraison

Livraisons partielles

Problèmes périodiques (sur plusieurs « jours »)

Problèmes de tournées avec inventaires

Problèmes dynamiques et stochastiques

Chaire industrielle de management logistique 5 décembre 2007 9

Le projet CRSNG-RDC de la Chaire

Un projet amorcé pour faire face aux problèmes rencontrés dans la pratique par

la Fédération des Producteurs de Lait du Québec(FPLQ),Couche-Tard.

En collaboration avec Omega Optimisation.

Chaire industrielle de management logistique 5 décembre 2007 10

Protagonistes

Chercheurs universitaires:Teodor Gabriel CrainicMichel GendreauBernard GendronWalter Rei

Omega Optimisation:Alexandre Le BouthillierLouis-Martin Rousseau

Chaire industrielle de management logistique 5 décembre 2007 11

Protagonistes (suite)

Trois post-docsNicolas Jozefoview……

Deux étudiants de Ph.D.Iman DayarianAlireza Rahimi Vahed

Deux étudiants de maîtrise

Chaire industrielle de management logistique 5 décembre 2007 12

Les problèmes

Fédération des Producteurs de Lait du QuébecRoutes faites sur une base semestrielle, alors qu’il y a de fortes variations de la demande (éléments stochastiques).Fonction de coût extrêmement complexe avec des éléments non linéaires.Dépôts et usines « multiples ».Flotte hétérogène.Restrictions d’accès au réseau routier.Vitesse variable.

Chaire industrielle de management logistique 5 décembre 2007 13

Les problèmes

Couche TardContraintes sur le chargement des véhicules et interaction avec les tournées permises.Contraintes de capacité « particulières »Dépôts et usines « multiples ».Flotte hétérogène.Restrictions d’accès des véhicules chez les clients.…

Chaire industrielle de management logistique 5 décembre 2007 14

Approche de résolution

Adaptation/mise à jour d’heuristiques existantes pour traiter les problèmes classiques de PTV.

Extension de ces heuristiques pour prendre en compte les dimensions « riches ».

Intégration dans une approche coopérative « multi-fils ».

Expérimentation poussée sur des données fournies par les partenaires industriels.

Chaire industrielle de management logistique 5 décembre 2007 15

Autres travaux

Confection de tournées dans le contexte de la logistique urbaine:

PTV synchronisées

…

Chaire industrielle de management logistique 5 décembre 2007 16

Perspectives

Les PTV complexes sont un élément récurrent de nombreux contextes pratiques de distribution.Négliger les éléments complexes de ces PTV mène à des solutions de peu d’utilité pour les vraies applications pratiques.Les PTV complexes devraient constituer un élément central de la programmation d’une chaire en management logistique.