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

Thèse de Haiyan HOUSROUM

Une approche génétique pour la résolution du problème VRPTW dynamique

Date de début : 1er septembre 2002
Mots clés : Problème DVRPTW, Algorithme génétique “en ligne”, Simulation, Plans d’expériences
Encadrement :

Ces dernières années les systèmes de transport utilisés pour le ramassage et la distribution de biens ou de services ont fait l’objet de nombreuses études dans la communauté scientifique. De nos jours, la plupart des systèmes de transport doivent pouvoir fonctionner en respectant des contraintes temporelles strictes et ceci en s’adaptant aux aléas du problème. En effet, les clients ou partenaires d’une entreprise exigent de celle-ci une qualité de service garantie (i.e. délais à
respecter). De plus, l’environnement dans lequel une entreprise doit évoluer est bien souvent incertain et donc sa réactivité est également un atout important. Ceci a conduit à définir des modèles de pilotage des systèmes de transport dits dynamiques dans lesquels une partie des
données est considérée comme dépendante du temps.

Le domaine dans lequel s’inscrit nos travaux, concerne le problème classique de l’élaboration de tournées de véhicules (VRP : Vehicle Routing Problem). Celui-ci consiste à construire des tournées de coût minimal afin que de visiter une fois et une seule fois un ensemble de clients
géographiquement distribué. Le travail présenté dans cette thèse traite plus précisément de la résolution du problème de l’élaboration dynamique de tournées de véhicules avec fenêtres de temps (DVRPTW : Dynamic Vehicle Routing Problem with Time Windows) et de quelques
unes de ses extensions.

L’objectif de ce travail était double. D’une part, il s’agissait de montrer qu’une approche de type évolutionniste était utilisable dans un cadre dynamique. D’autre part, il fallait vérifier que les performances que l’on pouvait attendre de ce type d’approche étaient comparables voire
supérieures à celles des meilleures techniques utilisées à ce jour.
Pour atteindre ces objectifs, nous avons utilisé la technique des Algorithmes Génétiques (AG) pour définir un planificateur dirigé par les évènements. Ce planificateur cherche à optimiser dynamiquement le problème après chaque évènement significatif (“arrivée d’une nouvelle
demande” et “fin de service chez un client”) survenant tout au long de la journée d’ouverture.

L’algorithme génétique est basé pour cela sur des chromosomes de taille variable dans le temps permettant de prendre en compte l’arrivée de nouveaux clients pendant l’exécution effective des tournées de véhicules.
L’efficacité des approches AG pose la question délicate du réglage de certains paramètres par rapport au problème à traiter. Nous avons utilisé un réglage “ a priori ” de ces paramètres en utilisant la technique des plans d’expériences.

Le dernier point de cette thèse porte sur une plate-forme développée en JAVA pour évaluer notre approche et comparer les résultats avec ceux obtenus par d’autres approches.

Axes scientifiques impliqués :

Domaines d'application impliqués :

Aucun partenaire n'est associé à ces travaux.

Soutenance

Soutenance ayant eu lieu le 03/05/2005 à 14:00 Salle Prestige - FSA - Béthune

Jury :

  • Président Anne-Marie JOLLY-DESODT Université de Valenciennes
  • Rapporteur Frédéric SEMET Université de Valenciennes
  • Rapporteur Christian PRINS Université de Technologie de Troyes
  • Examinateur Daniel JOLLY Université d'Artois
  • Examinateur Slim HAMMADI Ecole centrale de Lille
  • Directeur Gilles GONCALVES Université d'Artois
  • Co-directeur Rémy DUPAS Université d'Artois