巡检路径规划方法、系统、计算机设备及存储介质

摘要

本方案涉及一种巡检路径规划方法、系统、计算机设备及存储介质。所述方法包括：获取巡检数据，并根据所述巡检数据基于距离的类间类内划分指标BWP计算出聚类数量；根据所述巡检数据、所述聚类数量，通过K‑Means算法划分巡检区域，得到各个初始巡检区域；计算各个所述初始巡检区域的工作量，根据各个所述工作量对各个所述初始巡检区域进行二次划分，得到各个目标巡检区域；对各个所述目标巡检区域，通过蚁群算法和遗传算法进行路径规划。基于BWP和K‑Means算法对大规模输电线路巡检区域进行区域划分，并对巡检区域进行调整，再结合蚁群算法和遗传算法对各区域内最优路径进行求解，可以提高最优路径算法求解效率，并平衡各个无人机的工作量。

权利要求

1.一种巡检路径规划方法，其特征在于，所述方法包括：

获取巡检数据，并根据所述巡检数据基于距离的类间类内划分指标BWP计算出聚类数量；

根据所述巡检数据、所述聚类数量，通过K‑Means算法划分巡检区域，得到各个初始巡检区域；

计算各个所述初始巡检区域的工作量，根据各个所述工作量对各个所述初始巡检区域进行二次划分，得到各个目标巡检区域；

对各个所述目标巡检区域，通过蚁群算法和遗传算法进行路径规划；

所述计算各个所述初始巡检区域的工作量，根据各个所述工作量对各个所述初始巡检区域进行二次划分，包括：计算各个所述初始巡检区域的工作量并进行排序，计算最大工作量与最小工作量的差值，若所述差值大于工作量阈值，则将最大工作量对应的初始巡检区域中距离初始聚类中心的最远数据点移除，并将所述最远数据点添加至与所述初始聚类中心距离第二小的类中；当存在有最大工作量大于最大工作量阈值的初始巡检区域时，计算所述初始巡检区域内各个数据点到所述初始聚类中心的第一距离，并计算各个数据点到其他初始聚类中心的第二距离，根据所述第一距离、所述第二距离移动数据点；计算各个所述初始巡检区域工作量与所有区域中最大工作量的比值，并根据所述比值移动数据点。

2.根据权利要求1所述的巡检路径规划方法，其特征在于，所述根据所述巡检数据、所述聚类数量，通过K‑Means算法划分巡检区域，包括：基于所述巡检数据中的单个数据对象，计算出各个所述单个数据对象的各个BWP指标值；

根据各个所述BWP指标值计算出平均BWP值；

根据所述平均BWP值从所述聚类数量中确定最佳聚类数据；

根据所述巡检数据、所述最佳聚类数量，通过K‑Means算法划分巡检区域。

3.根据权利要求2所述的巡检路径规划方法，其特征在于，所述通过K‑Means算法划分巡检区域，得到各个初始巡检区域，包括：根据所述最佳聚类数量，通过K‑Means算法从所述巡检数据的各个数据点中确定各个初始聚类中心；

计算各个剩余数据点到各个所述初始聚类中心的距离，并根据所述距离将各个所述剩余数据点划分到各个所述初始聚类中心所属类中；

判断各个所述初始聚类中心是否收敛，若是，则输出分类结果，并根据所述分类结果划分巡检区域，得到各个初始巡检区域。

4.根据权利要求1所述的巡检路径规划方法，其特征在于，在通过蚁群算法和遗传算法进行路径规划前，所述方法还包括：采用蚁群算法生成初始种群，对所述蚁群算法的参数进行初始化；

构建所述蚁群算法的解空间，初始化蚂蚁的位置；

对蚂蚁进行随机分配，更新信息素，计算蚂蚁遍历的路径；

将迭代一次的路径作为遗传算法的初始种群。

5.根据权利要求4所述的巡检路径规划方法，其特征在于，在通过蚁群算法和遗传算法进行路径规划前，所述方法还包括：设置所述遗传算法的参数，并对所述遗传算法进行初始化；

其中，初始化参数包括种群规模、交叉概率、变异概率以及迭代次数。

6.根据权利要求5所述的巡检路径规划方法，其特征在于，通过蚁群算法和遗传算法进行路径规划，包括：通过所述遗传算法对所述初始种群中的染色体进行交叉、变异操作；

所述染色体进行解码操作，得到配送路径的规划和划分结果；

获取所述初始种群中每个个体的适应度值，采用轮盘赌的方式选择优秀的个体进入下一代；

采用变规模种群规模遗传算法，对种群规模进行调整；

当所述遗传算法达到最大的迭代次数时，则结束算法，输出最短的配送路径。

7.一种巡检路径规划系统，其特征在于，所述系统包括：

聚类数量计算模块，用于获取巡检数据，并根据所述巡检数据基于距离的类间类内划分指标BWP计算出聚类数量；

初始巡检区域划分模块，用于根据所述巡检数据、所述聚类数量，通过K‑Means算法划分巡检区域，得到各个初始巡检区域；

巡检区域调整模块，用于计算各个所述初始巡检区域的工作量，根据各个所述工作量对各个所述初始巡检区域进行二次划分，得到各个目标巡检区域；包括：计算各个所述初始巡检区域的工作量并进行排序，计算最大工作量与最小工作量的差值，若所述差值大于工作量阈值，则将最大工作量对应的初始巡检区域中距离初始聚类中心的最远数据点移除，并将所述最远数据点添加至与所述初始聚类中心距离第二小的类中；当存在有最大工作量大于最大工作量阈值的初始巡检区域时，计算所述初始巡检区域内各个数据点到所述初始聚类中心的第一距离，并计算各个数据点到其他初始聚类中心的第二距离，根据所述第一距离、所述第二距离移动数据点；计算各个所述初始巡检区域工作量与所有区域中最大工作量的比值，并根据所述比值移动数据点；

路径规划模块，用于对各个所述目标巡检区域，通过蚁群算法和遗传算法进行路径规划。

8.一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，其特征在于，所述处理器执行所述计算机程序时实现权利要求1至6中任一项所述方法的步骤。

9.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时实现权利要求1至6中任一项所述的方法的步骤。

说明书

巡检路径规划方法、系统、计算机设备及存储介质

技术领域

[0001] 本发明涉及输电线路巡检技术领域，特别是涉及一种巡检路径规划方法、系统、计算机设备及存储介质。

背景技术

[0002] 输电线路是电力系统的重要组成部分，其安全运行是系统整体稳定的重要保障。为了保证输电线路稳定安全的运行，需要对输电线路进行定期巡检。输电线路的日常巡检是保障供电可靠的一项基础而重要的工作。目前，创建的输电线路巡检方式有人工巡检、无人机巡检和车辆巡检等方式，且近年来，由于无人机(UAV)的快速发展，且其具有较好地灵活性和可控性，输电线路中多采用UAV完成日常巡检任务。无人机在进行输电线路巡检的过程中，由于输电线路巡检区域范围一般较大，不同的无人机巡检组所需要的巡检时间各不相同。

[0003] 因此，传统的无人机进行输电线路巡检时，在求解最优路径过程中，不同无人机巡检组巡检路径所需的工作时间可能差异较大，存在各无人机巡检组工作量不平衡的问题。

发明内容

[0004] 基于此，为了解决上述技术问题，提供一种巡检路径规划方法、系统、计算机设备及存储介质，可以调整巡检区域，平衡各个无人机的工作量。

[0005] 一种巡检路径规划方法，所述方法包括：

[0006] 获取巡检数据，并根据所述巡检数据基于距离的类间类内划分指标BWP计算出聚类数量；

[0007] 根据所述巡检数据、所述聚类数量，通过K‑Means算法划分巡检区域，得到各个初始巡检区域；

[0008] 计算各个所述初始巡检区域的工作量，根据各个所述工作量对各个所述初始巡检区域进行二次划分，得到各个目标巡检区域；

[0009] 对各个所述目标巡检区域，通过蚁群算法和遗传算法进行路径规划。

[0010] 在其中一个实施例中，所述根据所述巡检数据、所述聚类数量，通过K‑Means算法划分巡检区域，包括：

[0011] 基于所述巡检数据中的单个数据对象，计算出各个所述单个数据对象的各个BWP指标值；

[0012] 根据各个所述BWP指标值计算出平均BWP值；

[0013] 根据所述平均BWP值从所述聚类数量中确定最佳聚类数据；

[0014] 根据所述巡检数据、所述最佳聚类数量，通过K‑Means算法划分巡检区域。

[0015] 在其中一个实施例中，所述通过K‑Means算法划分巡检区域，得到各个初始巡检区域，包括：

[0016] 根据所述最佳聚类数量，通过K‑Means算法从所述巡检数据的各个数据点中确定各个初始聚类中心；

[0017] 计算各个剩余数据点到各个所述初始聚类中心的距离，并根据所述距离将各个所述剩余数据点划分到各个所述初始聚类中心所属类中；

[0018] 判断各个所述初始聚类中心是否收敛，若是，则输出分类结果，并根据所述分类结果划分巡检区域，得到各个初始巡检区域。

[0019] 在其中一个实施例中，所述计算各个所述初始巡检区域的工作量，根据各个所述工作量对各个所述初始巡检区域进行二次划分，包括：

[0020] 计算各个所述初始巡检区域的工作量并进行排序，计算最大工作量与最小工作量的差值，若所述差值大于工作量阈值，则将最大工作量对应的初始巡检区域中距离所述初始聚类中心的最远数据点移除，并将所述最远数据点添加至与所述初始聚类中心距离第二小的类中；

[0021] 当存在有最大工作量大于最大工作量阈值的初始巡检区域时，计算所述初始巡检区域内各个数据点到所述初始聚类中心的第一距离，并计算各个数据点到其他初始聚类中心的第二距离，根据所述第一距离、所述第二距离移动数据点；

[0022] 计算各个所述初始巡检区域工作量与所有区域中最大工作量的比值，并根据所述比值移动数据点。

[0023] 在其中一个实施例中，在通过蚁群算法和遗传算法进行路径规划前，所述方法还包括：

[0024] 采用蚁群算法生成初始种群，对所述蚁群算法的参数进行初始化；

[0025] 构建所述蚁群算法的解空间，初始化蚂蚁的位置；

[0026] 对蚂蚁进行随机分配，更新信息素，计算蚂蚁遍历的路径；

[0027] 将迭代一次的路径作为遗传算法的初始种群。

[0028] 在其中一个实施例中，在通过蚁群算法和遗传算法进行路径规划前，所述方法还包括：

[0029] 设置所述遗传算法的参数，并对所述遗传算法进行初始化；

[0030] 其中，初始化参数包括种群规模、交叉概率、变异概率以及迭代次数。

[0031] 在其中一个实施例中，通过蚁群算法和遗传算法进行路径规划，包括：

[0032] 通过所述遗传算法对所述初始种群中的染色体进行交叉、变异操作；

[0033] 所述染色体进行解码操作，得到配送路径的规划和划分结果；

[0034] 获取所述初始种群中每个个体的适应度值，采用轮盘赌的方式选择优秀的个体进入下一代；

[0035] 采用变规模种群规模遗传算法，对种群规模进行调整；

[0036] 当所述遗传算法达到最大的迭代次数时，则结束算法，输出最短的配送路径。

[0037] 一种巡检路径规划系统，所述系统包括：

[0038] 聚类数量计算模块，用于获取巡检数据，并根据所述巡检数据基于距离的类间类内划分指标BWP计算出聚类数量；

[0039] 初始巡检区域划分模块，用于根据所述巡检数据、所述聚类数量，通过K‑Means算法划分巡检区域，得到各个初始巡检区域；

[0040] 巡检区域调整模块，用于计算各个所述初始巡检区域的工作量，根据各个所述工作量对各个所述初始巡检区域进行二次划分，得到各个目标巡检区域；

[0041] 路径规划模块，用于对各个所述目标巡检区域，通过蚁群算法和遗传算法进行路径规划。

[0042] 一种计算机设备，包括存储器和处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现以下步骤：

[0043] 获取巡检数据，并根据所述巡检数据基于距离的类间类内划分指标BWP计算出聚类数量；

[0044] 根据所述巡检数据、所述聚类数量，通过K‑Means算法划分巡检区域，得到各个初始巡检区域；

[0045] 计算各个所述初始巡检区域的工作量，根据各个所述工作量对各个所述初始巡检区域进行二次划分，得到各个目标巡检区域；

[0046] 对各个所述目标巡检区域，通过蚁群算法和遗传算法进行路径规划。

[0047] 一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时实现以下步骤：

[0048] 获取巡检数据，并根据所述巡检数据基于距离的类间类内划分指标BWP计算出聚类数量；

[0049] 根据所述巡检数据、所述聚类数量，通过K‑Means算法划分巡检区域，得到各个初始巡检区域；

[0050] 计算各个所述初始巡检区域的工作量，根据各个所述工作量对各个所述初始巡检区域进行二次划分，得到各个目标巡检区域；

[0051] 对各个所述目标巡检区域，通过蚁群算法和遗传算法进行路径规划。

[0052] 上述巡检路径规划方法、系统、计算机设备及存储介质，通过获取巡检数据，并根据所述巡检数据基于距离的类间类内划分指标BWP计算出聚类数量；根据所述巡检数据、所述聚类数量，通过K‑Means算法划分巡检区域，得到各个初始巡检区域；计算各个所述初始巡检区域的工作量，根据各个所述工作量对各个所述初始巡检区域进行二次划分，得到各个目标巡检区域；对各个所述目标巡检区域，通过蚁群算法和遗传算法进行路径规划。基于BWP和K‑Means算法对大规模输电线路巡检区域进行区域划分，并对巡检区域进行调整，再结合蚁群算法和遗传算法对各区域内最优路径进行求解，可以提高最优路径算法求解效率，并平衡各个无人机的工作量。

附图说明

[0053] 图1为一个实施例中巡检路径规划方法的应用环境图；

[0054] 图2为一个实施例中巡检路径规划方法的流程示意图；

[0055] 图3为一个实施例中划分巡检区域的流程示意图；

[0056] 图4为一个实施例中基于K‑Means算法的划分初步巡检区域的流程示意图；

[0057] 图5为一个实施例中基于蚁群算法和遗传算法的巡检路径规划流程示意图；

[0058] 图6为一个实施例中巡检路径规划系统的结构框图；

[0059] 图7为一个实施例中计算机设备的内部结构图。

具体实施方式

[0060] 为了使本申请的目的、技术方案及优点更加清楚明白，以下结合附图及实施例，对本申请进行进一步详细说明。应当理解，此处描述的具体实施例仅仅用以解释本申请，并不用于限定本申请。

[0061] 本申请实施例提供的巡检路径规划方法，可以应用于如图1所示的应用环境中。如图1所示，该应用环境包括计算机设备110，其中，计算机设备110可以是机器人、无人飞行器等设备。计算机设备110可以获取获取巡检数据，并根据巡检数据基于距离的类间类内划分指标BWP计算出聚类数量；计算机设备110可以根据巡检数据、聚类数量，通过K‑Means算法划分巡检区域，得到各个初始巡检区域；计算机设备110可以计算各个初始巡检区域的工作量，根据各个工作量对各个初始巡检区域进行二次划分，得到各个目标巡检区域；计算机设备110可以对各个目标巡检区域，通过蚁群算法和遗传算法进行路径规划。

[0062] 在一个实施例中，如图2所示，提供了一种巡检路径规划方法，包括以下步骤：

[0063] 步骤202，获取巡检数据，并根据巡检数据基于距离的类间类内划分指标BWP计算出聚类数量。

[0064] 计算机设备可以获取巡检数据，其中，巡检数据可以包括需要进行输电线路巡检的地图、巡检点、巡检的无人机数量等数据。在进行巡检区域划分的过程中，计算机设备可以根据巡检数据基于距离的类间类内划分指标BWP计算出聚类数量。其中，聚类数量的大小可以直接影响聚类结果。

[0065] 步骤204，根据巡检数据、聚类数量，通过K‑Means算法划分巡检区域，得到各个初始巡检区域。

[0066] K‑Means算法在划分巡检区域的时候，会受到各种因素影响，具体的影响因素可以包括聚类数量、类间关系、初始聚类中心的选择、目标点间最短距离、巡检区域最大工作量、最低负载率及工作量平衡等。

[0067] 其中，类间关系：属于不同类的数据集合不存在交集，每一个数据点都只属于一个类；在使用K‑Means算法时需保证类间不存在交集，且每个数据点均被分类到唯一的类中；采用两个数据点间的欧式距离作为目标点间最短距离；巡检区域间的工作量差异过大会导致某些巡检组过早或过晚完成任务，导致巡检效率低下，因此需保证各巡检区域满足最大工作量和最低负载率的要求，且保证各区域工作量整体均衡。

[0068] 步骤206，计算各个初始巡检区域的工作量，根据各个工作量对各个初始巡检区域进行二次划分，得到各个目标巡检区域。

[0069] 计算机设备可以分别计算出各个初始巡检区域的工作量，根据工作量的大小考虑巡检区域最大工作量、最低负载率及工作量平衡的约束条件对区域划分结果进行优化调整，从而得到各个目标巡检区域。

[0070] 步骤208，对各个目标巡检区域，通过蚁群算法和遗传算法进行路径规划。

[0071] 在本实施例中，计算机设备通过获取巡检数据，并根据巡检数据基于距离的类间类内划分指标BWP计算出聚类数量；根据巡检数据、聚类数量，通过K‑Means算法划分巡检区域，得到各个初始巡检区域；计算各个初始巡检区域的工作量，根据各个工作量对各个初始巡检区域进行二次划分，得到各个目标巡检区域；对各个目标巡检区域，通过蚁群算法和遗传算法进行路径规划。基于BWP和K‑Means算法对大规模输电线路巡检区域进行区域划分，并对巡检区域进行调整，再结合蚁群算法和遗传算法对各区域内最优路径进行求解，可以提高最优路径算法求解效率，并平衡各个无人机的工作量。

[0072] 在一个实施例中，提供的一种巡检路径规划方法还可以包括划分初始巡检区域的过程，具体过程包括：基于巡检数据中的单个数据对象，计算出各个单个数据对象的各个BWP指标值；根据各个BWP指标值计算出平均BWP值；根据平均BWP值从聚类数量中确定最佳聚类数据；根据巡检数据、最佳聚类数量，通过K‑Means算法划分巡检区域。

[0073] 其中，由于K‑Means算法是以距离为量度计算不同巡检区域，为确定最佳聚类数量，使聚类结果呈现类内紧密且类间分离的效果，采用BWP对算法进行聚类评价，得到最佳聚类数量。

[0074] 具体的，BWP从距离测度出发，将最佳聚类结果定义为使聚类内部和聚类之间的距离最小化的结果。先针对待划分的数据集中的单个数据对象，基于定义的类间距离与类内距离，得到单个数据对象的BWP指标值；再计算得到整体数据集的平均BWP值，判断出整个数据对象集的聚类有效性。

[0075] 现将BWP指标的相关参数定义如下：将数据对象的聚类空间设置为K＝{X,R}，其中X＝{x1,x2,...,xn}。假设n个数据被划分到c个类之中，类间距离d(i,j)为第i类的第j个数据到其他类的数据对象的平均距离，计算公式为： 最小类间距离min d(i,j)的计算公式为： 其
中，k表示聚类数量，i表示第i类， 表示第i类的第j个数据对象，表示第k类的第r个数
2
据，nk表示第k类中的数据数量，||...||表示欧氏距离的平方；定义类内距离w(i,j)为第i类的第j个数据到类内的其他数据对象的平均距离，计算公式为：
其中， 表示第i类的第s个数据；定义聚类距离baw(i,j)为最小类
间距离与类内距离之和，聚类离差距离bsw(i,j)为最小类间距离与类内距离之差，则BWP值为baw(i,j)与bsw(i,j)的比值，计算公式为：

[0076] 其中，BWP指标值越大则代表该数据的聚类效果越好；基于BWP指标的定义设计平均BWP值，利用数据集合中所有数据的平均BWP指标值，实现对整个数据集的聚类效果评价。当整个数据集合的平均BWP指标值最大时，对应的聚类数量为该数据集的最佳聚类数量，计算公式为： kopt＝argmax{BWPavg(k)}。

[0077] 在对初始巡检区域进行划分时，计算机设备基于BWP评价标准，采用K‑Means算法初步进行区域划分，首先输入包含n个数据对象的待分类数据集及聚类数量k的取值范围，在k的取值范围内，分别计算其聚类结果，并根据不同k值得到的聚类结果计算相应的BWP值，将具有最大BWP值的聚类数量和聚类结果作为最终结果输出。

[0078] 在一个实施例中，提供的一种巡检路径规划方法还可以包括得到各个初始巡检区域的过程，具体过程包括：根据最佳聚类数量，通过K‑Means算法从巡检数据的各个数据点中确定各个初始聚类中心；计算各个剩余数据点到各个初始聚类中心的距离，并根据距离将各个剩余数据点划分到各个初始聚类中心所属类中；判断各个初始聚类中心是否收敛，若是，则输出分类结果，并根据分类结果划分巡检区域，得到各个初始巡检区域。

[0079] 在本实施例中，进行初始聚类中心选择时，为了避免聚类结果陷入局部最优解，先从所有的数据点中选取密度最大的一个点作为第一个初始聚类中心点，其次选取距离第一个初始聚类中心距离最大的点作为第二个初始聚类中心点，之后选取距离前两个点最短距离最大的点作为第三个初始聚类的中心点，以此类推，直至选出k个初始聚类中心点。

[0080] 具体的，在计算聚类结果时，首先根据初始聚类中心选择策略，选择k个数据点(c1,c2,...,ck)作为初始聚类中心；其次计算剩余数据点到各聚类中心间距离，基于最小距离约束将各数据点划分至与其距离最近的聚类中心所属类中；之后计算新的聚类中心，并根据公式 判断聚类中心是否收敛，若收敛则终止计算并输出分类结果，若不收敛则返回重新进行计算。

[0081] 在一个实施例中，提供的一种巡检路径规划方法还可以包括对初始巡检区域进行二次划分的过程，即考虑初始巡检区域最大工作量、最低负载率及工作量平衡的约束条件对区域划分结果进行优化调整；具体过程包括：计算各个初始巡检区域的工作量并进行排序，计算最大工作量与最小工作量的差值，若差值大于工作量阈值，则将最大工作量对应的初始巡检区域中距离初始聚类中心的最远数据点移除，并将最远数据点添加至与初始聚类中心距离第二小的类中。

[0082] 首先基于工作量平衡条件进行调整优化：对区域划分结果中每个区域的工作量进行计算并排序，选取最大工作量和最小工作量进行对比，如果两者差值不大于设定的工作量阈值则结束调整，如果大于设定的工作量阈值，则将工作量最大区域内距离聚类中心最远的点移除，并将该点添加至与聚类中心距离第二小的类中，并重新计算工作量及聚类中心，以此类推直至满足约束条件。

[0083] 当存在有最大工作量大于最大工作量阈值的初始巡检区域时，计算初始巡检区域内各个数据点到初始聚类中心的第一距离，并计算各个数据点到其他初始聚类中心的第二距离，根据第一距离、第二距离移动数据点。

[0084] 其次基于最大工作量条件进行调整优化：在上一步调整结果基础上，结合无人机最长工作时间，设置区域内的最大工作量阈值，计算各区域是否有超过最大工作量的情况，若不存在则完成调整，若存在则计算区域内各节点i到该区域聚类中心点距离di，即第一距离，同时计算各节点到其他聚类中心的距离Di，即第二距离，将di最大的节点移动至Di较小且满足工作量限制的区域，并重新计算工作量，以此类推直至满足约束条件。

[0085] 计算各个初始巡检区域工作量与所有区域中最大工作量的比值，并根据比值移动数据点。

[0086] 最后基于最小负载率进行调整优化：定义负载率为各区域工作量与所有区域中最大工作量的比值，在上一步调整结果基础上，设置区域最小负载率阈值，计算各区域负载率值并排序，若不存在低于阈值的区域则完成调整，若存在则从负载率最小的区域开始调整，计算其他区域各节点i到该区域聚类中心点距离Di，将Di值最小的节点移动至当前区域中，并重新计算工作量及聚类中心，以此类推直至满足约束条件。调整完成后得到最终的巡检区域划分结果。

[0087] 在一个实施例中，划分巡检区域的过程如图3所示：输入数据后，首先计算BWP值；根据计算出的BWP值选取最佳聚类数量；再基于K‑Means算法求解，得到初步区域划分结果；
接着，进行区域划分优化，基于巡检区域最大工作量、最低负载率及工作量平衡的约束条件对区域划分结果，得到区域划分最终结果，即各个目标巡检区域。

[0088] 在一个实施例中，基于K‑Means算法的划分初步巡检区域的过程如图4所示：输入数据及聚类数量范围后，可以计算聚类结果以及BWP值，然后再输出BWP值最大的聚类数量及结果。其中，计算聚类结果的过程包括：设置初始聚类中心，然后计算数据点到各聚类中心距离，依据最小距离原则划分数据点，并计算新聚类中心，然后判断聚类中心是否收敛，若收敛，则获取聚类结果；若不收敛，则重新设置初始聚类中心。

[0089] 在一个实施例中，提供的一种巡检路径规划方法还可以包括进行蚁群算法初始化的过程，具体过程包括：采用蚁群算法生成初始种群，对蚁群算法的参数进行初始化；构建蚁群算法的解空间，初始化蚂蚁的位置；对蚂蚁进行随机分配，更新信息素，计算蚂蚁遍历的路径；将迭代一次的路径作为遗传算法的初始种群。

[0090] 在一个实施例中，提供的一种巡检路径规划方法还可以包括进行遗传算法初始化的过程，具体过程包括：设置遗传算法的参数，并遗传算法进行初始化；其中，初始化参数包括种群规模、交叉概率、变异概率以及迭代次数。

[0091] 在一个实施例中，提供一种巡检路径规划方法还可以包括路径规划的过程，具体过程包括：通过遗传算法对初始种群中的染色体进行交叉、变异操作；染色体进行解码操作，得到配送路径的规划和划分结果；获取初始种群中每个个体的适应度值，采用轮盘赌的方式选择优秀的个体进入下一代；采用变规模种群规模遗传算法，对种群规模进行调整；当遗传算法达到最大的迭代次数时，则结束算法，输出最短的配送路径。

[0092] 其中，交叉部分采用两点交叉，变异部分采用两点互换变异。在对染色体进行解码操作时，可以基于最大工作时间、消除子环路等约束对染色体进行解码，从而得到配送路径的规划和划分结果。

[0093] 在一个实施例中，路径规划的过程如图5所示：

[0094] 采用蚁群算法生成初始种群，对算法的参数进行初始化，并构建蚁群算法的解空间，初始化蚂蚁的位置；再对蚂蚁进行随机分配，更新信息素，计算蚂蚁遍历的路径；将迭代一次的路径作为遗传算法的初始种群；

[0095] 设置遗传算法的参数，进行算法的初始化，包括种群规模、交叉概率、变异概率以及迭代次数；

[0096] 对种群中的染色体进行交叉、变异操作。其中交叉部分采用两点交叉，变异部分采用两点互换变异；

[0097] 基于最大工作时间、消除子环路等约束对染色体进行解码，得到配送路径的规划和划分结果；

[0098] 根据目标函数得到种群中每个个体的适应度值，采用轮盘赌的方式选择优秀的个体进入下一代；

[0099] 采用变规模种群规模遗传算法，对种群规模进行调整；

[0100] 判断是否满足遗传算法的结束条件。如果已经达到最大的迭代次数，则结束算法，输出最短的配送路径；否则将继续进行下一代的迭代，直至达到结束条件。

[0101] 应该理解的是，虽然上述流程图中的各个步骤按照箭头的指示依次显示，但是这些步骤并不是必然按照箭头指示的顺序依次执行。除非本文中有明确的说明，这些步骤的执行并没有严格的顺序限制，这些步骤可以以其它的顺序执行。而且，上述流程图中的至少一部分步骤可以包括多个子步骤或者多个阶段，这些子步骤或者阶段并不必然是在同一时刻执行完成，而是可以在不同的时刻执行，这些子步骤或者阶段的执行顺序也不必然是依次进行，而是可以与其它步骤或者其它步骤的子步骤或者阶段的至少一部分轮流或者交替地执行。

[0102] 在一个实施例中，如图6所示，提供了一种巡检路径规划系统，包括：聚类数量计算模块610、初始巡检区域划分模块620、巡检区域调整模块630和路径规划模块640，其中：

[0103] 聚类数量计算模块610，用于获取巡检数据，并根据巡检数据基于距离的类间类内划分指标BWP计算出聚类数量；

[0104] 初始巡检区域划分模块620，用于根据巡检数据、聚类数量，通过K‑Means算法划分巡检区域，得到各个初始巡检区域；

[0105] 巡检区域调整模块630，用于计算各个初始巡检区域的工作量，根据各个工作量对各个初始巡检区域进行二次划分，得到各个目标巡检区域；

[0106] 路径规划模块640，用于对各个目标巡检区域，通过蚁群算法和遗传算法进行路径规划。

[0107] 在一个实施例中，初始巡检区域划分模块620还用于基于巡检数据中的单个数据对象，计算出各个单个数据对象的各个BWP指标值；根据各个BWP指标值计算出平均BWP值；根据平均BWP值从聚类数量中确定最佳聚类数据；根据巡检数据、最佳聚类数量，通过K‑Means算法划分巡检区域。

[0108] 在一个实施例中，初始巡检区域划分模块620还用于根据最佳聚类数量，通过K‑Means算法从巡检数据的各个数据点中确定各个初始聚类中心；计算各个剩余数据点到各个初始聚类中心的距离，并根据距离将各个剩余数据点划分到各个初始聚类中心所属类中；判断各个初始聚类中心是否收敛，若是，则输出分类结果，并根据分类结果划分巡检区域，得到各个初始巡检区域。

[0109] 在一个实施例中，巡检区域调整模块630还用于计算各个初始巡检区域的工作量并进行排序，计算最大工作量与最小工作量的差值，若差值大于工作量阈值，则将最大工作量对应的初始巡检区域中距离初始聚类中心的最远数据点移除，并将最远数据点添加至与初始聚类中心距离第二小的类中；当存在有最大工作量大于最大工作量阈值的初始巡检区域时，计算初始巡检区域内各个数据点到初始聚类中心的第一距离，并计算各个数据点到其他初始聚类中心的第二距离，根据第一距离、第二距离移动数据点；计算各个初始巡检区域工作量与所有区域中最大工作量的比值，并根据比值移动数据点。

[0110] 在一个实施例中，路径规划模块640还用于采用蚁群算法生成初始种群，对蚁群算法的参数进行初始化；构建蚁群算法的解空间，初始化蚂蚁的位置；对蚂蚁进行随机分配，更新信息素，计算蚂蚁遍历的路径；将迭代一次的路径作为遗传算法的初始种群。

[0111] 在一个实施例中，路径规划模块640还用于设置遗传算法的参数，并对遗传算法进行初始化；其中，初始化参数包括种群规模、交叉概率、变异概率以及迭代次数。

[0112] 在一个实施例中，路径规划模块640还用于通过遗传算法对初始种群中的染色体进行交叉、变异操作；染色体进行解码操作，得到配送路径的规划和划分结果；获取初始种群中每个个体的适应度值，采用轮盘赌的方式选择优秀的个体进入下一代；采用变规模种群规模遗传算法，对种群规模进行调整；当遗传算法达到最大的迭代次数时，则结束算法，输出最短的配送路径。

[0113] 在一个实施例中，提供了一种计算机设备，该计算机设备可以是无人机，其内部结构图可以如图7所示。该计算机设备包括通过系统总线连接的处理器、存储器、网络接口、显示屏和输入装置。其中，该计算机设备的处理器用于提供计算和控制能力。该计算机设备的存储器包括非易失性存储介质、内存储器。该非易失性存储介质存储有操作系统和计算机程序。该内存储器为非易失性存储介质中的操作系统和计算机程序的运行提供环境。该计算机设备的网络接口用于与外部的终端通过网络连接通信。该计算机程序被处理器执行时以实现一种巡检路径规划方法。该计算机设备的显示屏可以是液晶显示屏或者电子墨水显示屏，该计算机设备的输入装置可以是显示屏上覆盖的触摸层，也可以是计算机设备外壳上设置的按键、轨迹球或触控板，还可以是外接的键盘、触控板或鼠标等。

[0114] 本领域技术人员可以理解，图7中示出的结构，仅仅是与本申请方案相关的部分结构的框图，并不构成对本申请方案所应用于其上的计算机设备的限定，具体的计算机设备可以包括比图中所示更多或更少的部件，或者组合某些部件，或者具有不同的部件布置。

[0115] 在一个实施例中，提供了一种计算机设备，包括存储器和处理器，存储器中存储有计算机程序，该处理器执行计算机程序时实现以下步骤：

[0116] 获取巡检数据，并根据巡检数据基于距离的类间类内划分指标BWP计算出聚类数量；

[0117] 根据巡检数据、聚类数量，通过K‑Means算法划分巡检区域，得到各个初始巡检区域；

[0118] 计算各个初始巡检区域的工作量，根据各个工作量对各个初始巡检区域进行二次划分，得到各个目标巡检区域；

[0119] 对各个目标巡检区域，通过蚁群算法和遗传算法进行路径规划。

[0120] 在一个实施例中，处理器执行计算机程序时还实现以下步骤：基于巡检数据中的单个数据对象，计算出各个单个数据对象的各个BWP指标值；根据各个BWP指标值计算出平均BWP值；根据平均BWP值从聚类数量中确定最佳聚类数据；根据巡检数据、最佳聚类数量，通过K‑Means算法划分巡检区域。

[0121] 在一个实施例中，处理器执行计算机程序时还实现以下步骤：根据最佳聚类数量，通过K‑Means算法从巡检数据的各个数据点中确定各个初始聚类中心；计算各个剩余数据点到各个初始聚类中心的距离，并根据距离将各个剩余数据点划分到各个初始聚类中心所属类中；判断各个初始聚类中心是否收敛，若是，则输出分类结果，并根据分类结果划分巡检区域，得到各个初始巡检区域。

[0122] 在一个实施例中，处理器执行计算机程序时还实现以下步骤：计算各个初始巡检区域的工作量并进行排序，计算最大工作量与最小工作量的差值，若差值大于工作量阈值，则将最大工作量对应的初始巡检区域中距离初始聚类中心的最远数据点移除，并将最远数据点添加至与初始聚类中心距离第二小的类中；当存在有最大工作量大于最大工作量阈值的初始巡检区域时，计算初始巡检区域内各个数据点到初始聚类中心的第一距离，并计算各个数据点到其他初始聚类中心的第二距离，根据第一距离、第二距离移动数据点；计算各个初始巡检区域工作量与所有区域中最大工作量的比值，并根据比值移动数据点。

[0123] 在一个实施例中，处理器执行计算机程序时还实现以下步骤：采用蚁群算法生成初始种群，对蚁群算法的参数进行初始化；构建蚁群算法的解空间，初始化蚂蚁的位置；对蚂蚁进行随机分配，更新信息素，计算蚂蚁遍历的路径；将迭代一次的路径作为遗传算法的初始种群。

[0124] 在一个实施例中，处理器执行计算机程序时还实现以下步骤：设置遗传算法的参数，并对遗传算法进行初始化；其中，初始化参数包括种群规模、交叉概率、变异概率以及迭代次数。

[0125] 在一个实施例中，处理器执行计算机程序时还实现以下步骤：通过遗传算法对初始种群中的染色体进行交叉、变异操作；染色体进行解码操作，得到配送路径的规划和划分结果；获取初始种群中每个个体的适应度值，采用轮盘赌的方式选择优秀的个体进入下一代；采用变规模种群规模遗传算法，对种群规模进行调整；当遗传算法达到最大的迭代次数时，则结束算法，输出最短的配送路径。

[0126] 在一个实施例中，提供了一种计算机可读存储介质，其上存储有计算机程序，计算机程序被处理器执行时实现以下步骤：

[0127] 获取巡检数据，并根据巡检数据基于距离的类间类内划分指标BWP计算出聚类数量；

[0128] 根据巡检数据、聚类数量，通过K‑Means算法划分巡检区域，得到各个初始巡检区域；

[0129] 计算各个初始巡检区域的工作量，根据各个工作量对各个初始巡检区域进行二次划分，得到各个目标巡检区域；

[0130] 对各个目标巡检区域，通过蚁群算法和遗传算法进行路径规划。

[0131] 在一个实施例中，计算机程序被处理器执行时还实现以下步骤：基于巡检数据中的单个数据对象，计算出各个单个数据对象的各个BWP指标值；根据各个BWP指标值计算出平均BWP值；根据平均BWP值从聚类数量中确定最佳聚类数据；根据巡检数据、最佳聚类数量，通过K‑Means算法划分巡检区域。

[0132] 在一个实施例中，处计算机程序被处理器执行时还实现以下步骤：根据最佳聚类数量，通过K‑Means算法从巡检数据的各个数据点中确定各个初始聚类中心；计算各个剩余数据点到各个初始聚类中心的距离，并根据距离将各个剩余数据点划分到各个初始聚类中心所属类中；判断各个初始聚类中心是否收敛，若是，则输出分类结果，并根据分类结果划分巡检区域，得到各个初始巡检区域。

[0133] 在一个实施例中，计算机程序被处理器执行时还实现以下步骤：计算各个初始巡检区域的工作量并进行排序，计算最大工作量与最小工作量的差值，若差值大于工作量阈值，则将最大工作量对应的初始巡检区域中距离初始聚类中心的最远数据点移除，并将最远数据点添加至与初始聚类中心距离第二小的类中；当存在有最大工作量大于最大工作量阈值的初始巡检区域时，计算初始巡检区域内各个数据点到初始聚类中心的第一距离，并计算各个数据点到其他初始聚类中心的第二距离，根据第一距离、第二距离移动数据点；计算各个初始巡检区域工作量与所有区域中最大工作量的比值，并根据比值移动数据点。

[0134] 在一个实施例中，计算机程序被处理器执行时还实现以下步骤：采用蚁群算法生成初始种群，对蚁群算法的参数进行初始化；构建蚁群算法的解空间，初始化蚂蚁的位置；对蚂蚁进行随机分配，更新信息素，计算蚂蚁遍历的路径；将迭代一次的路径作为遗传算法的初始种群。

[0135] 在一个实施例中，计算机程序被处理器执行时还实现以下步骤：设置遗传算法的参数，并对遗传算法进行初始化；其中，初始化参数包括种群规模、交叉概率、变异概率以及迭代次数。

[0136] 在一个实施例中，计算机程序被处理器执行时还实现以下步骤：通过遗传算法对初始种群中的染色体进行交叉、变异操作；染色体进行解码操作，得到配送路径的规划和划分结果；获取初始种群中每个个体的适应度值，采用轮盘赌的方式选择优秀的个体进入下一代；采用变规模种群规模遗传算法，对种群规模进行调整；当遗传算法达到最大的迭代次数时，则结束算法，输出最短的配送路径。

[0137] 本领域普通技术人员可以理解实现上述实施例方法中的全部或部分流程，是可以通过计算机程序来指令相关的硬件来完成，所述的计算机程序可存储于一非易失性计算机可读取存储介质中，该计算机程序在执行时，可包括如上述各方法的实施例的流程。其中，本申请所提供的各实施例中所使用的对存储器、存储、数据库或其它介质的任何引用，均可包括非易失性和/或易失性存储器。非易失性存储器可包括只读存储器(ROM)、可编程ROM(PROM)、电可编程ROM(EPROM)、电可擦除可编程ROM(EEPROM)或闪存。易失性存储器可包括随机存取存储器(RAM)或者外部高速缓冲存储器。作为说明而非局限，RAM以多种形式可得，诸如静态RAM(SRAM)、动态RAM(DRAM)、同步DRAM(SDRAM)、双数据率SDRAM(DDRSDRAM)、增强型SDRAM(ESDRAM)、同步链路(Synchlink)DRAM(SLDRAM)、存储器总线(Rambus)直接RAM(RDRAM)、直接存储器总线动态RAM(DRDRAM)、以及存储器总线动态RAM(RDRAM)等。

[0138] 以上实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。

[0139] 以上所述实施例仅表达了本申请的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本申请构思的前提下，还可以做出若干变形和改进，这些都属于本申请的保护范围。因此，本申请专利的保护范围应以所附权利要求为准。