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

Séminaire

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

Le 23 octobre 2012 à 14h00 Salle des séminaires du LGI2A, FSA, Béthune
Yuhan GUO Doctorant LGI2A

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. 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 pour se déplacer, ont été mis en place partout dans le monde.
Nous présentons ici nos travaux sur le problème de covoiturage
régulier. Dans nos travaux, le problème 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.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 de
test et d’analyse pour évaluer nos approches et une plate-forme de
covoiturage sont présentées.

Mots clés : optimisation, problème du covoiturage, recherche locale,
métaheuristique, hyper-heuristique, système multi-agents.

In english

Title : Metaheuristics for Solving Large Size Long-term Car Pooling
Problem and an Extension

Abstract :
Nowadays, the increased human mobility combined with high use of
private cars increases the load on environment and raises issues about
quality of life. The extensive use of private cars lends to high
levels of air pollution, parking problem, traffic congestion and low
transfer velocity. In order to ease these shortcomings, the car
pooling program, where sets of car owners having the same travel
destination share their vehicles, has emerged all around the world. We
present here our research on the long-term car pooling problem. In our
work, the long-term car pooling problem is modeled and metaheuristics
for solving the problem are investigated. First, the definition and
description of the problem as well as its mathematical model are
introduced. Then, several metaheuristics to effectively and
efficiently solve the problem are presented. These approaches include
a Variable Neighborhood Search Algorithm, a Clustering Ant Colony
Algorithm, a Guided Genetic Algorithm and a Multi-agent Self-adaptive
Genetic Algorithm. Experiments have been conducted to demonstrate the
effectiveness of these approaches on solving the long-term car pooling
problem. Afterwards, we extend our research to a multi-destination
daily car pooling problem, which is introduced in detail manner along
with its resolution method. At last, an algorithm test and analysis
platform for evaluating the algorithms and a car pooling platform are
presented.

Keywords : optimization, car pooling problem, local search,
metaheuristic, hyper-heuristic, multi-agent system.