Towards Social-Aware Ridesharing Group Query Services
- 14 December 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Services Computing
- Vol. 10 (4) , 646-659
Abstract
With the deep penetration of smartphones and geo-locating devices, ridesharing is envisioned as a promising solution to transportation-related problems in metropolitan cities, such as traffic congestion and air pollution. Despite the potential to provide significant societal and environmental benefits, ridesharing has not so far been as popular as expected. Notable barriers include social discomfort and safety concerns when traveling with strangers. To overcome these barriers, in this paper, we propose a new type of Social-aware Ridesharing Group (SaRG) queries which retrieve a group of riders by taking into account their social connections and spatial proximities. While SaRG queries are of practical usefulness, we prove that, however, the SaRG query problem is NP-hard. Thus, we design an efficient algorithm with a set of powerful pruning techniques to tackle this problem. We also present several incremental strategies to accelerate the search speed by reducing repeated computations. Moreover, we propose a novel index tailored to our problem to further speed up query processing. Experimental results on real datasets show that our proposed algorithms achieve desirable performance.Keywords
Funding Information
- Research Grants Council of Hong Kong (HKBU211512, HKBU12200114, HKBU12201615)
This publication has 24 references indexed in Scilit:
- Optimization for dynamic ride-sharing: A reviewEuropean Journal of Operational Research, 2012
- An optimization model and a solution algorithm for the many-to-many car pooling problemAnnals of Operations Research, 2011
- Clique Relaxations in Social Network Analysis: The Maximum k-Plex ProblemOperations Research, 2011
- Combinatorial algorithms for the maximum k-plex problemJournal of Combinatorial Optimization, 2010
- The dial-a-ride problem: models and algorithmsAnnals of Operations Research, 2007
- A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraintsEuropean Journal of Operational Research, 2006
- A Branch-and-Cut Algorithm for the Dial-a-Ride ProblemOperations Research, 2006
- A distributed geographic information system for the daily car pooling problemComputers & Operations Research, 2004
- Parallel Tabu search heuristics for the dynamic multi-vehicle dial-a-ride problemParallel Computing, 2004
- Network structure and minimum degreeSocial Networks, 1983