Xhare-a-Ride: A Search Optimized Dynamic Ride Sharing System with Approximation Guarantee
| Autor: | Koushik Chattopadhyay, Raja Subramaniam Thangaraj, Narendra Annamaneni, Gurulingesh Raravi, Koyel Mukherjee, Asmita Metrewar |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
050210 logistics & transportation
Database business.industry Computer science Distributed computing media_common.quotation_subject 05 social sciences 02 engineering and technology Service provider computer.software_genre Vehicle dynamics Public transport 0502 economics and business 0202 electrical engineering electronic engineering information engineering Benchmark (computing) 020201 artificial intelligence & image processing Quality (business) business computer media_common |
| Zdroj: | ICDE |
| DOI: | 10.1109/icde.2017.156 |
| Popis: | 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-of the-art ride share system, showing a significant improvement in the search efficiency, and finally, (iii) the efficacy of combining ride sharing with public transportation. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|