Alternative Pickup Locations in Taxi-Sharing: A Feasibility Study

Abstract

Taxi-sharing is a known solution for reducing congestion and is more beneficial when the traveled miles, imposed by detours while serving additional passengers, are minimized. This study proposes incorporation of alternative meeting points in taxi-sharing routes to boost the efficiency of the system by eliminating unnecessary detours and improving the chances of passengers being matched. Unlike most ridesharing systems, in the proposed approach, passengers are not necessarily picked up or dropped off at their original location, but at a walkable distance from their origin. The proposed framework deals with practical challenges of including meeting points in a real-world high-demand taxi-sharing system with hundreds of requests per minute. This includes efficient selection of alternative pick up locations and incorporation of these alternatives into a novel mixed integer linear programming (MILP) formulation to find the optimal schedule. Using the 2015 New York City (NYC) yellow cab dataset, first, the potential benefits of introducing meeting points in Manhattan road network are demonstrated. Given the Nondeterministic Polynomial-time Hard (NP-hard) nature of the associated optimization problem, the problem is then broken down into smaller-sized problems forming clusters of passengers with high potential of sharing a ride. Then, the proposed MILP model is used to find the optimal route for each cluster, while selecting the best pickup point for each passenger. Testing on a sample of the NYC dataset, it is shown that the proposed methodology improves the efficiency of the taxi-sharing system by reducing the wait times by about 50% while considerably reducing total travel times and the number of vehicles used.