A Multi-Objective ACO to Solve the Daily Carpool Problem

Introduction

In spite of the technological evolutions integrated in our roads like passage counts in the bitumen, the presence of intelligent signaling lights and the counting of the vehicles, the number and the extent of the traffic jams do not stop increasing. The traffic density at peak hours is one of challenges to solve today. Thus, reducing the congestion cost in urban areas presents a key perspective for transportation services and road users. According to the Center for Economics and Enterprise Research (CEER, 2014), the time spent by vehicles on congested roads is extremely expensive in economic, ecological and commercial terms. Forecasts for the United States, Germany, France and the United Kingdom indicate that the increase in the cost of traffic will increase on average by 46% in 2030 compared to the assessments in 2013.

Cope with these needs, there is no single solution but a multitude of solutions that together can reduce this traffic. Among them, carpooling is a flexible solution for managing the traffic congestion. The basic idea of the carpooling is to maximize the occupancy of empty spaces in passenger cars, sharing all or part of common routes. The drivers offer a carpool whose boarding and disembarking points must meet several constraints related to the journey (shortest, fastest, economical, etc.). The evaluation of the performances of the journeys must take into account these constraints to which are added more general constraints which are the total distance of the journey, the time of displacement, etc.

This solution is enough to convince previous countries to encourage their citizens to move collectively instead of doing it individually. In which, the carpool system in these countries is supported by several online platforms that coordinate the correspondence between passenger requests and driver offers. Among these platforms are Blablacar, Shareyourride, Carpoolonline and Ridesharing. In fact, due to the growing reputation of carpooling, a lot of work has been done on the daily carpooling problem while respecting specific constraints related to travel needs. (Boukhater et al., 2014) classify ridesharing practices according to the travel scenarios in: several points of origin to a single destination (M2O), a point of origin to several destination points (O2M), multiple origin points to multiple destination points (M2M). GUO et al. (2013) propose a meta-heuristic method based on a hybrid ant colony algorithm (HAC) to solve the problem of multi-destination daily carpool (MDCPP), where a number of users (passenger / driver) report their trip information as their location and availability time. The solution of the problem (MDCPP) optimizes both the cost and the travel penalties. Baldacci et al, (2004) propose an exact method based on two linear programming formulations of the carpool problem, they model this problem as the problem vehicle routing problem (VRP). In which the objective is to maximize the rate of satisfaction of the requests in order to minimize the expenses and the penalties of displacement. Nevertheless, the proposed method uses deterministic travel times between passengers and is equal to the Euclidean distances between these passengers. Huang et al. (2015) propose a carpooling route and a genetic algorithm to solve the Carpool Service Problem (CSP) by significantly obtaining ideal solutions while reducing the necessary computing time. The objective of CSP is to minimize two objective functions, the first function is to minimize the number of carpools and the second function is to minimize the travel distance and waiting time for passengers. Cheikh et al. (2017) propose a meta-heuristic approach based on controlled genetic operators (MACGeO) to solve the multi-destination dynamic carpool problem. The basic idea of this approach lies in the fact that chromosome coding is dynamic and in the non-existence of a correction process for crossover and mutation operators. The weak point of this approach is that the authors envision a unique travel constraint with a multipurpose carpool space.