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

Ph.D. thesis of Yuhan GUO

Metaheuristics for Solving Large Size Long-term Car Pooling Problem

Starting date: 1 October 2009
Keywords: optimization, car pooling problem, local search, metaheuristic, hyper-heuristic, multi-agent system

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.

In the beginning of 20th century, the widespread use of internet and mobile phones has greatly helped car pooling to expand by enabling people to find, contact and arrange their car pool members more easily. However, the car pooling shows a lack of research on its optimization, since only very few works can be found in the literature. With such background, we present here our research on the long-term car pooling problem. In this thesis, the long-term car pooling problem is modeled and metaheuristics for solving the problem are investigated.

The thesis is organized as follows. 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 designed for the students of Artois University are presented in the appendix.

Involved research axes:

Involved application areas:

No partner is associated with this element.


Defense took place the 09/11/2012 pm30 14:00 Prestige room - FSA - Béthune


  • 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
  • Advisor Gilles GONCALVES Université d'Artois
  • Co-supervisor Tienté HSU Université d'Artois