Recommendation model of taxi passenger-finding locations based on weighted non-homogeneous Poisson model

doi:10.11772/j.issn.1001-9081.2017092339

Abstract

Abstract: To slove the problem of high taxi empty-loading ratio of taxi and difficulty in finding passengers, a new model called Possion-Kalman combined prediction Model (PKCPM) was proposed. Firstly, weighted Non-Homogeneous Poisson Model (NHPM) was used to get the estimated value of the target time based on taxi historical data. Secondly, the mean value of the passenger demand in the near time, was taken as the predicted value, based on the real-time data. Finally, the predicted value and the estimated value were used as the inputs of Kalman filtering model to predict the target variance, meanwhile, the error backpropagation mechanism was introduced to reduce the next prediction error. The experimental results on the taxi trajectory dataset in Zhengzhou show that compared with NHPM, Weighted NHPM (WNHPM) and Support Vector Machine (SVM), PKCPM achieves a better optimization effect, and the error of PKCPM is reduced by about 8.85 percentage points and 14.9 percentage points respectively compared with WNHPM and SVM. PKCPM can predict passenger demand within different time and spacial grid, and provides a reliable solution to taxi driver for finding passengers.

Key words: empty-loading ratio, Kalman filtering prediction model, weighted Non-Homogeneous Poisson Model (NHPM), passenger demand in the near time

摘要： 针对出租车空载率高、司机寻客难的问题，提出泊松-卡尔曼组合预测模型（PKCPM）。首先，采用加权非齐次泊松模型，针对出租车历史数据进行建模，得到目标时刻的估计值；其次，基于当天的实时数据，将临近时刻乘客需求的平均值作为目标时刻预测值；最后，将预测值和估计值作为卡尔曼滤波模型的输入参数，实现对目标时刻出租车乘客需求的预测，同时引入误差反向传播机制，减小下一次预测误差。基于郑州市出租车轨迹数据集，对组合模型与非齐次泊松模型（NHPM）、加权非齐次泊松模型（WNHPM）、支持向量机（SVM）等三种模型进行对比，实验结果显示PKCPM的误差比WNHPM、SVM分别降低了8.85个百分点、14.9个百分点。该模型能对不同时段内、不同空间网格的乘客需求进行预测，为出租车寻找乘客提供可靠的依据。

关键词: 空载率, 卡尔曼滤波预测模型, 加权时变泊松模型, 临近时刻乘客需求

CLC Number:

TP181

SHANG Jiandong, LI Panle, LIU Runjie, LI Runchuan. Recommendation model of taxi passenger-finding locations based on weighted non-homogeneous Poisson model[J]. Journal of Computer Applications, 2018, 38(4): 923-927.

商建东, 李盼乐, 刘润杰, 李润川. 基于加权时变泊松模型的出租车载客点推荐模型[J]. 计算机应用, 2018, 38(4): 923-927.

References

[1] JING W P, HU L K, SHU L, et al. RPR:recommendation for passengers by roads based on cloud computing and taxis traces data[J]. Personal and Ubiquitous Computing, 2016, 20(3):337-347.
[2] LEE J. Traveling pattern analysis for the design of location-dependent contents based on the taxi telematics system[EB/OL].[2017-05-10]. http://www.dbpia.co.kr/Journal/ArticleDetail/NODE01623693.
[3] LI B, ZHANG D Q, SUN L, et al. Hunting or waiting? Discovering passenger-finding strategies from a large-scale real-world taxi dataset[C]//Proceedings of the 2011 IEEE International Conference on Pervasive Computing and Communications Workshops. Piscataway, NJ:IEEE, 2011:63-68.
[4] 唐炉亮,郑文斌,王志强,等.城市出租车上下客的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.)
[5] 程静,刘家骏,高勇.基于时间序列聚类方法分析北京出租车出行量的时空特征[J].地球信息科学学报, 2016, 18(9):1227-1239.(CHENG J, LIU J J, GAO Y. Analyzing the spatio-temporal characteristics of Beijing's OD trip volume based on time series clustering method[J]. Journal of Geo-Information Science, 2016, 18(9):1227-1239.)
[6] SHEN Y, ZHAO L G, FAN J. Analysis and visualization for hot spot based route recommendation using short-dated taxi GPS traces[J]. Information, 2015, 6(2):134-151.
[7] LEE J, SHIN I, PARK G L. Analysis of the passenger pick-up pattern for taxi location recommendation[C]//NCM 2008:Proceedings of the Fourth International Conference on Networked Computing and Advanced Information Management. Piscataway, NJ:IEEE, 2008:199-204.
[8] YUAN J, ZHENG Y, ZHANG L H, et al. T-Finder:a recommender system for finding passengers and vacant taxis[J]. IEEE Transactions on Knowledge & Data Engineering, 2013, 25(10):2390-2403.
[9] YUAN J, ZHENG Y, ZHANG L, et al. Where to find my next passenger[C]//UbiComp 2011:Proceedings of the 13th International Conference on Ubiquitous Computing. New York:ACM, 2011:109-118.
[10] 周春姐,戴鹏飞,王晓玲,等.面向移动用户的乘客需求预测系统[J].计算机研究与发展, 2015, 41(增刊1):143-148.(ZHOU C J, DAI P F, WANG X L, et al. A system of passenger demand prediction for mobile users[J]. Journal of Computer Research and Development, 2015, 41(S1):143-148.)
[11] 王芮.基于GPS数据的城市出租车出行需求研究[D].济南:山东大学, 2016:44-45.(WANG R. Research on urban taxi travel demand based on GPS data[D]. Jinan:Shandong University, 2016:44-45.)
[12] 林永杰, 邹难. 基于运营系统的出租车出行需求短时预测模型[J]. 东北大学学报(自然科学版), 2016, 37(9):1235-1240.(LIN Y J, ZOU N. Short-term prediction model of taxi passenger demand based on operation systems[J]. Journal of Northeastern University (Natural Science), 2016, 37(9):1235-1240.)
[13] 王涛波, 黄宝军. 基于改进卡尔曼滤波的四维飞行航迹预测模型[J]. 计算机应用, 2014, 34(6):1812-1815.(WANG T B, HUANG B J. 4D flight trajectory prediction model based on improved Kalman filter[J]. Journal of Computer Applications, 2014, 34(6):1812-1815.)
[14] 钱文逸, 蒋新华, 廖律超, 等. 基于时空上下文协同过滤的出租车载客点推荐算法[J]. 计算机应用, 2015, 35(6):1659-1662.(QIAN W Y, JIANG X H, LIAO L C, et al. Recommendation algorithm of taxi passenger-finding locations based on spatio-temporal context collaborative filtering[J]. Journal of Computer Applications, 2015, 35(6):1659-1662.)
[15] MOREIRA-MARTIAS L, GAMA J, FERREIRA M, et al. Predicting taxi-passenger demand using streaming data[J]. IEEE Transactions on Intelligent Transportation Systems, 2013, 14(3):1393-1402.
[16] HOU Y, LI X, ZHAO Y, et al. Towards efficient vacant taxis cruising guidance[C]//Proceedings of the 2013 IEEE Global Communications Conference. Piscataway, NJ:IEEE, 2014:54-59.
[17] 张红, 王晓明, 过秀成, 等. 出租车GPS轨迹大数据在智能交通中的应用[J]. 兰州理工大学学报,2016, 42(1):109-114.(ZHANG H, WANG X M, GUO X C, et al. Application of taxi GPS big trajectory data in intelligent traffic system[J]. Journal of Lanzhou University of Technology, 2016, 42(1):109-114.)
[18] 姬波, 叶阳东, 肖煜. 基于信息瓶颈方法的出租车空载聚集区聚类算法[J]. 小型微型计算机系统, 2013, 34(9):2139-2143.(JI B, YE Y D, XIAO Y. Empty taxi areas clustering algorithm based on information bottleneck method[J]. Journal of Chinese Computer Systems, 2013, 34(9):2139-2143.)
[19] 刘大有, 陈慧灵, 齐红, 等. 时空数据挖掘研究进展[J]. 计算机研究与发展, 2013, 50(2):225-239.(LIU D Y, CHEN H L, QI H, et al. Advances in spatiotemporal data mining[J]. Journal of Computer Research and Development, 2013, 50(2):225-239.)
[20] GE Y, XIONG H, ALEXANDER T Z L, et al. An energy-efficient mobile recommender system[C]//KDD 2010:Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2010:899-908.
[21] YUAN J, ZHENG Y, XIE X, et al. Driving with knowledge from the physical world[C]//KDD 2011:Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York:ACM, 2011:316-324.
[22] PHITHAKKITNUKOON S, VELOSO M, BENTO C, et al. Taxi-aware map:identifying and predicting vacant taxis in the city[C]//AmI 2010:Proceedings of the First International Joint Conference on Ambient Intelligence. Berlin:Springer, 2010:86-95.
[23] GUI Z, YU H, TANG Y. Locating traffic hot routes from massive taxi tracks in clusters[J]. Journal of Information Science & Engineering, 2016, 32(1):113-131.
[24] ZHANG D, SUN L, LI B, et al. Understanding taxi service strategies from taxi GPS traces[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(1):123-135.
[25] RAO F, ZHANG X, DONG Y, et al. Understanding the mobility pattern of passenger-searching taxis[C]//Proceedings of the 2014 IEEE 17th International Conference on Intelligent Transportation Systems. Piscataway, NJ:IEEE, 2014:290-295.
[26] QIAO S, HAN N, ZHU W, et al. TraPlan:an effective three-in-one trajectory-prediction model in transportation networks[J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(3):1188-1198.
[27] QIAO S, SHEN D, WANG X, et al. A self-adaptive parameter selection trajectory prediction approach via hidden Markov models[J]. IEEE Transactions on Intelligent Transportation, 2015, 16(1):284-296.
[28] 乔少杰, 韩楠, 李天瑞, 等. 一种基于空间编码技术的轨迹特征提取方法[J]. 中国科学:信息科学, 2017, 47(11):1523-1537.(QIAO S J, HAN N, LI T R, et al. A trajectory feature extraction approach based on spatial coding technique[J]. Chinese Science:Informationis, 2017, 47(11):1523-1537.)
[29] QIAO S, HAN N, WANG J, et al. Predicting long-term trajectories of connected vehicles via the prefix-projection technique[J]. IEEE Transactions on Intelligent Transportation Systems, 2017, PP(99):1-11