research-article

Mining regular routes from GPS data for ridesharing recommendations

Authors:

Guisheng ChenAuthors Info & Claims

UrbComp '12: Proceedings of the ACM SIGKDD International Workshop on Urban Computing

Pages 79 - 86

https://doi.org/10.1145/2346496.2346510

Published: 12 August 2012 Publication History

Abstract

The widely use of GPS-enabled devices has provided us amount of trajectories related to individuals' activities. This gives us an opportunity to learn more about the users' daily lives and offer optimized suggestions to improve people's trip styles. In this paper, we mine regular routes from a users' historical trajectory dataset, and provide ridesharing recommendations to a group of users who share similar routes. Here, regular route means a complete route where a user may frequently pass through approximately in the same time of day. In this paper, we first divide users' GPS data into individual routes, and a group of routes which occurred in a similar time of day are grouped together by a sliding time window. A frequency-based regular route mining algorithm is proposed, which is robust to slight disturbances in trajectory data. A feature of Fixed Stop Rate (FSR) is used to distinguish the different types of transport modes. Finally, based on the mined regular routes and transport modes, a grid-based route table is constructed for a quick ride matching. We evaluate our method using a large GPS dataset collected by 178 users over a period of four years. The experiment results demonstrate that the proposed method can effectively extract the regular routes and generate rideshare plan among users. This work may help ridesharing to become more efficient and convenient.

References

[1]

Keivan G., Ali H. and Masoud H. 2011. Real-Time Rideshare Matching Problem. Technical Report. University of Maryland at College Park.

[2]

Andrew A., Attanucci J., and Rabi M. 2011. Real-Time Ridesharing. Transportation Research Record: Journal of the Transportation Research Board. 2217: 103--110.

[3]

Chen, L., M. Lv, and Qian Y. 2011A personal route prediction system based on trajectory data mining. Information Sciences 181(7), 1264--1284.

Digital Library

[4]

Chang, K.-P., L.-Y. Wei, M.-Y. Yeh, and W.-C. Peng. 2011. Discovering personalized routes from trajectories. In Proc. of the 3rd ACM SIGSPATIAL International Workshop on LBSN'11. Chicago, Illinois, ACM, 33--40.

Digital Library

[5]

Zheng Y., Zhang L., Xie X., and Ma, W.-Y 2009. Mining interesting locations and travel sequences from GPS trajectories. In Proc. of WWW'09. Madrid Spain. ACM Press, 791--800.

Digital Library

[6]

Zheng Y., Li Q., Chen Y. Xie X. and Ma W.-Y. 2008. Understanding Mobility Based on GPS Data. In Proc. of UbiComp'08. Seoul, Korea. ACM Press: 312--321.

Digital Library

[7]

Zheng Y., Xie X., and Ma W. 2010. GeoLife: A Collaborative Social Networking Service among User, location and trajectory. Invited paper, in IEEE Data Engineering Bulletin. 33, 2, 2010, 32--40.

[8]

Ece Kamar and Eric Horvitz. 2009. Collaboration and Shared Plans in the Open World: Studies of Ridesharing. IJCAI 2009, 187--194.

Digital Library

[9]

Gidofalvi, G. and T. B. Pedersen. 2007. Cab-sharing: An Effective, Door-to-Door, On-Demand Transportation Service. Proceedings of the 6th European Congress on Intelligent Transport Systems and Services, ERTICO.

[10]

Kammerdiener, T. and H. Zhang. 2011. Classification of ride-sharing partners based on multiple constraints. J. Comput. Sci. Coll. 26(4), 95--101.

Digital Library

[11]

C.-W., Cho, Y.-H. Wu, C. Yen, and C.-Y. Chang. 2011. Passenger Search by Spatial Index for Ridesharing. In TAAI 2011, 88--93.

Digital Library

[12]

Teodorović, D. and M. Dell' Orco. 2008. Mitigating Traffic Congestion: Solving the Ride-Matching Problem by Bee Colony Optimization. Transportation Planning and Technology 31(2): 135--152.

[13]

Gidófalvi, G. and T. Pedersen. 2009. Mining Long, Sharable Patterns in Trajectories of Moving Objects. GeoInformatica 13(1): 27--55.

Digital Library

[14]

J. Yuan, Y. Zheng, C. Zhang, W. Xie, G. Sun, H. Yan, and X. Xie. 2010. T-drive: Driving directions based on taxi trajectories. Proc.GIS. ACM, 2010.

Digital Library

[15]

http://research.microsoft.com/en-us/downloads/b16d359d-d164-469e-9fd4-daa38f2b2e13/default.aspx

Cited By

Tran VNhan Vu T(2023)A New Method for Forming Rideshare Groups2023 15th International Conference on Knowledge and Systems Engineering (KSE)10.1109/KSE59128.2023.10299428(1-6)Online publication date: 18-Oct-2023
https://doi.org/10.1109/KSE59128.2023.10299428
Portugal IAlencar PCowan D(2023)Identifying Regions of High Demand for Transportation Services based on Cluster Evolution and Graph Analysis2023 IEEE International Conference on Big Data (BigData)10.1109/BigData59044.2023.10386990(2633-2638)Online publication date: 15-Dec-2023
https://doi.org/10.1109/BigData59044.2023.10386990
Pandey MSaini ASubbiah KChintalapudi NBattineni G(2022)Improved Carpooling Experience through Improved GPS Trajectory Classification Using Machine Learning AlgorithmsInformation10.3390/info1308036913:8(369)Online publication date: 3-Aug-2022
https://doi.org/10.3390/info13080369
Show More Cited By

Index Terms

Mining regular routes from GPS data for ridesharing recommendations
1. Applied computing
  1. Law, social and behavioral sciences
    1. Sociology
2. Information systems
  1. Information retrieval
    1. Retrieval models and ranking
    2. Retrieval tasks and goals
      1. Clustering and classification
  2. Information systems applications
    1. Data mining
      1. Clustering

Recommendations

Real-Time City-Scale Taxi Ridesharing
We proposed and developed a taxi-sharing system that accepts taxi passengers' real-time ride requests sent from smart phones and schedules proper taxis to pick up them via ride sharing, subject to time, capacity, and monetary constraints. The monetary ...
Towards ridesharing with passenger transfers
AAMAS '13: Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems

Ridesharing services have the potential to fill empty seats in cars, reduce emissions and enable more efficient transportation. We propose rideshare services which transfer passengers between multiple drivers. By planning for transfers, we increase the ...
On Ridesharing Competition and Accessibility: Evidence from Uber, Lyft, and Taxi
WWW '18: Proceedings of the 2018 World Wide Web Conference

Ridesharing services such as Uber and Lyft have become an important part of the Vehicle For Hire (VFH) market, which used to be dominated by taxis. Unfortunately, ridesharing services are not required to share data like taxi services, which has made it ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

UrbComp '12: Proceedings of the ACM SIGKDD International Workshop on Urban Computing

August 2012

176 pages

ISBN:9781450315425

DOI:10.1145/2346496

General Chair:
Ouri E. Wolfson
University of Illinois at Chicago
,
Program Chair:
Yu Zheng
Microsoft Research Asia, China

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 August 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Natural Science Foundation of China

Conference

KDD '12

Sponsor:

KDD '12: The 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining

August 12, 2012

Beijing, China

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
516
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)1

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tran VNhan Vu T(2023)A New Method for Forming Rideshare Groups2023 15th International Conference on Knowledge and Systems Engineering (KSE)10.1109/KSE59128.2023.10299428(1-6)Online publication date: 18-Oct-2023
https://doi.org/10.1109/KSE59128.2023.10299428
Portugal IAlencar PCowan D(2023)Identifying Regions of High Demand for Transportation Services based on Cluster Evolution and Graph Analysis2023 IEEE International Conference on Big Data (BigData)10.1109/BigData59044.2023.10386990(2633-2638)Online publication date: 15-Dec-2023
https://doi.org/10.1109/BigData59044.2023.10386990
Pandey MSaini ASubbiah KChintalapudi NBattineni G(2022)Improved Carpooling Experience through Improved GPS Trajectory Classification Using Machine Learning AlgorithmsInformation10.3390/info1308036913:8(369)Online publication date: 3-Aug-2022
https://doi.org/10.3390/info13080369
Xia DZheng LCai XLiu WSun D(2022)Urban Customized Bus Design for Private Car CommutersIEEE Internet of Things Journal10.1109/JIOT.2022.31815919:21(21723-21735)Online publication date: 1-Nov-2022
https://doi.org/10.1109/JIOT.2022.3181591
Chen HLee SOn BJeong D(2021)LSTM-Based Path Prediction for Effective Sensor Filtering in Sensor Registry SystemSensors10.3390/s2123810621:23(8106)Online publication date: 3-Dec-2021
https://doi.org/10.3390/s21238106
Li R(2021)Joint Modeling of User Behaviors Based on Variable-Order Additive Markov Chain for POI RecommendationWireless Communications and Mobile Computing10.1155/2021/43593692021(1-13)Online publication date: 23-Nov-2021
https://doi.org/10.1155/2021/4359369
Martelli FRenda M(2021)Comparison of Trip Matching Algorithms for Mobility Sharing Applications2021 IEEE 22nd International Symposium on a World of Wireless, Mobile and Multimedia Networks (WoWMoM)10.1109/WoWMoM51794.2021.00051(274-279)Online publication date: Jun-2021
https://doi.org/10.1109/WoWMoM51794.2021.00051
Chen LZheng LXia LLiu WSun D(2021)Detecting and analyzing unlicensed taxis: A case study of Chongqing CityPhysica A: Statistical Mechanics and its Applications10.1016/j.physa.2021.126324584(126324)Online publication date: Dec-2021
https://doi.org/10.1016/j.physa.2021.126324
Jia YLee C(2020)Vector Field Model for Trajectory Data and Its Application in Similarity Query2020 IEEE 22nd International Conference on High Performance Computing and Communications; IEEE 18th International Conference on Smart City; IEEE 6th International Conference on Data Science and Systems (HPCC/SmartCity/DSS)10.1109/HPCC-SmartCity-DSS50907.2020.00152(1180-1187)Online publication date: Dec-2020
https://doi.org/10.1109/HPCC-SmartCity-DSS50907.2020.00152
Williams GTushev MEbrahimi FMahmoud A(2020)Modeling user concerns in Sharing Economy: the case of food delivery appsAutomated Software Engineering10.1007/s10515-020-00274-7Online publication date: 9-Aug-2020
https://doi.org/10.1007/s10515-020-00274-7
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents