基于区域划分的出租车统一推荐算法

doi:10.11772/j.issn.1001-9081.2016.08.2109

计算机应用 ›› 2016, Vol. 36 ›› Issue (8): 2109-2113.DOI: 10.11772/j.issn.1001-9081.2016.08.2109

• 第六届中国数据挖掘会议(CCDM 2016) • 上一篇下一篇

基于区域划分的出租车统一推荐算法

吕红瑾, 夏士雄, 杨旭, 黄丹

中国矿业大学计算机科学与技术学院, 江苏徐州 221116

收稿日期:2016-03-13 修回日期:2016-05-04 出版日期:2016-08-10 发布日期:2016-08-10
通讯作者: 吕红瑾
作者简介:吕红瑾(1993-),男,河北邢台人,硕士研究生,主要研究方向:智能网络信息处理、信息挖掘;夏士雄(1961-),男,辽宁抚顺人,教授,博士生导师.博士,主要研究方向为:智能网络信息处理、复杂系统智能故障诊断;杨旭(1992-),男,江苏徐州人,硕士研究生,主要研究方向为:数据挖掘、智能信息处理;黄丹(1991-),女,江苏常州人,硕士研究生,主要研究方向:数据挖掘、智能信息处理。
基金资助:
国家自然科学青年基金资助项目（51404258）；江苏省科技厅产学研联合创新资金前瞻性联合研究项目（BY2014028-09）。

Taxi unified recommendation algorithm based on region partition

LYU Hongjin, XIA Shixiong, YANG Xu, HUANG Dan

School of Computer Science and Technology, China University of Mining and Technology, Xuzhou Jiangsu 221116, China

Received:2016-03-13 Revised:2016-05-04 Online:2016-08-10 Published:2016-08-10
Supported by:
This work is partially supported by the National Natural Science Foundation of China (51404258), the Fundamental Research Funds for the Department of Science and Technology Project of Jiangsu Province (BY2014028-09).

摘要/Abstract

摘要： 针对在极端天气或交通繁忙时乘客无法快速搭乘出租车到达目的地的问题，提出一种基于区域划分的出租车统一推荐算法，不仅提供普通打车服务，同时提供拼车服务。首先，将区域作为旅程标识，在旅程匹配方面化不可能为可能；其次，在拼车服务中算法将两对路线相近的乘客进行即时匹配，帮乘客拼车共乘；最后，选取绕远时间比例最小的出租车推荐给用户。使用包含14747辆出租车的全球定位系统（GPS）数据对算法进行评估，与CallCab系统相比虽然在减少的总里程数上下降了10%左右，但每次拼车平均只需要多花费6%的时间，且降低的送达乘客总里程数同样达到30%，不仅大幅度减少汽车尾气的排放，同时在用户更加关注的时间消耗方面表现更佳。

关键词: 拼车, 区域划分, 全球定位系统数据, MapReduce, 里程数

Abstract: In extreme weather or traffic, passengers cannot get a taxi to the destination quickly, thus a taxi unified recommendation algorithm based on region partition was proposed to provide common taxi service and carpooling service. First of all, the region was regarded as the logo of journey, making the journey matching possible. Secondly, in the carpooling service, the similar routes of two passengers were matched in real-time to help passenger carpool sharing. Finally, the taxi with the minimum percentage of bypass time was selected to recommend to the user. The Global Positioning System (GPS) data of 14747 taxis was used to evaluate the proposed algorithm. Compared with CallCab system, the total mileage of the proposed algorithm was dropped by about 10%, while the carpooling time was only raised by 6% on average, as well as the total passenger mileage was reduced by 30%. Experimental results show that the proposed algorithm not only can significantly reduce the emission of automotive exhaust, but also has better performance in terms of time consumption.

Key words: carpooling, geographic division, Global Positioning System (GPS)data, MapReduce, mileage

中图分类号:

TP311

吕红瑾, 夏士雄, 杨旭, 黄丹. 基于区域划分的出租车统一推荐算法[J]. 计算机应用, 2016, 36(8): 2109-2113.

LYU Hongjin, XIA Shixiong, YANG Xu, HUANG Dan. Taxi unified recommendation algorithm based on region partition[J]. Journal of Computer Applications, 2016, 36(8): 2109-2113.

参考文献

[1] Taxi of tomorrow survey[EB/OL].[2015-11-16].http://www.nyc.gov/html/tlc/downloads/pdf/tot_survey_results_02_10_11.pdf.
[2] The New York city taxicab fact book[EB/OL].[2015-11-16].http://www.schallerconsult.com/taxi/taxifb.pdf.
[3] BALAN R K,NGUYEN K X,JIANG L.Real-time trip information service for a large taxi fleet[C]//MobiSys'11:Proceedings of the 9th International Conference on Mobile Systems.New York:ACM,2011:99-112.
[4] WU W,NG W S,KRISHNASWAMY S,et al.To taxi or not to taxi? -enabling personalised and real-time transportation decisions for mobile users[C]//MDM'12:Proceedings of the 2012 IEEE 13th International Conference on Mobile Data Management.Washington,DC:IEEE Computer Society,2012:320-323.
[5] GE Y,XIONG H,TUZHILIN A,et al.An energy-efficient mobile recommender system[C]//KDD'10:Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2010:899-908.
[6] LIU W,ZHENG Y,CHAWLA S,et al.Discovering spatiotemporal causal interactions in traffic data streams[C]//KDD'11:Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM,2011:1010-1018.
[7] HUANG Y,POWELL J W.Detecting regions of disequilibrium in taxi services under uncertainty[C]//SIGSPATIAL'12:Proceedings of the 20th International Conference on Advances in Geographic Information Systems.New York:ACM,2012:139-148.
[8] 肖强,何瑞春,张薇,等.基于模糊聚类和识别的出租车合乘算法研究[J].交通运输系统工程与信息,2014,14(5):119-125.(XIAO Q,HE R C,ZHANG W,et al.Algorithm research of taxi carpooling based on fuzzy clustering and fuzzy recognition[J].Journal of Transportation Systems Engineering and Information Technology,2014,14(5):119-125.)
[9] 白竹,金晓红.出租车GPS数据的应用研究[J].黑龙江工程学院学报,2014,28(2):50-54.(BAI Z,JIN X H.Research on the application of taxi GPS data[J].Journal of Heilongjiang Institute of Technology,2014,28(2):50-54.)
[10] DEAN J,GHEMAWAT S.MapReduce:simplified data processing on large clusters[C]//OSDI'04:Proceedings of the 6th Conference on Symposium on Operating Systems Design&Implementation.Berkeley,CA:USENIX Association,2004,6:Article No.10.
[11] 何贤国,孙国道,高家全,等.出租车GPS大数据的道路行车可视分析[J].计算机辅助设计与图形学学报,2014,26(12):2163-2172.(HE X G,SUN G D,GAO J Q,et al.Visual analytics of road traffic with large scale taxi GPS data[J].Journal of Computer-Aided Design&Computer Graphics,2014,26(12):2163-2172.)
[12] 桂智明,向宇,李玉鉴.基于出租车轨迹的并行城市热点区域发现[J].华中科技大学学报(自然科学版),2012,40(S1):187-190.(GUI Z M,XIANG Y,LI Y J.Parallel discovering of city hot spot based on taxi trajectories[J].Journal of Huazhong University of Science and Technology (Natural Science Edition),2012,40(S1):187-190.)
[13] 唐炉亮,郑文斌,王志强,等.城市出租车上下客的GPS轨迹时空分布探测方法[J].地球信息科学学报,2015,17(10):1179-1186.(TANG L L,ZHENG W B,WANG Z Q,et al.Space time analysis on the pick-up and drop-off of taxi passengers based on GPS big data[J].Journal of Geo-Information Science,2015,17(10):1179-1186.)
[14] Data description for UrbanCPS[EB/OL].[2015-11-20].http://www-users.cs.umn.edu/~tianhe/BIGDATA/.
[15] ZHANG D S,HE T,LIU Y,et al.CallCab:A unified recommendation system for carpooling and regular taxicab services[C]//IEEE Big Data 2013:Proceedings of the 2013 IEEE International Conference on Big Data.Piscataway,NJ:IEEE,2013:439-447.

基于区域划分的出租车统一推荐算法

Taxi unified recommendation algorithm based on region partition

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	王家亮, 李树华, 张海涛. 基于贝叶斯估计与区域划分遍历的四轴飞行器避障路径规划算法[J]. 计算机应用, 2021, 41(2): 384-389.
[2]	王松伟, 赵秋阳, 王宇航, 饶小平. 基于深度学习的脑片图像区域划分方法[J]. 计算机应用, 2020, 40(4): 1202-1208.
[3]	郭方方, 潮洛蒙, 朱建文. 基于相似连接的多源数据并行预处理方法[J]. 计算机应用, 2019, 39(1): 57-60.
[4]	马友忠, 张智辉, 林春杰. 大数据相似性连接查询技术研究进展[J]. 计算机应用, 2018, 38(4): 978-986.
[5]	曹云鹏, 王海峰. 面向MapReduce计算模式的中间数据通信优化[J]. 计算机应用, 2018, 38(4): 1078-1083.
[6]	郭良敏, 王安鑫, 郑孝遥. 基于区域划分的轨迹隐私保护方法[J]. 计算机应用, 2018, 38(11): 3263-3269.
[7]	张承畅, 张华誉, 罗建昌, 何丰. 基于云计算和改进K-means算法的海量用电数据分析方法[J]. 计算机应用, 2018, 38(1): 159-164.
[8]	马生俊, 陈旺虎, 俞茂义, 李金溶, 郏文博. 云环境下影响数据分布并行应用执行效率的因素分析[J]. 计算机应用, 2017, 37(7): 1883-1887.
[9]	廖彬, 张陶, 国冰磊, 于炯, 张旭光, 刘炎. 基于Spark的ItemBased推荐算法性能优化[J]. 计算机应用, 2017, 37(7): 1900-1905.
[10]	肖子达, 朱立谷, 冯东煜, 张迪. 分布式数据库聚合计算性能优化[J]. 计算机应用, 2017, 37(5): 1251-1256.
[11]	吴家皋, 夏轩, 刘林峰. 基于MapReduce的轨迹压缩并行化方法[J]. 计算机应用, 2017, 37(5): 1282-1286.
[12]	王卓, 索勃, 潘巍. 三角形的并行枚举算法[J]. 计算机应用, 2017, 37(12): 3397-3400.
[13]	杨俊杰, 廖卓凡, 冯超超. 大数据存储架构和算法研究综述[J]. 计算机应用, 2016, 36(9): 2465-2471.
[14]	魏臻, 张晓旭, 陆阳, 卫星. 井下巷道机车无线接入通信策略[J]. 计算机应用, 2016, 36(4): 909-913.
[15]	赵虎, 杨宇. 基于迭代式MapReduce的误差反向传播算法[J]. 计算机应用, 2016, 36(4): 923-926.