Nos tutelles

CNRS

Nos partenaires


Accueil > Publications > Thèses

BEN TICHA Hamza


Problèmes de tournées de véhicules avec des informations du réseau routier

Lundi 20 novembre 2017 - Ecole des Mines de Saint-Etienne (campus de Gardanne)

Les problèmes de tournées de véhicules (VRPs) ont fait l’objet de plusieurs travaux de recherche depuis maintenant plus de 50 ans. La plupart des approches trouvées dans la littérature s’appuient sur un graphe complet ou un noeud est introduit pour tout point d’intérêt du réseau routier (typiquement les clients et le dépôt). Cette modélisation est, implicitement, basée sur l’hypothèse que le meilleur chemin entre toute paire de points du réseau routier est bien défini. Cependant, cette hypothèse n’est pas toujours valide dans de nombreuses situations.
Souvent, plus d’informations sont nécessaires pour modéliser et résoudre correctement le problème.

Nous commençons par examiner ces situations et définir les limites de la modélisation basée sur un graphe complet. Nous proposons un état de l’art des travaux qui examinent ces limites et qui traitent des VRPs en considérant plus d’informations issues du réseau routier.
Nous décrivons les approches alternatives proposées, à savoir la modélisation utilisant un multi-graphe et celle utilisant la résolution directe sur un graph représentant le réseau routier.
Dans une seconde étude, nous nous intéressons à l’approche basée sur la construction d’un multi-graphe. Nous proposons, d’abord, un algorithme qui permet de calculer d’une manière efficace la représentation par multi-graph du réseau routier. Puis, nous présentons une analyse empirique sur l’impact de cette modélisation sur la qualité de la solution. Pour ce faire, nous considérons le problème classique VRPTW comme un problème de pilote. Par la suite, nous développons une méthode heuristique efficace afin de résoudre le VRPTW basée sur une représentation par un multi-graphe.

Dans une troisième étape, nous nous concentrons sur l’approche basée sur la résolution directe du problème sur un graphe représentant le réseau routier. Nous développons un algorithme de type branch-and-price pour la résolution de cette variante du problème. Une étude expérimentale est, ensuite, menée afin d’évaluer l’efficacité relative des deux approches.
Enfin, nous étudions les problèmes de tournées de véhicules dans lesquels les temps de parcours varient au cours de la journée. Nous proposons un algorithme de type branch-and-price afin de résoudre le problème avec des fenêtres de temps directement sur le graphe représentant le réseau routier. Une analyse empirique sur l’impact de l’approche proposée sur la qualité de la solution est proposée.

Membres du jury :

Mme Claudia ARCHETTI, Professeur associée à l’Université de Brescia, Italie - Rapporteur
M. Frédéric SEMET, Professeur à l’Ecole Centrale de Lille, France - Rapporteur
M. Fabien LEHUEDE, Professeur associé à l’Ecole des Mines de Nantes, France - Examinateur
M. Thierry GARAIX, Professeur assistant à l’Ecole des Mines de Saint-Etienne, France - Examinateur
M. Tom VanWOENSEL, Professuer à l’Université des Technologies d’Eindhoven, Pays-Bas - Examinateur
M. Nabil ABSI, Professeur à l’Ecole des Mines de Saint-Etienne - Directeur de thèse
M. Alain QUILLIOT, Professeur à l’ISIMA - Co-directeur de thèse
M. Dominique FEILLET, Professeur à l’Ecole des Mines de Saint-Etienne - Co-encadrant.