Top-k hotspots recommendation algorithm based on real-time traffic
-
摘要: 为降低城市出租车的空载率，缓解路网交通拥堵压力，亟需设计有效的出租车载客热门区域推荐方法.针对传统的出租车相关推荐方法忽略实际路况导致推荐精度较低的现状，提出了一个两阶段的载客热门区域实时推荐算法.首先，离线挖掘阶段，基于出租车历史轨迹数据集提取基于时段属性的载客热门区域；随后，在线推荐阶段，根据出租车请求位置及时间，结合实时路况设计潜在空载时间开销函数Tcost对载客热门区域进行评测排序，继而发现Top-k载客热门区域.基于出租车轨迹数据集的实验结果表明，结合实时交通状况的Top-k载客热门区域推荐方法以确保较小潜在空载时间开销，相较于传统的出租车推荐方法具有较好的有效性与鲁棒性.
-
关键词:
- 潜在空载时间开销函数 /
- 实际路况 /
- 热门区域 /
- 推荐
Abstract: To cut down the no-load rate of taxis and relieve the traffic pressure, an effective hotspot recommendation method of picking up passenger is necessitated. Aiming at the problem of lower recommendation precision of traditional recommendation technique due to ignoring the actual road situation, we propose a two-phase real-time hotspot recommendation approach for picking up passenger. In the phase of offline mining, timebased hotspots are extracted by mining the history taxi trajectory dataset. In the phase of online recommendation, according to the position and time of taxi requests, a potential no-passenger time cost evaluation function that based on real-time road situation is presented to evaluate and rank hotspots, and obtain top-k hotspots of picking up passenger.Experimental results on taxi trajectory data show that, our proposal ensure smaller potential no-load time overhead due to considering real-time traffic conditions, and hence has good effectiveness and robustness as compared to the traditional recommendation approached.-
Key words:
- potential no-passenger time cost function /
- real-time traffic /
- hotspot /
- recommendation
-
图 3 北京市机场、火车站、中学区域各时段平均载客频数
Fig. 3 The average passenger frequency of airport, train station and school
图 6 基于位置 $P$ 、时间 $T$ 的载客热门区域top- $k$ 推荐可视化效果图
Fig. 6 The top-k hotspots for taxi based on P and T
Algorithm 1 Hotspot generation algorithm based on improved DBSCAN Input: A list of pick-up locations point pointsList=$\{p_1 ,p_2 ,\cdots ,p_n \}$, MinPts, $\varepsilon _{\rm temporal} ,\varepsilon _{\rm spatio}$ Output: Clustering result clusterList 1: Initialize pointsList(clusterID$\leftarrow$0, isVisited$\leftarrow$false, isNoised$\leftarrow$false); 2: cluster$\_i\leftarrow 1$; 3: for each point $p_i$ in pointsList do 4: if(!$p_i$.isVisited)then 5: $p_i$.isVisited=true; 6: find the Neiborhood points for $p_i$ about $\varepsilon _{\rm temporal}$, $\varepsilon _{\rm spatio}:N_{\varepsilon_{\rm temporal},\varepsilon _{\rm spatio}} p_i$; 7: if$(|N_{\varepsilon _{\rm temporal},\varepsilon _{\rm spatio}} p_i |＜$ MinPts)then 8: $p_i$.isNoised=true; 9: else 10: $p_i$.clusterID=cluster$\_i$; 11: for each point $p'_{i.{\rm adjacent}}$ in $N_{\varepsilon_{\rm temporal} ,\varepsilon _{\rm spatio}}$ $p_i$ do 12: if(!$p'_{i.{\rm adjacent}}$.isVisited)then 13: $p'_{i.{\rm adjacent}}$.isVisited=true; 14: find the Neiborhood points for $p'_{i.{\rm adjacent}}$ about $\varepsilon _{\rm temporal},\varepsilon _{\rm spatio}$: $N_{\varepsilon _{\rm temporal} ,\varepsilon _{\rm spatio}} p'_{i.{\rm adjacent}}$; 15: if($|N_{\varepsilon _{\rm temporal} ,\varepsilon _{\rm spatio}}p'_{i.{\rm adjacent}}|\ge$ MinPts)then 16: $N_{\varepsilon _{\rm temporal},\varepsilon _{\rm spatio}}p_i =N_{\varepsilon _{\rm temporal},\varepsilon _{\rm spatio}}p_i\cup N_{\varepsilon_{\rm temporal} ,\varepsilon _{\rm spatio}}p'_{i.{\rm adjacent}}$; 17: end if 18: end if 19: if($p'_{i.{\rm adjacent}}$.clusterID=0) then 20: $p'_{i.{\rm adjacent}}$.clusterID=cluster$\_i$; 21: if$(p'_{i.{\rm adjacent}}$.isNoised)then 22: $p'_{i.{\rm adjacent}}$.isNoised=false; 23: end if 24: end if 25: end for 26: cluster$\_i$++; 27: end if 28: end if 29: end for 
下载: 导出CSV
表 1 出租车GPS数据格式
Tab. 1 Taxi GPS trajectory data format
数据字段 数据类型 描述(示例) Time char 时间信息(20131023000013) ID char 出租车唯一标识(001141) Longitude float 经度值(116.439 972) Latitude float 纬度值(39.850 876) Speed short 速度值(62.000 000) Direction short 方向信息(170.000 000) Stat char 载客状态(1)
空载状态(0)
下载: 导出CSV
-
[1] CHANG H W, TAI Y C, HSU Y J. Context-aware taxi demand hotspots prediction[J]. International Journal of Business Intelligence and Data Mining, 2010, 5(1):3-18. doi: 10.1504/IJBIDM.2010.030296 [2] LI X L, PAN G, WU Z H, et al. Prediction of urban human mobility using large-scale taxi traces and its applications[J]. Frontiers of Computer Science, 2012, 6(1):111-121. [3] QU M, ZHU H, LIU J, et al. A cost-effective recommender system for taxi drivers[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2014:45-54. [4] YUAN N J, ZHENG Y, ZHANG L, 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. https://users.wpi.edu/~yli15/courses/DS504Fall16/includes/TKDE13.pdf [5] LI B, ZHANG D Q, SUN L, et al. Hunting or waiting? Discovering passenger-finding strategies from a largescale real-world taxi dataset[C]//Proceedings of the Pervasive Computing and Communications Workshops (PERCOM Workshops), 2011 IEEE International Conference on. IEEE, 2011:63-68. [6] MOREIRA-MATIAS 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. doi: 10.1109/TITS.2013.2262376 [7] PHITHAKKITNUKOON S, VELOSO M, BENTO C, et al. Taxi-aware map:Identifying and predicting vacant taxis in the city[C]//AmI'10 Proceedings of the First International Joint Conference on Ambient Intelligence. 2010:86-95. [8] 齐观德, 潘遥, 李石坚, 等.基于出租车轨迹数据挖掘的乘客候车时间预测[J].软件学报, 2013, 24(2):14-23. http://cpfd.cnki.com.cn/Article/CPFDTOTAL-JDMT201211003002.htm [9] MAO J L, SONG Q G, JIN C Q, et al. TSCluWin:Trajectory stream clustering over sliding window[C]//DASFAA 2016:Database Systems for Advanced Applications. 2016:133-148. [10] WANG Z C, LU M, YUAN X R, et al. Visual traffic jam analysis based on trajectory data.[J]. IEEE Transactions on Visualization & Computer Graphics, 2013, 19(12):2159-2168. https://www.narcis.nl/publication/RecordID/oai%3Alibrary.tue.nl%3A770083 [11] HAN B, LIU L, OMIECINSKI E. Road-network aware trajectory clustering:Integrating locality, flow, and density[J]. IEEE Transactions on Mobile Computing, 2015, 14(2):416-429. doi: 10.1109/TMC.2013.119 [12] GRAHAM R L. An efficient algorith for determining the convex hull of a finite planar set[J]. Information Processing Letters, 1972, 4(1):132-133. https://www.cise.ufl.edu/~sitharam/COURSES/CG/Graham2.pdf [13] DIJKSTRA E D. A note on two problem in connexion with graphs[J]. Numerische Mathematik, 1959(1):269-271. http://jmvidal.cse.sc.edu/lib/dijkstra59a.html [14] MITCHELL T, BUCHANAN B, DEJONG G, et al. Machine learning[J]. Annual Review of Computer Science, 1990(4):417-433. -
点击查看大图
图(10) / 表(2)
计量
- 文章访问数: 156
- HTML全文浏览量: 88
- PDF下载量: 265
- 被引次数: 0