Taxi unified recommendation algorithm based on region partition

doi:10.11772/j.issn.1001-9081.2016.08.2109

Journal of Computer Applications ›› 2016, Vol. 36 ›› Issue (8): 2109-2113.DOI: 10.11772/j.issn.1001-9081.2016.08.2109

Previous Articles Next Articles

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).

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

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

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

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

Abstract

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

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

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

CLC Number:

TP311

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.

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

References

[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

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	GUO Fangfang, CHAO Luomeng, ZHU Jianwen. Multi-source data parallel preprocessing method based on similar connection [J]. Journal of Computer Applications, 2019, 39(1): 57-60.
[2]	MA Youzhong, ZHANG Zhihui, LIN Chunjie. Research progress in similarity join query of big data [J]. Journal of Computer Applications, 2018, 38(4): 978-986.
[3]	CAO Yunpeng, WANG Haifeng. Communication optimization for intermediate data of MapReduce computing model [J]. Journal of Computer Applications, 2018, 38(4): 1078-1083.
[4]	GUO Yuhan, YI Peng. Hybrid variable neighborhood search algorithm for long-term carpooling problem [J]. Journal of Computer Applications, 2018, 38(10): 3036-3041.
[5]	ZHANG Chengchang, ZHANG Huayu, LUO Jianchang, HE Feng. Massive data analysis of power utilization based on improved K-means algorithm and cloud computing [J]. Journal of Computer Applications, 2018, 38(1): 159-164.
[6]	MA Shengjun, CHEN Wanghu, YU Maoyi, LI Jinrong, JIA Wenbo. Analysis of factors affecting efficiency of data distributed parallel application in cloud environment [J]. Journal of Computer Applications, 2017, 37(7): 1883-1887.
[7]	LIAO Bin, ZHANG Tao, GUO Binglei, YU Jiong, ZHANG Xuguang, LIU Yan. Performance optimization of ItemBased recommendation algorithm based on Spark [J]. Journal of Computer Applications, 2017, 37(7): 1900-1905.
[8]	XIAO Zida, ZHU Ligu, FENG Dongyu, ZHANG Di. Performance optimization of distributed database aggregation computing [J]. Journal of Computer Applications, 2017, 37(5): 1251-1256.
[9]	WU Jiagao, XIA Xuan, LIU Linfeng. Parallel trajectory compression method based on MapReduce [J]. Journal of Computer Applications, 2017, 37(5): 1282-1286.
[10]	WANG Zhuo, SUO Bo, PAN Wei. Parallel algorithm for triangle enumeration [J]. Journal of Computer Applications, 2017, 37(12): 3397-3400.
[11]	YANG Junjie, LIAO Zhuofan, FENG Chaochao. Survey on big data storage framework and algorithm [J]. Journal of Computer Applications, 2016, 36(9): 2465-2471.
[12]	ZHAO Hu, YANG Yu. Error back propagation algorithm based on iterative MapReduce framework [J]. Journal of Computer Applications, 2016, 36(4): 923-926.
[13]	LI Yue, LIU Chen. Parallel discovery of fake plates based on historical automatic number plate recognition data [J]. Journal of Computer Applications, 2016, 36(3): 864-870.
[14]	LIANG Junjie, GAN Wenting, YU Dunhui. Personalized recommendation algorithm based on location bitcode tree [J]. Journal of Computer Applications, 2016, 36(2): 419-423.
[15]	LIN Yang, JIANG Yu'e, LIN Jie. Local similarity detection algorithm for time series based on distributed architecture [J]. Journal of Computer Applications, 2016, 36(12): 3285-3291.