Journée du GT Transport et Logistique et du Projet France-Québec Tournées à Hautes Technologies

Angers 14/10/2010


 

Programme définitif: sommaire

 

09h30 – 10h00

Café d'accueil

10h00 – 11h00

Les problèmes stochastiques de tournées de véhicules : un état de l'art.

Michel Gendreau, CIRRELT et Département de mathématiques et de génie industriel, École Polytechnique de Montréal.

11h05 – 11h35

Un modèle pour la logistique urbaine.

Olivier Guyon, École des Mines de Saint-Etienne / CMP.

11h40 – 12h10

Le point sur les approches "route first - cluster second" pour les problèmes de tournées de véhicules.

Christian Prins, Université de Technologie de Troyes / LOSI.

12h20 – 13h50

Déjeuner

14h00 – 14h10

Présentation du projet  France-Québec tournées à hautes technologies.

Pierre Dejax, École des Mines de Nantes / IRCCyN

André Langevin, CIRRELT et Département de mathématiques et de génie industriel, École Polytechnique de Montréal.

14h10 – 14h40

Une approche exacte pour le problème du  « Close Enough Traveling Salesman » avec contraintes de couverture sur les arcs. 

Hoang Ha, École des Mines de Nantes / IRCCyN

14h40 – 15h10

 

La ré-optimisation des tournées de techniciens dans un environnement dynamique avec des temps de service stochastiques.

Erwann Delage, École des Mines de Nantes / IRCCyN

15h10 -15h40

La réoptimisation des tournées de techniciens dans un environnement dynamique avec des temps de déplacement  stochastiques.

Sixtine Binart, École Centrale de Lille / LAGIS.

15h40 – 16h00

Pause café

16h00 – 16h30

Une recherche à voisinages larges pour le problème de collectes et livraisons avec transferts.

Renaud Masson, École des Mines de Nantes / IRCCyN.

16h30 – 17h00

Discussion GT-TL

 

retour

 

Les problèmes stochastiques de tournées de véhicules : un état de l'art

M. Gendreau*

*CIRRELT et Département de mathématiques et de génie industriel, École Polytechnique de Montréal

 

Bien que les problèmes de tournées de véhicules aient fait l’objet de nombreuses recherches au cours des 50 dernières années, ceux dans lesquels certains paramètres demeurent incertains n’ont reçu que peu d’attention, malgré le fait qu’il y ait beaucoup de contextes  d’applications dans lesquels certains paramètres-clés ne sont pas connus avec certitude. Dans cet exposé, nous présenterons tout d’abord un survol général des problèmes stochastiques de tournées de véhicules (PSTV) et des modèles et méthodes de résolution pertinents pour leur étude, puis nous discuterons plus en détail les trois principales classes de PSTV à ce jour : les problèmes de tournées avec demandes stochastiques, les problèmes de tournées avec clients stochastiques et les problèmes de tournées avec temps de parcours ou de service stochastiques.

 

 

Un modèle pour la logistique urbaine

O. Guyon*, N. Absi*, D. Boudouin, D. Feillet*,

*École des Mines de Saint-Etienne  / CMP

Jonction – CRET-LOG

 

Notre étude, conduite dans le cadre du projet PLUME (projet financé par le Programme de Recherche Et d'Innovation dans le Transport), se propose d'évaluer l'intérêt de la mise en œuvre de systèmes de distribution urbaine à partir d'Espaces Logistiques Urbains  dédiés à la logistique urbaine (city logistics). Nous visons à définir d'un point de vue organisationnel et fonctionnel les atouts économiques, environnementaux et sociétaux de ces systèmes; le but étant de fournir un cadre méthodologique pour guider leur mise en place dans toute agglomération. Un premier terrain d'analyse pour notre étude sera la ville de Marseille qui possède la particularité de disposer d'une Zone Logistique Urbaine en cœur de centre-ville avec la plate-forme logistique d'ARENC (41362m² d'entrepôts et de bureaux). 

 

Durant notre présentation au GT Transport, nous détaillerons la problématique et exposerons les caractéristiques de différents Espaces Logistiques Urbains. Nous formulerons ensuite le modèle mathématique utilisé, puis listerons les prolongements à court terme de nos travaux.

 

Le point sur les approches "route first - cluster second" pour les problèmes de tournées de véhicules

C. Prins*

*Université de Technologie de Troyes / LOSI

 

Les heuristiques de type "cluster-first / route-second" consistent à définir pour chaque véhicule un paquet de clients, pour lequel est résolu ensuite un problème de voyageur de commerce. Certaines comme celles de Gillett et Miller ou Fisher et Jaikumar sont bien connues. Les méthodes de type "route-first / cluster-second" relaxent d'abord la contrainte de capacité pour calculer un cycle unique passant par tous les clients, puis découpent ce cycle en tournées réalisables. Peu utilisées par rapport au premier type, on leur a longtemps prêté des performances médiocres. Les développements réalisés depuis 10 ans montrent que ces approches peuvent être très compétitives, voire même obtenir les meilleurs résultats connus sur divers problèmes de tournées. L'exposé fera un point sur les résultats obtenus et les limites de ces approches.

 

 

Une approche exacte pour le problème du  « Close Enough Traveling Salesman » avec contraintes de couverture sur les arcs

H. Ha*, N. Bostel,  A. Langevin, L-M. Rousseau

*École des Mines de Nantes / IRCCyN

IUT de Saint-Nazaire / IRCCyN

CIRRELT et Département de mathématiques et de génie industriel, École Polytechnique de Montréal

 

Nous adressons le problème de tournées de relevés de compteurs d’énergie (eau, gaz, électricité…), dans lequel les compteurs sont équipés de puces RFID (Radio Frequency Identification)  permettant de communiquer à distance, dans un certain rayon , les informations nécessaires (quantité consommée…). Il suffit alors au technicien de parcourir un sous-ensemble d’arcs couvrant les clients, sans s’arrêter, pour relever les consommations. Ce problème a été identifié comme  le problème du voyageur de commerce suffisamment proche (« Close Enough Traveling Salesman ») avec contraintes de couverture sur les arcs. Ce problème est proche du « covering tour problem » (Gendreau et al. 1997) mais nécessite d’identifier les arcs à parcourir de façon à couvrir l’ensemble des clients.

 

Nous proposons une formulation mathématique pour ce problème et un algorithme pour sa résolution exacte. Enfin nous analysons les résultats des expérimentations numériques réalisées sur 320 instances.

 

 

La ré-optimisation des tournées de techniciens dans un environnement dynamique avec des temps de service stochastiques

E. Delage*, N. Bostel, P. Dejax*, M. Gendreau

*École des Mines de Nantes / IRCCyN

IUT de Saint-Nazaire / IRCCyN

CIRRELT et Département de mathématiques et de génie industriel, École Polytechnique de Montréal

 

Nous nous intéressons au problème de tournées de techniciens sur le terrain, qui est proche du multi-dépots VRPTW sans contrainte de capacité. Les tournées établies a priori sont souvent soumises à des aléas au cours de leur réalisation (aléas sur le temps de service ou le temps de transport). Grâce aux possibilités offertes par les nouvelles technologies (suivi en temps réel des véhicules), il est possible de mettre à jour en temps réel l’état d’avancement des opérations et de pouvoir adapter les tournées du reste de la journée pour modifier les visites clients prévues et insérer de nouvelles demandes ou s’adapter aux aléas. Après avoir présenté un état de l’art sur les tournées réactives, nous proposons deux méthodes permettant de traiter la réoptimisation des tournées de techniciens avec temps de service stochastiques. La première est une procédure temps réel utilisant la recherche tabou et la programmation stochastique avec recours. La seconde est une méthode basée sur la programmation dynamique.

 

 

La réoptimisation des tournées de techniciens dans un environnement dynamique avec des temps de déplacement  stochastiques

S. Binart*, F. Semet*,, M. Gendreau

*École Centrale de Lille / LAGIS

CIRRELT et Département de mathématiques et de génie industriel, École Polytechnique de Montréal

 

Nous nous intéressons à un problème de tournées de techniciens de type VRPTW dans un contexte dynamique, sans contrainte de capacité. Il s’agit de tournées de techniciens qui vont effectuer des services chez les clients. Ils doivent, d’une part, effectuer des opérations de contrôle (de type relevé de compteurs) planifiées a priori chez des clients non urgents. Ils doivent également intervenir suite à des pannes chez des clients urgents. Face à cette apparition de nouveaux clients et du fait de l’aléa sur les temps de trajet, les tournées seront réoptimisées au cours du temps.

 

Nous ferons d’abord un bref état de l’art à ce sujet. Puis nous proposerons deux méthodes pour modéliser ce problème ainsi qu’une méthode de résolution pour finalement comparer les résultats avec ceux de la littérature.

 

 

Une recherche à voisinages larges pour le problème de collectes et livraisons avec transferts

R. Masson*, F. Lehuéde*, O. Péton*

*École des Mines de Nantes / IRCCyN

 

On s'intéresse au problème de collectes et livraisons (PDP : Pickup and Delivery Problem). Des applications classiques existent dans le domaine du transport à la demande ou de la messagerie.  Nous considérons une généralisation du PDP où les biens ou les personnes transportés peuvent changer de véhicule au cours de leur trajet.  On parle alors d’un problème de collectes et livraisons avec transferts (PDPT : Pickup and Delivery Problem with Transfers).  Nous présentons une méthode heuristique dite « recherche à voisinages larges » pour résoudre le PDPT.  Une telle méthode a déjà été développée pour le PDP sans transferts. L’introduction des transferts nécessite d’adapter certains voisinages existants, et d’en créer de nouveaux.  Nous étudions l'efficacité de ces différents voisinages ainsi que l'intérêt de prendre en compte les transferts selon le type d’instances considérées.