基于D-OPTICS算法的网约车载客热点区域挖掘

王璐瑶; 邬岚; 杨晟; 朱兴贝

doi:10.13700/j.bh.1001-5965.2022.0008

基于D-OPTICS算法的网约车载客热点区域挖掘

doi: 10.13700/j.bh.1001-5965.2022.0008

南京林业大学汽车与交通工程学院，南京 210037

基金项目: 国家自然科学基金(51408314)；江苏省研究生科技创新计划(SJCX20_0278)

详细信息

通讯作者:
E-mail：wulan@njfu.edu.cn

中图分类号: U495
计量
- 文章访问数: 114
- HTML全文浏览量: 33
- PDF下载量: 7
- 被引次数: 0
出版历程
- 收稿日期: 2022-01-08
- 录用日期: 2022-03-18
- 网络出版日期: 2022-03-25
- 整期出版日期: 2023-11-30

Hot spots areas mining of online ride-hailing based on D-OPTICS algorithm

College of Automobile and Traffic Engineering，Nanjing Forestry University，Nanjing 210037，China

Funds: National Natural Science Foundation of China(51408314)；Graduate Student Scientific Research Innovation Projects in Jiangsu Province(SJCX20_0278)

More Information

Corresponding author: E-mail：wulan@njfu.edu.cn

摘要

摘要:
为准确分析网约车载客高需求热点区域，考虑载客热点聚类中车辆行驶距离的约束，采用结合Dijkstra寻路算法的OPTICS算法，提出寻路密度OPTICS（D-OPTICS）算法。D-OPTICS算法利用车辆轨迹数据进行空间聚类研究分析载客热点区域。通过道路网络拓扑结构提取各路段节点，采用Dijkstra算法进行寻路并以路段为单位提取邻域范围内载客点进行聚类。将成都市网约车轨迹数据进行热点区域的挖掘和分析。与传统OPTICS算法相比，所提算法考虑了道路距离的约束，提高了载客热点聚类稳定性和精度，获取的载客热点区域更贴合实际情况。
- 数据挖掘 /
- 载客热点 /
- OPTICS算法 /
- 车辆轨迹 /
- Dijkstra算法
Abstract:
Dijkstra ordering points to identify the OPTICS algorithm based on the Dijkstra routing algorithm is proposed to accurately analyze the hot spots areas with high passenger demand for online ride-hailing, which performs a spatial clustering analysis of high passenger demand hot spots areas using vehicle trajectory data. This analysis takes into account the restriction of the road topological structure on the driving distance of vehicles. The Dijkstra algorithm is used to discover the road, and the road network is utilized to extract the passenger spots in the neighborhood for the clustering as well as to produce the road nodes connecting each road segment. Finally, the hot spots areas are mined and analyzed based on the trajectory data of online car-hailing in Chengdu. Compared with the traditional ordering points to identify the OPTICS algorithm, the proposed algorithm takes into account the road space restriction and has higher precision and stability of hot spots areas for carrying passengers, the hot spots areas of carrying passengers are closer to the actual situation.
- data mining /
- passenger hotspots /
- OPTICS algorithm /
- vehicle trajectory /
- Dijkstra algorithm

HTML全文

图 1 各种距离度量示意图

Figure 1. schematic diagram of various distance measures

下载: 全尺寸图片幻灯片

图 2 带权无向图邻接表示意图

Figure 2. Schematic diagram of adjacency list of weighted undirected graph

下载: 全尺寸图片幻灯片

图 3 Dijkstra寻路结果邻接表示意图

Figure 3. Schematic diagram Dijkstra pathfinding result adjacency list

下载: 全尺寸图片幻灯片

图 4 D-OPTICS算法相关概念图示

Figure 4. D-OPTICS algorithm related concept diagram

下载: 全尺寸图片幻灯片

图 5 邻域内载客点提取流程

Figure 5. Flow of selection of pick-up points in Eps

下载: 全尺寸图片幻灯片

图 6 基于D-OPTICS算法的载客热点挖掘思路

Figure 6. Mind map of passenger hot spots mining on D-OPTICS algorithm

下载: 全尺寸图片幻灯片

图 7 OPTICS算法与D-OPTICS算法聚类稳定性比较

Figure 7. Comparison of clustering stability between OPTICS algorithm and D-OPTICS algorithm

下载: 全尺寸图片幻灯片

图 8 OPTICS算法改进前后可达图（m=40，$ \varepsilon $不限）

Figure 8. OPTICS algorithm improvements before and after reachable graph (m = 40, $ \varepsilon $ is not limited)

下载: 全尺寸图片幻灯片

图 9 OPTICS算法与D-OPTICS算法聚类效果（$ \varepsilon $=100 m，m=40）

Figure 9. OPTICS algorithm and D-OPTICS algorithm cluster result diagram ($ \varepsilon $= 100 m, m= 40)

下载: 全尺寸图片幻灯片

表 1 OPTICS算法与D-OPTICS算法轮廓系数

Table 1. OPTICS algorithm and D-OPTICS algorithm profile coefficient

ε/m	m	轮廓系数
ε/m	m	OPTICS算法	D-OPTICS算法
60	20	0.721	0.742
	30	0.815	0.816
	40	0.847	0.855
80	20	0.416	0.627
	30	0.563	0.674
	40	0.725	0.779
100	20	0.273	0.592
	30	0.498	0.651
	40	0.671	0.736
120	20	0.224	0.412
	30	0.347	0.584
	40	0.413	0.723
140	20	−0.113	0.326
	30	0.104	0.538
	40	0.196	0.719

下载: 导出CSV

参考文献(21)

[1]	吴华意, 黄蕊, 游兰, 等. 出租车轨迹数据挖掘进展[J]. 测绘学报, 2019, 48(11): 1341-1356. WU H Y, HUANG R, YOU L, et al. Recent progress in taxi trajectory data mining[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(11): 1341-1356(in Chinese).
[2]	郑林江, 赵欣, 蒋朝辉, 等. 基于出租车轨迹数据的城市热点出行区域挖掘[J]. 计算机应用与软件, 2018, 35(1): 1-8. doi: 10.3969/j.issn.1000-386x.2018.01.001 ZHENG L J, ZHAO X, JIANG C H, et al. Mining urban attractive areas using taxi trajectory data[J]. Computer Applications and Software, 2018, 35(1): 1-8(in Chinese). doi: 10.3969/j.issn.1000-386x.2018.01.001
[3]	王郑委. 基于大数据Hadoop平台的出租车载客热点区域挖掘研究[D]. 北京: 北京交通大学, 2016. WANG Z W. Research on mining taxi pick-up hotspots area based on big data hadoop platform[D]. Beijing: Beijing Jiaotong University, 2016 (in Chinese).
[4]	苗星至. 基于GPS数据的出租车需求热点分析与寻客驾驶方案推荐研究[D]. 大连: 大连理工大学, 2019. MIAO X Z. Taxi demand hotspot analysis and passenger-seeking driving scheme recommendation based on GPS data[D]. Dalian: Dalian University of Technology, 2019(in Chinese).
[5]	PALMA A T, BOGORNY V, KUIJPERS B. A clustering-based approach for discovering interesting places in trajectories[C]//Proceedings of the 2008 ACM Symposium on Applied Computing. New York: ACM, 2008: 863-868.
[6]	LIU Y, LIU J, WANG J, et al. Recommending a personalized sequence of pick-up points[J]. Journal of Computational Science, 2018(28): 382-388.
[7]	杨树亮, 毕硕本, 黄铜, 等. 一种出租车载客轨迹空间聚类方法[J]. 计算机工程与应用, 2018, 54(14): 249-255. doi: 10.3778/j.issn.1002-8331.1703-0189 YANG S L, BI S B, HUANG T, et al. Spatial clustering method for taxi passenger trajectory[J]. Computer Engineering and Applications, 2018, 54(14): 249-255(in Chinese). doi: 10.3778/j.issn.1002-8331.1703-0189
[8]	王明. 基于出租车GPS数据的载客热点可视化的研究与应用[D]. 太原: 中北大学, 2018. WANG M. Research and application of passenger hot spot visualization based on taxi GPS data[D]. Taiyuan: North University of China, 2018 (in Chinese).
[9]	LUO T, ZHENG X, XU G, et al. An improved DBSCAN algorithm to detect stops in individual trajectories[J]. ISPRS International Journal of Geo-Information, 2017, 6(3): 63. doi: 10.3390/ijgi6030063
[10]	江慧娟, 余洋. 出租车载客热点精细提取的改进DBSCAN算法[J]. 地理空间信息, 2017, 15(10): 16-20. JIANG H J, YU Y. Improved DBSCAN algorithm for fine extraction of hot spots of taxi passengers[J]. Geospatial Information, 2017, 15(10): 16-20(in Chinese).
[11]	黄子赫, 高尚兵, 潘志庚, 等. 基于快速密度聚类的载客热点可视化分析方法[J]. 系统仿真学报, 2019, 31(7): 1429-1438. HUANG Z H, GAO S B, PAN Z G, et al. Visualization analysis method of passenger hot spots based on fast density clustering[J]. Journal of System Simulation, 2019, 31(7): 1429-1438(in Chinese).
[12]	GE Y, XIONG H, TUZHILIN A, et al. An energy-efficient mobile recommender system[C]//Proceedings of the 16th ACM International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2010: 899-908.
[13]	田智慧, 马占宇, 魏海涛. 基于密度核心的出租车载客轨迹聚类算法[J]. 计算机工程, 2021, 47(2): 133-138. TIAN Z H, MA Z Y, WEI H T. Taxi passenger trajectory clustering algorithm based on density core[J]. Computer Engineering, 2021, 47(2): 133-138(in Chinese).
[14]	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. doi: 10.3390/info6020134
[15]	林翊钧, 吴凤鸽, 赵军锁. 基于图像分割和密度聚类的遥感动目标分块提取[J]. 北京航空航天大学学报, 2018, 44(12): 2510-2520. LIN Y J, WU F G, ZHAO J S. Image segmentation and density clustering for moving object patches extraction in remote sensing image[J]. Journal of Beijing University of Aeronautics and Astronautics, 2018, 44(12): 2510-2520(in Chinese).
[16]	孙文财, 杨志发, 李世武, 等. 面向驾驶员注视区域划分的DBSCAN-MMC方法[J]. 浙江大学学报(工学版), 2015, 49(8): 1455-1461. SUN W C, YANG Z F, LI S W, et al. Driver fixation area division oriented DBSCAN-MMC method[J]. Journal of Zhejiang University (Engineering Science), 2015, 49(8): 1455-1461(in Chinese).
[17]	姚锐. 基于出租车轨迹的热点区域挖掘及应用研究[D]. 北京: 北京工业大学, 2019. YAO R. Research on mining and application of hot spots based on taxi trajectory[D]. Beijing: Beijing University of Technology, 2019 (in Chinese).
[18]	鲍冠文, 刘小明, 蒋源, 等. 基于改进DBSCAN算法的出租车载客热点区域挖掘研究[J]. 交通工程, 2019, 19(4): 62-69. BAO G W, LIU X M, JIANG Y, et al. Research on mining taxi pick-up hotspots area[J]. Journal of Transportation Engineering, 2019, 19(4): 62-69(in Chinese).
[19]	ZHANNG Y, HAN L D, KIM H. Dijkstra's-DBSCAN: Fast, accurate, and routable density based clustering of traffic incidents on large road network[J]. Transportation Research Record: Journal of the Transportation Research Board, 2018, 2672(45): 265-273. doi: 10.1177/0361198118796071
[20]	刘国华. 基于Dijkstra距离的聚类算法研究及其在物流中的应用[D]. 兰州: 兰州大学, 2011. LIU G H. An Dijkstra distance-based clustering algorithm and application in logistics[D]. Lanzhou: Lanzhou University, 2011 (in Chinese).
[21]	LU Y L, WEI J S, LI S Y, et al. A K-means clustering optimization algorithm for spatiotemporal trajectory data[C]//International Conference on Human Centered Computing. Berlin: Springer, 2020: 103-113.