Xhare-A-Ride: A search optimized dynamic ride sharing system with approximation guarantee

Abstract

Ride sharing is a sustainable, environmentallyfriendly mode of commute that is gaining in popularity. Though there are well-established commercial service providers, there are not many platforms for facilitating peer-To-peer ride sharing, especially in a dynamic scenario, integrated with multi-modal trip planners. Such systems would need to be highly searchoptimized for retrieval of multiple potential ride matches in real time, especially because multi-modal trip planners have a high look-To-book ratio. At the same time, validity of the matches need to be ensured, even in a dynamic setting, while addressing quality considerations and constraints such as maximum detour incurred by rides, walking distance for commuters, and time windows of requests. We describe Xhare-A-Ride (XAR) system, a platform for dynamic peer-To-peer ride sharing, that is scalable, efficient, and highly search-optimized for retrieving multiple potential matches for every ride request, while handling quality considerations. We propose a hierarchical discretization of the geographical region using grids, landmarks and clusters with theoretical guarantees, along with an efficient in-memory indexing of rides for maintaining spatio-Temporal validity within a specified error tolerance. This helps eliminate shortest path computation in realtime during search, thus making XAR search-optimized, hence, suitable for integration with a multi-modal trip planner. We discuss modes of integrating XAR with such a trip planner for building an integrated system. Finally, we evaluate XAR thoroughly on ride share request data generated from the NY taxi trip data set on three fronts: (i) empirical performance against the theoretical guarantees as well as trade-off of performance with system parameters; (ii) benchmark XAR against a state-ofthe-Art ride share system, showing a significant improvement in the search efficiency; and finally, (iii) the efficacy of combining ride sharing with public transportation.