Solving Taxi Sharing Problem using Metaheuristics

Transportation is one of the most important parts of cities. Sharing systems play an important role in the development of transportation and become very popular in recent years. Taxi Sharing includes grouping passengers with similar time schedules and assigning them to one shared taxi. This paper presents the application of two metaheuristic algorithms, genetic algorithm (GA) and particle swarm optimization (PSO) to the taxi sharing problem. Generally most of the requests for taxi come from the center of different districts of the cities. By using a well-known clustering algorithm K-means at first, we categorize geographically the requests. Then the GA and PSO methods are used to solve each of the sub problems. In the taxi sharing problem, riders specify their origins, destinations, earliest departure times, and latest arrival times. Taking all requests into consideration, the system dispatcher determines which requests can be grouped and thus served by one taxi, without violating any user specified time windows and taxi capacity. The objective is to minimize the system wide vehicle miles traveled. Both algorithms are compared against each other and against the state of the art heuristic method in the literature. The experimental evaluation is performed over a real world dataset of Washington, D.C. Results show that the proposed algorithms are able to efficiently reach significant improvements in quality of solution over the basic heuristic method.