随着时代的进步，物流行业的快速发展增加了货运需求，仅依靠人力来记录货运行程数据的时间成本高。

 

而空间定位技术和无线技术不断进步和普及，越来越多的货运卡车已经配备了用于定位和导航的GPS设备，通过GPS设备采集了海量的车辆轨迹数据，数据中包含大量的车辆运行信息，利用数据挖掘技术从轨迹数据中提取有效信息是近年来研究的难点。

数据挖掘是指从海量的、有噪声的原始数据中获取有效信息的一种数据处理方式。轨迹数据应用领域非常广泛，例如可以利用历史数据对当前轨迹位置进行预测。

可以将数据用于城市不同时间交通状况的监测；可以通过车辆轨迹数据对一个城市的货运量进行分析；可以分析人们出行模式并由此推荐出行路径等。

基于轨迹数据识别异常装卸点

 

在物流运输过程中，司机偷窃货物和私下拉货等异常行为检测成为物流行业的一大难题，因此本文利用对车辆异常行为检测问题进行研究。

传统异常行为检测问题都是基于车辆轨迹异常来判断，大多数现有的轨迹异常检测算法都是针对单次行程较短的出租车。

但重型卡车一般路程较长且复杂，使得异常轨迹检测困难且准确率较低。

因此有些学者选择先将轨迹划分为许多子轨迹，再进行异常检测，但这些方法也有很多不合理的地方，如：由于重型卡车行程较长，不同的司机可能习惯走不同的路线，所以就算轨迹不同也不一定说明车辆行为异常。

 

一般利用速度阈值和驾驶方向变化将轨迹分为子轨迹，而这样所有车辆得到的子轨迹的起点和终点不一定是相同的，会给异常检测带来很大的困难，使检测结果误差较大。

当异常行为出现在经常行驶的路线中时，传统方法难以将其识别出来。研究表明车辆异常行为可以通过异常停车表现出来。

所以本文基于货车轨迹大数据提出一种识别异常装卸（originsanddestinations,OD）点的方法，主要包括两部分。

先从轨迹点中识别OD点，再从OD点中进行异常检测。这样可以把异常轨迹识别问题转化为异常OD点识别问题，避免上述不合理的地方。

基于孤立森林识别异常OD点

 

异常点识别有多种方法，例如基于分类、聚类等的异常点识别方法，但它们都是将不符合正常数据特征识别为异常。

而孤立森林算法是利用异常数据的定量属性（即异常点是少数且其属性值与正常实例的属性值非常不同）来识别异常点，具有准确性高、效率高的优点，适用于大数据的异常点识别问题。

iForest类似于决策树和随机森林，由孤立树（iTree）组成，但由于不需要计算距离和密度，故只具有线性时间复杂度，因此本文借鉴iForest检测异常OD点。

iForest的异常检测包含两个阶段。第一阶段使用训练集的样本构建包含t个孤立树的孤立森林；第二阶段利用孤立森林来获取每个实例的异常得分，识别异常点。

 

结果分析

iForest中的参数α为异常点的占比，经试验α=0.03时检测效果最好。下图为异常OD点识别情况，由图可知车辆基本在包头-天津的路线上进行货运活动。

图中的每一个点代表卡车的一个OD点，共有1796个。其中，蓝点代表正常OD点，红点代表异常OD点，异常点的检测结果如下图所示。

 

改进算法的基本思想

尽管Yang在2009年提出布谷鸟算法时候指出算法不必为特定问题微调算法中的参数，布谷鸟算法与其他元启发式算法相比更具通用性和鲁棒性。

但是后续的大部分文献都在算法改进中会对参数进行调整，同时也通过实验证实参数的调整是可以改变算法的收敛速度。

而且很多文献都证实了将布谷鸟算法和其他元启发式方法相结合，可以改进布谷鸟算法的搜索效率，在提升搜索的收敛速度的同时又避免陷入局部最优解。

在随机搜索的元启发式算法中，如何达到探索能力和开发能力的平衡，是一个一直值得探究的问题。

同时从上述文献的分析中可以看出，布谷鸟算法的缺点在于，虽然levy飞行中随机分布的重尾性导致从概率意义上可以保证全局搜索，但是因为信息共享机制的引入加快了收敛速度的同时也导致容易陷入局部最优解。

 

在各种单种群的布谷鸟算法改进中，有好些已经对相关的全局搜索策略和局部搜索策略的改进以及变得异常复杂，而其中的也变得越来越难以琢磨。

因此有必要设计一个相对比较简单，而又可以很好的达到探索能力和开发能力的平衡，并且这一机制也容易识别和设计的算法。

随机系统耦合指出，分组有助于提高CS算法的性能。孤岛模型结合布谷鸟算法的实验结果也佐证了分种群的方法可以提升算法的性能。

因此，算法设计上，可以借鉴孤岛模型，让两个种群分别用不同的搜索策略进行搜索，但是在两个种群中搜索的策略有所侧重。

种群一注重全局搜索，种群二注重局部搜索，同时选择一定的策略对两个种群的信息进行共享。

 

从中可以看出，两个种群中选择最优解与最次解的交换替代，将会不减少勘探能力的同时，提升在代际最优解周围的开发能力。

因此有必要选择在两个种群独立运行一定代数后进行解的交换替代；在每个种群中的搜索策略的选择要根据各自的侧重情况进行选择，子种群中的算法参数的设计可以不需要很复杂。

另一方面，初始种群的情况也会影响算法的性能，种群的多样性越好，越不容易陷入局部最优解。

而混沌运动具有一定的不确定性、遍历性和随机性，可以在一定范围内均匀分布。

因此，越来越多的研究人员利用混沌遍历性的特点，来降低启发式优化算法的随机性，尤其是将其应用到初始种群的产生上，可以很好的确保初始种群的多样性。

 

基于以上分析,本文提出一种基于双种群的布谷鸟搜索算法。

为了验证算法的有效性，选取了多个不同类型的测试函数及多个算法进行仿真实验对比分析，实验结果表明DPCS可以提高算法的寻优精度，验证了改进算法的优越性。

基于双种群的布谷鸟改进算法

基于改进思想对CS算法进行以下改进，首先用tent混沌映射初始化种群，并且提出非线性递减的自适应步长因子。

其次借鉴粒子群算法改进算法的位置更新方法（Particle-CuckooSearchAlgorithm,PCS）。

最后提出双种群策略，种群一扩大搜索范围，提升算法的开发能力，另一个种群侧重在局部最优解周围进行搜索，增强探索能力。并且当种群迭代到一定次数时进行信息共享，提高算法收敛精度。

 

DPCS在路径规划问题中的应用

随着时代的发展，物流行业也获得高速发展，货物配送需求逐渐提升。因此对于物流公司来说，如何找到最优的货物配送路径，削减配送成本至关重要。

物流行业中的货物配送问题，旨在从多条配送路径中找寻出最优规划，提升货物的配送效率。起初学者将各种精确算法用来解决该问题。

但随着实际问题越来越复杂，此类算法寻优效果并不理想。随着越来越多的启发式算法出现，许多学者采用了目前处于快速发展中的智能算法，求解路径规划中的近似最优解。

目前将智能优化算法用于求解路线规划问题都取得了不错的优化效果，同时布谷鸟搜索算法也在求解路线规划问题中大放异彩。

 

因此，本文将基于CS算法改进的DPCS算法用于配送货物的路径规划问题中，利用生活中的实际问题检测算法的可行性。

实验结果分析

利用CS、PSO、PCS和DPCS算法在路径规划问题中进行对比实验，通过实验结果可以更全面的验证改进算法的可行性。实验中所用的配送点为第二章中识别出的20个某公司的实际装卸点，配送点地址及经纬度坐标数据如表所示。

 

在实验过程中，算法的种群大小均为n=20，最高迭代代数为1500maxt，上述四种算法各自独立运行20次。

记录每种算法的平均值、最短路径和最优路径，实验结果如表所示，加粗数据为最优解，并展示最优路径规划，其中红点代表配送点，蓝线表访问路线，红线连接起始配送点和最终配送点。

由于两个经纬度坐标之间的距离跟纬度有关，在二维坐标轴上显示会有较大偏差，故在实际地图上进行可视化。

 

从实验结果表和图中可以看出，PCS在一定程度上是优于CS和PSO的，证明借鉴粒子群思想的改进策略能够进一步提高CS算法的求解精度。

而DPCS算法由于采用双种群策略，大大提高了算法的收敛速度和精度，故规划的路径长度相较于其它三种算法缩短了很多。

相比PSO算法规划的最优路径更是缩短了将近三分之一的路程，减少了很多不必要的绕路。综上所述，DPCS算法在路径规划问题中也有较好的寻优性能。

结语

提出一种基于重型卡车轨迹数据识别异常OD点方法。不同于传统的方法将整条路径作为一个对象进行分析。

 

本文运用离散思维先对轨迹点进行聚类识别出有效的OD点，然后用孤立森林算法识别异常OD点，最后以包钢集团的车辆轨迹数据进行实证分析，结果表明此方法可以有效识别异常OD点。

基于双种群策略的DPCS改进算法。首先，由于混沌映射的随机性和遍历性，利用tent混沌映射初始化种群，使初始种群能够均匀的分布在解空间中。

其次，步长因子的大小能够影响莱维飞行的结果，本文提出非线性递减的自适应步长因子代替固定取值的步长因子，使算法搜索前期步长较大注重全局搜索，从而加快收敛速度。

搜索后期靠近最优解，此时步长较小注重局部搜索，从而提高寻搜精度。然后，借鉴PSO算法的自我学习和社会学习思想改进个体位置更新公式。

最后，采用双种群策略，种群一借鉴PSO算法更注重局部搜索，种群二为CS算法更注重全局搜索，使得改进算法能够更好的平衡探索能力和开发能力。

当两个种群迭代一个周期次数cycle时对种群进行交换操作，淘汰种群中较差的解，吸收对方种群较好的解，能够有效提高算法的收敛速度和搜索精度。