A distributed algorithm solving multiobjective dynamic car pooling problem

Car pooling problem (CPP) is a well known transport solution that consists in sharing a car between a driver and passengers sharing the same route, or part of it. The challenge is to minimize both the number of required cars and the additional cost in terms of time for the drivers. There are two resulting problems that are interdependent and NP-complete: assigning passengers to cars and finding the shortest path for the drivers so that the overall cost is minimized. In this paper, we consider a multiobjective dynamic car pooling problem, where both the cost and the total travel time of drivers are to be minimized. We based on labeling algorithms for solving the multiobjective shortest problem investigate a new algorithm to solve this problem. Preliminary numerical results in a real scenario are reported. They show that our proposed algorithm is efficient and promising to real time applications.