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

Thèse de Jian XU

Modèles stochastiques évolutionnaires pour la gestion de tournées de véhicules avec fenêtres de temps souples et demandes floues

Date de début : 1er septembre 2004
Mots clés : Tournées de véhicules, Fenêtres de temps, Demandes floues, Stochastique, Dynamique, Théorie des possibilités, Algorithme génétique, Simulation
Encadrement :

Le travail réalisé dans cette thèse traite le problème de la gestion de tournées de véhicules avec fenêtres de temps et demandes floues (VRPTWFD : Vehicle Routing Problem with Time Windows and Fuzzy Demands). Ce problème consiste à trouver des chemins avec un coût minimum pour que les véhicules puissent visiter exactement une fois chaque client en respectant des contraintes. Les clients spécifient leur demande à l’aide d’un nombre flou pour une plus grande souplesse. Le VRPTWFD est étudié dans un contexte aussi bien statique que dynamique.

La théorie des possibilités nous a permis d’exprimer la contrainte de capacité floue en fixant des valeurs de seuils de possibilité et de nécessité. En utilisant cette contrainte de capacité floue, un modèle de programmation sous contraintes probabilistes (CCP) et un modèle à deux-étapes de programmation stochastique avec recours (SPR) ont été proposés pour traiter le VRPTWFD. Des algorithmes génétiques qui intègrent ces modèles, ont été proposés pour la recherche de bonnes solutions.

Dans le VRPTWFD dynamique, des nouveaux clients arrivent au cours de la journée. Une plateforme de simulation ayant la capacité de simuler la journée de service, nous a permis de résoudre le VRPTWFD dynamique « en ligne ».

Afin de vérifier les performances de ces modèles, nous avons construit un benchmark pour le VRPTWFD statique et un benchmark pour le VRPTWFD dynamique en modifiant le jeu de problèmes fournis par Solomon pour le VRPTW, puis nous avons évalué la qualité des solutions fournies par les modèles dans un environnement réel en simulant les situations
réelles à l’aide de scénarios « test ».

Axes scientifiques impliqués :

Aucun partenaire n'est associé à ces travaux.

Soutenance

Soutenance ayant eu lieu le 18/12/2007 à 14:00 Salle Prestige - FSA - Béthune

Jury :

  • Président Rémy DUPAS Université Bordeaux 1
  • Rapporteur Aziz MOUKRIM Université de Technologie de Compiègne
  • Rapporteur Abdelhakim ARTIBA Institut Supérieur de Mécanique de Paris
  • Examinateur Daniel JOLLY Université d'Artois