摘要
无人机巡检作业中，因为功能与续航距离不同，常面临异构无人机协同和机巢选址问题。无人机机巢的最优部署位置策略，可以看作新的选址优化问题，相对于传统设施选址问题，无人机机巢部署问题面临更多新挑战。笔者综合运用地理信息系统、优劣解距离法对候选点位做预筛选后使用贪心算法和拉格朗日松弛优化的p-中值覆盖问题优化方法，在综合考虑布点原则、飞行任务、飞行半径、功能性冗余等目标因素，提出一种多目标优化最低代价的无人机机巢选址法，将机巢分布问题定义为限制因素预选址前提下的p-中值最低代价问题，设置原则性约束，实现多目标优化最低代价的机巢布点，从多个角度考虑降低巡检成本。实验结果表明：多目标优化后机巢布点在建造、维护、巡检和综合成本上比传统选点方法有9.2%以上的成本节约。
随着中国电网规模扩大，无人机自动化电力线路巡检取代人工巡检已成为当下一大趋势。为进一步提升运检输变配送专业精益化管理水平与运维效率，降低运行成本，缓解巡检人员不足和巡检日益精细化矛盾，提升无人机巡检全自主水平，在电力线路巡检范围内设定不同规模的无人机巢点，作为无人机充电、安放的固定场所至关重要。无人机机巢位置固定，且每个机巢覆盖范围有限，需要通过设置不同机巢，实现电力网络全覆盖目标，由此产生机巢位置的最优部署问题。
无人机机巢的最优部署位置策略，可看作一类新的选址优化问题。相对于传统的设施选址问题，无人机机巢部署问题面临更多新挑
无人机机巢的选址方法可部分借鉴通信设施的选址问题，然而相比传统通信设施选址，无人机选址过程存在更加复杂的环境约束和更大的优化空间。在进行无人机选址任务时，需要明确原则性约束，比如无人机机巢必须设置在有人看守且方便维护的地方，这些原则性约束构成机巢选址过程的过滤条件集合，能够高效排除不符合这些条件的点位，显著缩小算法的搜索空间。此外，机巢选点问题不同于传统通信基站选点问题的一个关键因素是优化目标不同，在进行通信基站选点时，只需保证通过设立基站达到信号的全域覆盖即可。而在进行无人机机巢选点时，不仅需要达到搜索范围的全域覆盖，还需要针对一次性投入的基站建设成本、巢维护、巡检成本等长期投入成本进行多目标优化。结合使用地理信息系统、优劣解距离法和优化p-中值覆盖方法，综合考虑建造成本、维护成本和巡检成本3种不同成本，基于改进的p-median算法提出可行的选址方案。
机巢布点应首先采用布点规划方法进行布点模拟，再通过遗传算法、禁忌搜
随着计算机技术的不断发展，地理信息系统(GIS
优劣解距离法又叫技术偏好排序法（technique for order preference by similarity to an ideal solution， TOPSIS）是一种常用的多准则决策分析方法，基本思想是通过计算每个决策方案与最优解和最劣解之间的相似度来确定方案的优劣程度。陈俊锋
集合覆盖问
基于SCP的无人机基站部署问题是在满足规定覆盖比例前提下，融合无人机基站相关约束，优化所需无人机数量及部署位
| 策略名称 | 原理 | 优点 | 缺点 |
|---|---|---|---|
| SCP | 在全覆盖的情况下，优化所需无人机数量及位置 | 以全覆盖为目标，尽量减少成本，方便进行方案调整 | 不同任务执行频次不同，需要进行人工调整 |
| p-median | 使各任务点到机巢的加权平均距离最小 | 主要考虑整体的覆盖水平，覆盖效率较高 | 不能考虑距离较远的任务点，不能适应应急场景 |
| p-center | 使各任务点到机巢的最远距离最小 | 能够满足在应急条件下，距离较远的任务也可以以可控的成本完成 | 整体的覆盖水平较差 |
无人机机巢为无人机起降提供平台和运输导航系统，也为无人机自主巡检提供完善的路线规划和安全保
无人机机巢根据存放无人机类型不同划分为3种，即大型多旋翼机巢、中型多旋翼机巢和小型多旋翼机巢。在该设计中，3种机巢之间的差异集中体现在覆盖半径和可承担巡检任务上，其中大型无人机巢有效覆盖半径为7 km，中型无人机巢有效覆盖半径为5 km，小型无人机巢有效覆盖半径仅为3 km。因3种类型的无人机巢实际承担的巡检任务要求互不相同，因此考虑将3种不同类型的无人机巢部署视为3次机巢选址过程，分别使用所述机巢选址方法进行独立规划。所述选址方法以小型机巢选址为例，大、中型机巢选址过程同理。
无人机固定机巢选址原则主要考虑机巢部署区域不受到外界因素干扰，同时满足机巢供电需求及网络资源需求。为便于管理，部署区域一般定于供电所和本地运维管辖的变电站内。基于这些原则并结合电网地图信息、地形数据和禁飞区信息综合研判可初步筛选获得满足全部硬性要求的候选点位集合。具体来说，这些原则要求可部署固定机巢的位置包括：变电站生活区、供电所空旷区及办公楼楼顶、提供供电及网络区域、无禁飞限制区域等。
除原则性要求外，还需要考虑无人机覆盖半径约束对机巢选址的影响。对每个机巢而言，其只需负责其覆盖半径内的巡检目标。该约束可用欧氏距离表示为
| , | （1） |
式中：为源点集，即本研究中的机巢位置；为目标点集，即本研究中的任务点位置；为无人机的覆盖半径，在该例中为3 km；该式限制机巢与其负责的目标点构成矢量模应小于等于机巢覆盖半径。根据该约束信息可得到机巢点-目标点二部图，进而得到小类集合，表示为
算法1:小类集合生成
输入:原点集目标点集覆盖半径;
输出:小类集合
1） Initialize list S, s;
2） for d in D;
3） 清空s;
4） for u in U;
5） if distance(d,u);
6） S.append(u);
7）S.append(s);
8） return S;
在集合覆盖问题语境下，小类集合中的每一项(小类)中元素的交集应等于总集，才可实现覆盖。在实现集合覆盖的前提下，又需要考虑实现覆盖所需要的成本或代价。
基于地理信息系统的初步位置筛选步骤如
图1 基于地理信息系统的初步位置筛选流程图
Fig. 1 Preliminary Location Screening Flowchart Based on Geographic Information System
①使用ArcGIS对原则要求绘制单一图层，针对每一个原则，人为判断是否是适宜区。使用ArcGIS Toolbox将适宜区赋值为1，不适宜区赋值为0，得到变电站生活区图层、供电所空旷区及楼顶图层、可提供供电及网络区域图层和无禁飞区域图层。
②叠加评估。为了得到综合评估结果，通过对以上4个图层设置平均权重，进行叠加，根据叠加后综合图层的值进行判断，设置阈值，重新划分0，1。
③聚类分析。使用基于欧氏距离的K-means算法，以半径距离为3 km能够覆盖为前提，确定K个聚类中心。
④获得初选区域。根据聚类结果在GIS图上得到实际地点坐标。
机巢选址问题因其应用特殊性，不能简单归结为集合覆盖问题。在使用最少基站数量做到全域覆盖的前提下，还需要考虑实际应用场景下的优化问题。在做多目标优化时，需要考虑多种目标之间的权衡关系，该关系通常使用权重λ进行控制，并利用拉格朗日乘子法等优化方法，使最终目标达到帕累托最优，但在本问题中存在区别于传统优化方法的特点，即机巢位置一旦确定下来，便难以更改。因此，在选址时需要确定几个目标之间的权重关系，即针对一个特定实施方案，几个目标之间的权重总是静态的。因此针对机巢选址场景，多目标优化实质上被转化为同质化的代价数值优化，在此基础上，确定可量化的代价数值就成为了优化过程的关键。在本方案中着重考虑3种类型的代价：机巢建设代价、机巢维护代价和巡检代价。
机巢建设作为一个系统性工程项目，不同实施难度会直接造成建设成本有所差异。具体来说，若机巢部署需要额外用地，则将引入用地成本；若机巢点位选取在地形复杂、不易施工的地方，施工成本会相应上升；若机巢点位选在供电困难的地方，在部署好机巢后补充供电也会引入额外成本。
虽然可确保机巢均被安装在变电站和供电所等方便人员维护的地方，但是考虑到如果机巢维护需要进行危险作业，维护人员面临的工作风险也会引入隐性成本；若机巢安装在气候条件恶劣地方，则相对容易损坏，引入维修成本和可靠性成本。
在机巢位置确定下来且投入使用之后，巡检所需要花费的时间、人力和资源也会成为成本的一部分，优化机巢布局以使得巡检时的代价最低也被纳入考量。然而这部分成本难以被量化，主要体现在2个方面：1）时间成本和人力成本难以统计；2）巡检代价随着运行时间增加而增加，目前还难以确定该系统的使用年限。
在进行多目标优化前，首先满足硬性需求，实现无人机巡检范围覆盖辖区全域，在此前提下再进行代价优化。为满足覆盖需求，选择提出的4种常用覆盖问题求解模型的一种与本方案需求近似模型进行建模。
通过横向对比4种覆盖模型，在每个任务点采样概率相近的假设基础上，p-median算法和方案要求最为相符，因此将设计要求建模为p-median问题，即在全覆盖前提下实现最小化覆盖代价，并在此基础上补充提到的建设成本与维护成本加权后作为额外代价。
在p-median问题建模中，定义巡检任务集合，其中，定义无人机设备集合,其中，为了将问题归为整数线性规划问题解决，定义决策变量如式（2）
| 。 | （2） |
为了定义某个巡检任务具体是由哪个无人机执行的，定义决策变量（3）
| 。 | （3） |
在以上定义的基础上，可将本问题中所述约束条件如下
| , | （4） |
| , | （5） |
| , | （6） |
| , | （7） |
| , | （8） |
其中：
在上述约束条件基础上，进一步将机巢建设代价、机巢维护代价、巡检代价分别表示为
| , | （9） |
| , | （10） |
| , | （11） |
将上述3个优化目标通过多目标优化式统一到一个总优化目标上
| 。 | （12） |
上述3个优化目标单位不一致，且在部分情况下存在冲突，需要结合实际工程需要，在不同情况下选择多目标优化
对于覆盖问题的优化算法有很多，比较有效的包括贪心算法和动态规划算法。然而传统的集合覆盖问题优化算法存在以下2个主要缺陷：首先是求解速度慢，其次是容易陷入局部最优解。因此采用启发式算法，将亚梯度优化的贪心算法与拉格朗日松弛(LR)法结
图2 覆盖算法流程图
Fig. 2 Flowchart of the overlay algorithm
结合以上约束、优化目标、覆盖模型与优化器，实际数据向不同目标和需求生成了3种代价选址方案。面向3种代价优化得到的选址方案如
图3 多目标机巢布点仿真结果
Fig. 3 Simulation results of multi-target machine nest layout
为了验证多目标优化算法的优越性，根据约束条件下，引入自适应多目标优化方法前人为手动选择的机巢位点，与算法得到的机巢分布点进行比较，如
图4 手动选点与算法选择代价对比
Fig. 4 Comparison between manual point selection and algorithm selection costs
提出一种多目标优化最低代价的无人机机巢选址方法，结合GIS方法和TOPSIS方法对机巢候选点进行预筛选，后将机巢分布问题定义为p-median最低代价问题，通过多目标优化方法，最终确定无人机机巢的分布位点，并将算法优化得到的无人机机巢位点与基于GIS和TOPSIS方法的人工选择的无人机机巢位点从建造成本、维护成本、巡检成本等多约束条件进行对比，证明了本优化算法的有效性，对电力线路无人机巡检工作具有实践意义。
参考文献
靳晓洁, 石建迈, 伍国华, 等. 无人机基站部署问题综述: 模型与算法[J]. 控制理论与应用, 2022, 39(12): 2219-2232. [百度学术]
Jin X J, Shi J M, Wu G H, et al. Review of the UAV base station deployment problem: models and algorithms[J]. Control Theory & Applications, 2022, 39(12): 2219-2232.(in Chinese) [百度学术]
刘芳正,马博闻,吕博枫等.一种面向移动边缘计算的无人机基站部署方法[J].计算机科学,2022,49(S2):848-854. [百度学术]
Liu F Z, Ma B W, Lu B F, et al. An UAV base station deployment method for mobile edge computing[J]. Computer Science,2022,49(S2):848-854.(in Chinese) [百度学术]
方云飞, 王晓园, 周珍, 等. 基于禁忌搜索的公共自行车站点及车道选址优化[J]. 重庆大学学报, 2020, 43(1): 19-27. [百度学术]
Fang Y F, Wang X Y, Zhou Z, et al. Research of optimal layout of public bike stations and bike lanes based on tabu search[J]. Journal of Chongqing University (Natural Science Edition), 2020, 43(1): 19-27.(in Chinese) [百度学术]
Huang B,Lin J,Zheng X, et al. Airport site selection under complex airspace based on GIS[C]//Fourth International Conference on Transportation Engineering. October 19-20, 2013, Chengdu, China. Reston, VA, USA: American Society of Civil Engineers, 2013: 2188-2194. [百度学术]
Alves C J P, da Silva E J, Müller C, et al. Towards an objective decision-making framework for regional airport site selection[J]. Journal of Air Transport Management, 2020, 89: 101888. [百度学术]
何尧, 舒富民, 郑皓文. 基于GIS多因素加权叠加的机场选址方法[J]. 中国民航大学学报, 2021, 39(4)42-47. [百度学术]
He Y, Shu F M, Zheng H W. Site selection method of airport location based on GIS multi-factor weighted superposition[J]. Journal of Civil Aviation University of China, 2021, 39(4)42-47(in Chinese) [百度学术]
Wang J J, Jing Y Y, Zhang C F, et al. Review on multi-criteria decision analysis aid in sustainable energy decision-making[J]. Renewable and Sustainable Energy Reviews, 2009, 13(9): 2263-2278. [百度学术]
Feng S, XuL D. Decision support for fuzzy comprehensive evaluation of urban development[J]. Fuzzy Sets and Systems, 1999, 105(1): 1-12. [百度学术]
陈俊锋, 翁建军, 吴兵, 等. 基于熵权-TOPSIS的水上机场选址研究[J]. 交通信息与安全, 2018, 36(2)112-119 [百度学术]
Chen J F, Weng J J, Wu B, et al. A facility location model based on entropy and TOPSIS for sea drones[J]. Journal of Transport Information and Safety, 2018, 36(2)112-119(in Chinese) [百度学术]
种小雷, 雷继超, 张世迪, 等. 机场选址阶段不同场址净空条件的量化对比[J]. 科学技术与工程, 2020, 20(27): 11365-11370. [百度学术]
Chong X L, Lei J C, Zhang S D, et al. Quantitative comparison of clearance conditions of different sites in airport location selection stage[J]. Science Technology and Engineering, 2020, 20(27): 11365-11370.(in Chinese) [百度学术]
付蔷, 王诺. 机场选址对候鸟影响评价: 以大连为例[J]. 科学技术与工程, 2018, 18(19): 316-323. [百度学术]
Fu Q, Wang N. Impact assessment of airport site selection on migratory birds—case of Dalian civil aviation airport[J]. Science Technology and Engineering, 2018, 18(19): 316-323.(in Chinese) [百度学术]
Church R, ReVelle C. The maximal covering location problem[J].Papers of the Regional Science Association, 1974, 32(1): 101-118. [百度学术]
杨思颖. 基于空间-时间-电量网络的电动汽车充电站选址-路径问题研究[D]. 南京: 东南大学. [百度学术]
Yang S Y. Research on location-routing problem of electric vehicle charging station based on space-time-electricity network[D]. Nanjing: Southeast University,. (in Chinese) [百度学术]
Hakimi. Optimal locations of switching centers and the absolute centers and the medians of a graph[J]. Operations Research，1964，12： 450-459. [百度学术]
Navi S P, Zeiny A S. New approach to improve classification accuracy using ant clony optimization[C]//2010 Fourth UKSim European Symposium on Computer Modeling and Simulation. November 17-19, 2010. Pisa, Italy: IEEE, 2011: 46-50. [百度学术]
Mirjalili S. Genetic algorithm[C]// Evolutionary Algorithms and Neural Networks. Cham: Springer, 2019: 43-55. [百度学术]
吴钦钦, 王珂, 樊文有, 等. 基于连续空间需求的公共图书馆最大覆盖选址方法: 以武汉市主城区为例[J]. 地理与地理信息科学, 2020, 36(1)27-34, 99 [百度学术]
Wu Q Q, Wang K, Fan W Y, et al. Optimizing the public library location based on coverage maximization of continuous space demands: a case study of the downtown of Wuhan city[J]. Geography and Geo-Information Science, 2020, 36(1)27-34, 99(in Chinese) [百度学术]
Mozaffari M, Saad W, Bennis M, et al. Efficient deployment of multiple unmanned aerial vehicles for optimal wireless coverage[J]. IEEE Communications Letters, 2016, 20(8): 1647-1650. [百度学术]
Lagum F, Bor-Yaliniz I, Yanikomeroglu H. Strategic densification with UAV-BSs in cellular networks[J]. IEEE Wireless Communications Letters, 2018, 7(3): 384-387. [百度学术]
乔联宝. 覆盖类选址问题分类及研究综述[J]. 物流科技, 2015, 38(3): 59-66. [百度学术]
Qiao L B. Classification and review on the covering facility location problem[J]. Logistics Sci-Tech, 2015, 38(3): 59-66.(in Chinese) [百度学术]
田力. 输电线路无人机巡检综合应用研究[J]. 通讯世界, 2018(11): 215-216. [百度学术]
Tian L. Research on comprehensive application of UAV patrol inspection for transmission lines[J]. Telecom World, 2018(11): 215-216.(in Chinese) [百度学术]
Zhu G. A new view of classification in astronomy with the archetype technique: an astronomical case of the NP-complete set cover problem[EB/OL]. 2016: arXiv: 1606.07156. https://arxiv.org/abs/1606.07156 [百度学术]