改进DBSCAN算法下的轨迹点到充电站位置的探测方法

Detection method of trace points of charging station location under improved DBSCAN algorithm

在当前新能源汽车快速发展的背景下,针对相关充电设施位置信息更新缓慢等问题,如何通过第三方数据得到工作状态正常的充电站点分布具有重要意义。本文分析了新能源汽车充电停留轨迹数据的典型特征,并基于这些特征构建了时空关联静动(Stop/Move)模型。利用新能源汽车轨迹数据作为数据源,采用具有噪声的基于密度的聚类(DBSCAN)算法来检测满足充电停留点的点簇,并进一步探测充电站的位置。同时,针对DBSCAN算法具有高时间复杂度的问题,通过构建K维空间树(KD树)数据结构提高了算法执行效率;针对不同参数会影响DBSCAN算法聚类结果的问题,运用邻域参数自适应优化方法提升了轨迹点的聚类效果。利用深圳市的新能源车轨迹数据进行实验分析,结果表明,相比原始DBSCAN算法和k均值聚类(K-MEANS)算法,改进DBSCAN算法提高了算法执行效率,对真实充电站点探测成功率较高。

It is of great importance to obtain the distribution of functioning charging stations through third-party data,given the current rapid development of new energy vehicles and the corresponding lack of basic charging facilities and monitoring.In this study,the typical characteristics of new energy vehicle charging and stopping trajectory data were analyzed and a Stop/Move model was constructed based on these features.Taking new energy vehicle trajectory data as the data source,the density-based spatial clustering of applications with noise(DBSCAN)algorithm were applied to detect point clusters that satisfied charging and stopping points and further detected the location of charging stations.To address the high time complexity of the DBSCAN algorithm,a k-dimensional(KD)-tree data structure was constructed to improve algorithm performance.To address the problem of different parameters affecting the clustering results of the DBSCAN algorithm,an adaptive optimization method were applied for neighborhood parameters to improve the clustering effect of trajectory points.Experimental analysis was conducted using the trajectory data of new energy vehicles in Shenzhen,and the results showed that the improved DBSCAN algorithm improved algorithm performance.This method had a higher success rate in detecting real charging stations compared with other clustering algorithms.