An artificial bee colony algorithm for the dynamic taxi sharing problem

Abstract

Taxi sharing is a popular travel mode that the passengers with similar trips share the same taxi. Passengers and drivers use the mobile app to get matched in real-time by providing the ride information. This paper proposes a dynamic taxi-sharing problem which maximizes the total benefits of the taxi sharing network considering time, cost, and capacity constraints. To solve the dynamic problem, the authors divide it into many small continuous static sub-problems based on a specific time interval. The sub-problem is then solved by a combined Artificial Bee Colony (ABC) algorithm with path relinking, while the contraction hierarchy and vantage point tree are included to calculate the shortest path and narrow the search range respectively. For illustrative purposes, a case study of taxi sharing in Chengdu, China is studied. The proposed solution method is compared with the greedy randomized adaptive search procedure (GRASP) with path relinking proposed by Santos and Xavier (1). The results indicate that (1) The performance of the ABC model proposed in this paper is better than that of the GRASP model proposed by Santos and Xavier in solving dynamic taxi sharing problem; (2) With the longer length of time interval and higher tolerance for wasting time, the performance of the model is better, while path relinking can improve the model performance in dynamic taxi sharing problem; (3) By using the proposed method, the average saving ratio can reach 26% at the cost of only 16% extra travel time.