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.