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 |
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.
