基于DP-PSO的车辆GPS轨迹时空自适应离线压缩算法

Vehicle GPS trajectory spatiotemporal adaptive compression based on DP-PSO algorithm

为了尽可能多地保留有效轨迹信息,并更好地平衡有效轨迹信息与全局压缩效率之间的动态关联关系,利用海量移动轨迹数据,提出了一种基于Douglas Peucker-particle swarm optimization(DP-PSO)的车辆GPS轨迹时空自适应离线压缩算法。首先,根据原始轨迹时空特性,在第一阶段利用MDL分割框架对筛选出的有效轨迹进行初步分割,获取表征原始轨迹特性的轨迹分段数;然后,在第二阶段考虑偏移角度、垂直欧氏距离、轨迹分段数等多种影响因素,建立基于DP-PSO的车辆GPS轨迹时空自适应离线压缩算法,动态调整各参数阈值将所有轨迹同化为具有相似特性的一类轨迹簇,建立能够全面反映压缩结果的空间、时间特征的评价指标,实现所有轨迹的全局优化和有效压缩;最后,选择某城市车辆GPS轨迹数据验证本算法的可靠性。结果表明:与经典的TRACLUS算法和新算法TCDP、RSF、Top-Down Time Ratio相比,在轨迹压缩的准确性上,本文算法在保留较多特征轨迹点的同时,也涵盖了较丰富的轨迹信息。在精简性方面,本文算法在轨迹压缩数的平均变化量,相比于其他4种算法分别减少了55.823%、45.802%、50.815%和32.566%。在复杂度方面,本文算法不仅能获得较好的压缩精度,还能在压缩时间上相较于其他4种算法有较大优势,且稳定在101095 ms左右,提升轨迹压缩的整体运行效能。

In order to retain effective trajectory information and balance the dynamic correlation between effective trajectory information and global compression efficiency,the vehicle GPS trajectory spatiotemporal adaptive compression based on Douglas Peucker-particle swarm optimization(DP-PSO)algorithm was proposed by massive GPS trajectory data.According to the spatio-temporal characteristics of original trajectory,MDL segmentation framework was used to preliminarily segment the selected effective trajectory at the first stage.The number of segments representing the characteristics of original trajectory was obtained.At the second stage,the vehicle GPS trajectory spatiotemporal adaptive compression based on DP-PSO algorithm was established by influence factors,such as offset angle,perpendicular euclidean distance,trajectory segmentation and so on.All trajectories clustered into a class of trajectory with similar characteristics by dynamic adjusting for threshold parameters.An evaluation index that can fully reflect the spatial and temporal characteristics of the compression results was built.The global optimization and effective compression of all trajectories were realized.Finally,a vehicle GPS trajectory data selected can verify the reliability of the proposed algorithm.The results show that in the comparison of the classical TRACLUS algorithm,the new TCDP,RSF and Top-Down Time Ratio algorithm,the DPPSO not only retains more characteristic trajectory points,but also covers abundant trajectory information in the accuracy of trajectory compression.In terms of simplification,compared with other four algorithms,the average change variation of trajectory compression with the DP-PSO is reduced by 55.823%,45.802%,50.815%and 32.566%respectively.This improvement brings up advantages in complexity,compression accuracy and stability.The compression time is stable at 101095 ms,improving the overall operation efficiency of trajectory compression.