Laboratoire de Génie Informatique et d’Automatique de l’Artois

Thèse de Nathalie HELAL

Une réponse évidentielle pour le problème de tournée de véhicules avec contrainte de capacité et demandes incertaines

Date de début : 1er octobre 2014
Financement : Contrat doctoral
Mots clés : Optimisation sous incertitudes, Théorie des fonctions de croyance, Problème de tournée de véhicules
Encadrement :

Le problème de tournées de véhicules avec contrainte de capacité est un problème important en optimisation combinatoire. L’objectif du problème est de déterminer l’ensemble des routes, nécessaire pour servir les demandes déterministes des clients ayant un cout minimal, tout en respectant la capacité limite des véhicules. Cependant, dans de nombreuses applications réelles, nous sommes confrontés à des incertitudes sur les demandes des clients. La plupart des travaux qui ont traité ce problème ont supposé que les demandes des clients étaient des variables aléatoires. Nous nous proposons dans cette thèse de représenter l’incertitude sur les demandes des clients dans le cadre de la théorie de l’évidence - un formalisme alternatif pour modéliser les incertitudes. Pour résoudre le problème d’optimisation qui résulte, nous généralisons les approches de modélisation classiques en programmation stochastique. Précisément, nous proposons deux modèles pour ce problème. Le premier modèle, est une extension de l’approche Chance-Constrained Programming, qui impose des bornes minimales pour la croyance et la plausibilité que la somme des demandes sur chaque route respecte la capacité des véhicules. Le deuxième modèle étend l’approche stochastic programming with recourse : l’incertitude sur les recours (actions correctives) possibles sur chaque route est représentée par une fonction de croyance et le coût d’une route est alors son coût classique (sans recours) additionné du pire coût espéré des recours. Certaines propriétés de ces deux modèles sont étudiées. Un algorithme de recuit simulé est adapté pour résoudre les deux modèles et est testé expérimentalement.

Thèmes scientifiques impliqués :

Domaines d'application impliqués :

Aucun partenaire n'est associé à ces travaux.

Soutenance

Soutenance ayant eu lieu le 20/12/2017 à 13:00 Salle Prestige, FSA Béthune

Jury :

  • Rapporteur Didier DUBOIS Université Paul Sabatier Toulouse
  • Rapporteur Arnaud MARTIN Université Rennes 1
  • Examinateur Laetitia JOURDAN Université de Lille 1
  • Examinateur Caroline THIERRY Université Jean Jaurès Toulouse
  • Examinateur Sébastien DESTERCKE Université de Technologie de Compiègne
  • Invité David MERCIER Université d'Artois