Mobility-Aware Dynamic Taxi Ridesharing

Taxi ridesharing becomes promising and attractive because of the wide availability of taxis in a city and tremendous benefits of ridesharing, e.g., alleviating traffic congestion and reducing energy consumption. Existing taxi ridesharing schemes, however, are not efficient and practical, due to they simply match ride requests and taxis based on partial trip information and omit the offline passengers, who hail a taxi at roadside with no explicit requests to the system. In this paper, we consider the mobility-aware taxi ridesharing problem, and present mT- Share to address these limitations. mT-Share fully exploits the mobility information of ride requests and taxis to achieve efficient indexing of taxis/requests and better passenger-taxi matching, while still satisfying the constraints on passengers' deadlines and taxis' capacities. Specifically, mT-Share indexes taxis and ride requests with both geographical information and travel directions, and supports the shortest path based routing and probabilistic routing to serve both online and offline ride requests. Extensive experiments with a large real-world taxi dataset demonstrate the efficiency and effectiveness of mT-Share, which can response each ride request in milliseconds and with a moderate detour cost. Compared to state-of-the-art methods, mT-Share serves 42% and 62% more ride requests in peak and non-peak hours, respectively.

I. Introduction

Ridesharing allows multiple passengers with the similar itineraries and time schedules to share a vehicle, which can significantly alleviate urban traffic congestion, reduce energy consumption, and bring win-win benefits to both passengers and drivers [21]. Due to the wide availability of taxis in a city, taxi ridesharing becomes a promising transportation mode [21], [22], [41], [42]. Different from private vehicles based ridesharing, also known as carpooling [12], [29], where ride requests are static and ridesharing routes could be planned in advance, taxi ridesharing is more complex, because both ride requests and taxis are highly dynamic [21], [22]. On one hand, passengers usually submit their requests immediately once they need a ride with no prior planning. Even worse, some passengers will not explicitly report their requests but hail a taxi at roadside. On the other hand, a taxi randomly delivers passengers in the city with no fixed route. Such dynamics cause the real-time taxi ridesharing especially challenging, where ride requests need to be timely assigned to taxis and meanwhile taxi schedule and route should be wisely updated to guarantee the quality of services [14], [41].