Abstract
Ridesharing has been becoming increasingly popular in urban areas worldwide for its low cost and environment friendliness. In this paper, we introduce social-awareness into realtime ridesharing services. In particular, upon receiving a user’s trip request, the service ranks feasible taxis in a way that integrates detour in time and passengers’ cohesion in social distance. We propose a new system framework to support such a social-aware taxi-sharing service. It provides two methods for selecting candidate taxis for a given trip request. The grid-based method quickly goes through available taxis and returns a relatively larger candidate set, whereas the edge-based method takes more time to obtain a smaller candidate set. Furthermore, we design techniques to speed up taxi route scheduling for a given trip request. We propose travel-time based bounds to rule out unqualified cases quickly, as well as algorithms to find feasible cases efficiently. We evaluate our proposals using a real taxi dataset from New York City. Experimental results demonstrate the efficiency and scalability of the proposed taxi recommendation solution in real-time social-aware ridesharing services.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ma, S., Wolfson, O.: Analysis and evaluation of the slugging form of ridesharing. In: Proceedings of the 21st ACM SIGSPATIAL, pp. 64–73 (2013)
Cici, B., Markopoulou, A., Frias-Martinez, E., Laoutaris, N.: Assessing the potential of ride-sharing using mobile and social data: a tale of four cities. In: Proceedings of the 2014 ACM International Joint Conference on Pervasive and Ubiquitous Computing, pp. 201–211 (2014)
Ma, S., Zheng, Y., Wolfson, O.: Real-time city-scale taxi ridesharing. IEEE Trans. Knowl. Data Eng. 27(7), 1782–1795 (2015)
Huang, Y., Bastani, F., Jin, R., Wang, X.S.: Large scale real-time ridesharing with service guarantee on road networks. Proc. VLDB Endowment 7(14), 2017–2028 (2014)
Ma, S., Zheng, Y., Wolfson, O.: T-share: a large-scale dynamic taxi ridesharing service. In: IEEE 29th International Conference on Data Engineering (ICDE), pp. 410–421 (2013)
Badger, E.: Slugging-the people’s transit (2011)
Baldacci, R., Maniezzo, V., Mingozzi, A.: An exact method for the car pooling problem based on lagrangean column generation. Oper. Res. 52(3), 422–439 (2004)
Calvo, R.W., de Luigi, F., Haastrup, P., Maniezzo, V.: A distributed geographic information system for the daily car pooling problem. Comput. Oper. Res. 31(13), 2263–2278 (2004)
Agatz, N., Erera, A., Savelsbergh, M., Wang, X.: Sustainable passenger transportation: Dynamic ride-sharing (2010)
Tsubouchi, K., Hiekata, K., Yamato, H.: Scheduling algorithm for on-demand bus system. In: Information Technology: New Generations, 2009, ITNG 2009, pp. 189–194. IEEE (2009)
Yuan, N.J., Zheng, Y., Zhang, L., Xie, X.: T-finder: a recommender system for finding passengers and vacant taxis. IEEE TKDE 25(10), 2390–2403 (2013)
Yan, S., Chen, C.Y.: An optimization model and a solution algorithm for the many-to-many car pooling problem. Ann. Oper. Res. 191(1), 37–71 (2011)
Cordeau, J.F., Laporte, G.: The dial-a-ride problem: models and algorithms. Ann. Oper. Res. 153(1), 29–46 (2007)
Xiang, Z., Chu, C., Chen, H.: A fast heuristic for solving a large-scale static dial-a-ride problem under complex constraints. Eur. J. Oper. Res. 174(2), 1117–1139 (2006)
Zhao, W., Qin, Y., Yang, D., Zhang, L., Zhu, W.: Social group architecture based distributed ride-sharing service in vanet. Int. J. Distrib. Sens. Netw. 10(3), 650923 (2014)
Agatz, N., Erera, A., Savelsbergh, M., Wang, X.: Optimization for dynamic ride-sharing: a review. Eur. J. Oper. Res. 223(2), 295–303 (2012)
Rigby, M., Krüger, A., Winter, S.: An opportunistic client user interface to support centralized ride share planning. In: Proceedings of the 21st ACM SIGSPATIAL, pp. 34–43 (2013)
d’Orey, P.M., Fernandes, R., Ferreira, M.: Empirical evaluation of a dynamic and distributed taxi-sharing system. In: 15th International IEEE Conference on Intelligent Transportation Systems, pp. 140–146. IEEE (2012)
Li, Y., Chen, R., Chen, L., Xu, J.: Towards social-aware ridesharing group query services. IEEE Trans. Serv. Comput. PP(99), 1 (2015)
Bistaffa, F., Farinelli, A., Ramchurn, S.: Sharing rides with friends: a coalition formation algorithm for ridesharing (2015)
Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202–208 (1985)
Kanoulas, E., Du, Y., Xia, T., Zhang, D.: Finding fastest paths on a road network with speed patterns. In: ICDE 2006, p. 10, April 2006
TLC: NYC TLC trip data. http://www.nyc.gov/html/tlc/html/about/trip_record_data.shtml
SNAP: Gowalla. https://snap.stanford.edu/data/loc-gowalla.html
Acknowledgments
This work is supported by Hong Kong RGC grants 12200114, 12201615, 12244916 and NSFC grant 61602420.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Fu, X., Huang, J., Lu, H., Xu, J., Li, Y. (2017). Top-k Taxi Recommendation in Realtime Social-Aware Ridesharing Services. In: Gertz, M., et al. Advances in Spatial and Temporal Databases. SSTD 2017. Lecture Notes in Computer Science(), vol 10411. Springer, Cham. https://doi.org/10.1007/978-3-319-64367-0_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-64367-0_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-64366-3
Online ISBN: 978-3-319-64367-0
eBook Packages: Computer ScienceComputer Science (R0)