Construct, Merge, Solve and Adapt for Taxi Sharing

Abstract

Taxis are a quick and reliable mean of transportation, especially in those cities where the public transportation system is very inefficient. However, taxis rarely travel with full capacity, and its impact on traffic congestion and pollution in cities is usually important. For this reason, it is interesting to share taxis instead of traveling alone. We are interested in this paper in finding good solutions in a reasonable time for the taxi sharing problem for the very large instances. We adapt the Construct, Merge, Solve and Adapt (CMSA) algorithm to the taxi sharing problem.