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

Thèse de Yuhan GUO

Métaheuristiques pour la Résolution de Problème de Covoiturage régulier de Grande Taille et d’une Extension

Date de début : 1er octobre 2009
Mots clés : Optimisation, problème du covoiturage, recherche locale, métaheuristique, hyper-heuristique, système multi-agents
Encadrement :

La dispersion spatiale de l’habitat et des activités de ces dernières décennies a fortement contribué à un allongement des distances et des temps de trajets domicile-travail. Cela a pour conséquence un accroissement de l’utilisation des voitures particulières, notamment au sein et aux abords des grandes agglomérations. Ce boom de la mobilité n’est pas sans conséquence et l’actualité nous le rappelle chaque jour : la pollution atmosphérique, les accidents de la route, les embouteillages, ... Afin de réduire les impacts dus à l’augmentation du trafic routier, des services de covoiturage, où des usagers ayant la même destination se regroupent en équipage (un chauffeur et des passagers) pour se déplacer, ont été mis en place partout dans le monde.

Les avancées technologiques de ces dernières décennies de l’internet, de la téléphonie mobile et des systèmes de géolocalisation ont largement contribué à faciliter l’utilisation des systèmes de covoiturage, elles permettent plus facilement aux usagers de trouver, de contacter et de constituer les équipages. Toutefois, le problème du covoiturage semble être le parent pauvre de la famille des problèmes de tournées de véhicules : très peu de travaux concernent cette problématique. Néanmoins, on constate depuis quelques années, un intérêt accru pour ce problème, dû aux mouvements écologiques, à l’augmentation des prix du carburant, ... Nous présentons ici nos travaux sur le problème de covoiturage régulier. Dans cette thèse, le problèmes de covoiturage régulier a été modélisé et plusieurs métaheuristiques de résolution ont été implémentées, testées et comparées.

La thèse est organisée de la façon suivante : tout d’abord, nous commençons par présenter la définition et la description du problème ainsi que le modèle mathématique associé. Ensuite, plusieurs métaheuristiques pour résoudre le problème sont présentées. Ces approches sont au nombre de quatre : un algorithme de recherche locale à voisinage variable, un algorithme à base de colonies de fourmis, un algorithme génétique guidée et un système multi-agents génétiques auto-adaptatif. Des expériences ont été menées pour démontrer l’efficacité de nos approches. Nous continuons ensuite avec la présentation et la résolution d’une extension du problème de covoiturage occasionel comportant plusieurs destinations. Pour terminer, une plate-forme java de test et d’analyse pour évaluer nos approches et une plate-forme de covoiturage conçue pour les étudiants de l’Université d’Artois sont présentées dans l’annexe.

Axes scientifiques impliqués :

Domaines d'application impliqués :

Aucun partenaire n'est associé à ces travaux.

Soutenance

Soutenance ayant eu lieu le 09/11/2012 à 14:00 Salle Prestige - FSA - Béthune

Jury :

  • Rapporteur Jin-kao HAO Université d'Angers
  • Rapporteur Van-Dat CUNG Institut Polytechnique de Grenoble
  • Examinateur El-Ghazali TALBI Université des Sciences et Technologies de Lille
  • Examinateur Marie-José HUGUET Institut National des Sciences Appliquées de Toulouse
  • Examinateur Marie-José HUGUET Institut National des Sciences Appliquées de Toulouse
  • Directeur Gilles GONCALVES Université d'Artois
  • Co-encadrant Tienté HSU Université d'Artois