无人机巡检机巢选址的Matlab实现与遗传算法求解方法

无人机巡检项目的机巢布点选址，听起来像是个带约束的覆盖问题，但真正接手的电力巡检规划人员都知道，难点不在于把公式列出来，而在于把约束从现场搬进Matlab代码。机巢不是越多越好，太密的覆盖浪费成本；机巢也不能只考虑直线距离，巡检需求点在高山上、线路走向完全顺着山谷，续航余量、返航条件、任务时间窗每一项都会让原有方案失效。这篇文章就把我在电力巡检机巢选址里常用的算法思路、Matlab代码框架和参考文献清单分开讲清楚，适合正在做无人机巡检规划、准备给机巢布局避坑的工程师参考。

1. 巡检机巢选址的核心矛盾：约束不是加分项，而是边界条件

1.1 续航半径与线路走向的硬耦合

做机巢选址，第一步不是画圆覆盖，而是把巡检需求点离散化。电力巡检场景里，需求点通常是杆塔、耐张塔、变电站出线终端塔，或者被地质监测点名要求定期查看的山体区段。机巢要覆盖这些点，本质是让无人机在电池约束下飞得到、回得来。很多人建模时直接把无人机最大航程除以二当成覆盖半径，这是理想情况，实际工程里必须考虑返航余量。

举例说明，一款常见多旋翼巡检无人机，满载带光电吊舱，续航40分钟，巡航速度大约12m/s，理论航程约28.8km，理论半径14.4km。但这个半径在巡检中基本不能用，因为巡检输电线路时往往要悬停拍摄、调整云台角度，消耗的功率比匀速巡航高；遇到3~4级风，顺风飞和逆风飞的时间差很大；再加上电池老化后的容量缩水，我一般按理论续航乘以0.7折算。也就是说，理论半径14.4km，实际参与覆盖计算的半径我通常取8~10km。这个折扣不是保守，而是让算法结果真正能用于飞行。

有了实际覆盖半径R，距离约束就落到了“杆塔-机巢”之间的距离矩阵上。注意这里不是欧氏平面距离，而是考虑了高差和地形绕行的等效飞行距离。山区线路高差动辄几百米，直线距离5km的塔和机巢，实际航线可能要走7~8km。所以我在Matlab里算距离矩阵时，除了用平面坐标求XY距离，还会叠加DEM高程差修正。具体做法是先加载数字高程模型，沿机巢到目标点方向采样，把剖面的累计爬升量按比例计入等效距离；没有DEM数据也可以用线路走廊的杆塔海拔表做线性插值近似。这一步看似粗糙，却能让选址结果避开“图上能覆盖、实际飞不到”的尴尬。

1.2 地理起伏、通信链路和返航条件的隐性约束

除了飞不飞得到，还要考虑落不落得下、控制链路通不通。机巢不是随便一块平地就能建，需要考虑地势平坦度、土方量、道路可达性、附近是否有干扰源，以及最关键的一点：是否处于可用空域。这几个条件在做候选点筛选时就要提前过滤掉，不要把明显不能建的位置放进算法候选集里，否则算法迭代半天给出一个看似省钱的点，现场踏勘直接否定，等于白算。

通信链路约束更隐蔽。电力巡检无人机通常工作在2.4GHz或5.8GHz频段，机巢选址如果选在山谷底部，电台信号被山体遮挡，地面站和无人机之间容易丢链路。所以我在预处理时会对每个候选点计算通视范围，把对关键巡检目标存在通视遮挡的候选点做降权或者直接剔除。如果项目有固定翼无人机巡检任务，还要考虑起降航线空间，候选点周边不可有密集树林和高耸障碍物。这些约束没有写进目标函数，但必须在候选点生成阶段就处理干净，否则约束再精细，候选点本身不合格，后面全白搭。

还要特别提一下返航条件。很多模型只算“去程”距离小于R，但无人机飞抵最后一个巡检点拍照后，需要回到机巢降落，实际等效路径是“去程+全部巡检点串飞路径+返程”。巡检任务通常是机巢起飞到某线路段，沿着线路依次巡视多基杆塔，最后返航。所以覆盖一个“点”只是基础，更合理的建模应该覆盖“一个区段”。把路径长度拆解成作业段之后，每个候选机巢的覆盖半径不是一个固定圆，而是随巡检方向变化的串形区域。这会让模型的约束更多，但也更真实。

1.3 时效约束：巡检窗口不只是给无人机定的

电力巡检有不同的响应等级。日常周期巡视以月为单位，窗口很宽松；但雷雨季节过后、外力破坏高发区、缺陷复测等场景，要求发现异常后在几小时内完成复核。这意味着机巢不仅要覆盖目标，还要满足响应时间约束。无人机到达目标点的飞行时间、准备起飞时间、降落回收时间要全部计入。如果某些机巢位置虽然覆盖目标，但到达时间超过要求窗口，就不能算作有效覆盖。

所以在我的模型里，每个需求点除了有坐标和权重，还会带一个允许的最大响应时间T_i。在计算覆盖判定时，不使用“距离小于R”，而是使用“等效飞行距离/巡航速度 + 起飞准备时间 <= T_i”。这样把时间和空间两个维度统一进了一个表达式。响应时间约束对山区巡检来说往往比续航半径更苛刻，因为线路塔之间的距离不长，但每个塔都要悬停检查，时间消耗集中在作业阶段，而不是飞行阶段。

2. 从实际需求到数学模型：目标函数和约束怎么写

2.1 目标函数：覆盖优先还是成本优先

机巢布点本质是设施选址问题，目标函数取决于项目阶段。新建一张巡检网时，通常希望在预算内覆盖尽量多的重点目标，模型写成“最大覆盖问题”；运行阶段希望控制运维成本，则写成“最小成本问题”。实际项目中很少有人只用一个目标，常见做法是把成本和覆盖加权成一个单目标，或者用多目标智能算法求Pareto前沿。

我用的是加权单目标形式：

$$ \min Z = -\alpha\sum_{i \in I} w_i \cdot cov_i + \beta\sum_{j \in J} C_j \cdot x_j + \gamma\sum_{i \in I} w_i \cdot (1-cov_i) $$

其中，(x_j)是0-1决策变量，表示第j个候选机巢是否被选中；(cov_i)表示第i个需求点是否被至少一个选中机巢覆盖；(w_i)是需求点的重要程度权重，重点保供线路和重要负荷通道的塔位权重更高；(C_j)是第j个机巢的建设成本；(\alpha)、(\beta)、(\gamma)是权重系数。

这个目标函数把成本项和未覆盖惩罚项放在一起，避免“模型只追求覆盖而疯狂建机巢”的情况。未覆盖项(w_i(1-cov_i))本质是对漏检风险的惩罚，它比覆盖项更直观，因为优化结果可以看出来“还剩下哪些高权重塔没覆盖到”，方便人工研判。

2.2 约束条件的数学化表达

模型需要写清楚的关键约束有以下几类。

覆盖唯一性约束：每个需求点至少被一个机巢覆盖，但对于某些预设允许漏检的场景，可以放宽为软约束，只在目标函数里惩罚。

$$ \sum_{j \in J} y_{ij} \ge 1,\quad \forall i \in I $$

机巢启用逻辑约束：一个需求点只有在其所属机巢被选中时才能被覆盖。

$$ y_{ij} \le x_j,\quad \forall i \in I, j \in J $$

距离/时间约束：

$$ d_{ij} \cdot z_{ij} \le R_j + M(1-y_{ij}) $$

这里(z_{ij})是等效飞行距离，当需求点i被机巢j覆盖时，必须满足距离不大于该机巢的有效覆盖半径。(M)是足够大的常数，用来保证未覆盖时不约束。

容量约束：每个机巢在某一巡检周期内能执行的任务次数有限。如果一个机巢同时覆盖太多高密集杆塔，无人机一天内往返架次数会超过电池和运维人员上限。约束写为：

$$ \sum_{i \in I} q_i \cdot y_{ij} \le Q_j \cdot x_j,\quad \forall j \in J $$

预算约束：

$$ \sum_{j \in J} C_j \cdot x_j \le B $$

数量约束：有些区域受空域、土地审批限制，机巢总数不能超过(N_{max})。

$$ \sum_{j \in J} x_j \le N_{max} $$

这套模型本质上是一个带容量和预算的集合覆盖问题变体。需求点和候选点规模一旦超过几十个，精确算法就会卡住，所以要用启发式算法找近似最优解。

2.3 多目标与量纲归一化

在把目标函数写进代码前，必须先做量纲归一化，否则成本是几十万量级，覆盖率是0到1的小数，加权时覆盖率项会被完全淹没。我习惯把成本项也化为相对值，除以总预算上限B，让三个分项都在0~1之间。权重系数则在归一化后调整。

公式就变成了：

$$ \min Z = -\alpha\sum_{i} \frac{w_i cov_i}{\sum_i w_i} + \beta\frac{\sum_j C_jx_j}{B} + \gamma\sum_{i} \frac{w_i(1-cov_i)}{\sum_i w_i} $$

这样三个分项量纲一致，权重系数更容易解释。(\alpha)和(\beta)调节覆盖和成本的偏好：试点期看重覆盖率，(\alpha)取0.7、(\beta)取0.2；运行期控制成本，(\alpha)取0.4、(\beta)取0.5。(\gamma)通常略大于(\beta)，让漏检惩罚高于成本节约的诱惑。

3. 求解思路：规模让你放弃穷举，启发式算法是主力

3.1 先算一道“穷举算力账”

很多第一次做选址的工程师第一反应是枚举所有组合。我们算一笔账：假设候选机巢10个，计划建3个，组合数(C(10,3)=120)，穷举确实完全可以。但实际项目里候选点至少30个，目标选6~8个，组合数就是(C(30,6)=593775)，每个组合还要评估30个需求点的覆盖情况和路径检查。即便Matlab循环写得很快，也要跑很久，更别提50个候选点选10个，组合数已经上亿。

工程上做方案比选时，我们经常要做参数敏感性分析：改一下覆盖半径跑一遍，改一下预算上限再跑一遍。如果一次求解要花几十分钟，根本没法做多方案对比。所以需要一个能在几十秒内给出稳定近似解的算法。

3.2 为什么我最后选遗传算法

选址问题常用的启发式算法有遗传算法、模拟退火、粒子群、蚁群优化。这几个我都试过，对于“机巢数量少、候选点规模中等”的问题，粒子群容易在离散编码上施展不开，模拟退火对初始温度敏感，蚁群算法参数更多，最后我主力用的是遗传算法。

原因很简单：决策变量天生是0-1离散型，正好对应二进制染色体；交叉、变异算子语义清晰；Matlab里无论是用全局优化工具箱的ga函数还是自写主循环，调试都方便；而且遗传算法能配合罚函数处理多种约束，不用为每个约束单独设计修复逻辑。另一个重要原因是团队同事接手容易，遗传算法的概念大家多少都了解，后续改需求时沟通成本低。

要注意的是，遗传算法不是“原地起高楼”，它还需要一个不错的初始种群。我的做法是先用贪心策略生成一批解：每次优先选择“未覆盖权重最大”的候选点建巢，重复直到满足数量约束。把贪心解混入随机初始种群，能让算法前期收敛速度快很多，最终结果也更稳定。

3.3 约束处理的两条路：罚函数法与可行解修正

约束处理直接影响算法能不能在可接受时间内找到可用解。一条路是罚函数法，在目标函数值上加上违约量的倍数。另一条路是可行解修正，每次交叉变异后检查染色体是否满足硬约束，不满足就修复。

我在代码里两条路都用了。预算和数量约束用可行解修正：如果染色体里选中的机巢数超过(N_{max})，就把超出的机巢按覆盖率贡献排序，删掉贡献最小的机巢，直到数量达标。这样的好处是算法搜索空间始终在可行域附近，不会浪费时间在明显不可能的方案上。覆盖率本身是目标的一部分，不用强制约束；容量约束我用罚函数处理，因为容量稍微超过一点可以通过调度排班来弥补，不值得为它严格惩罚到排除所有解。

但罚函数系数不能拍脑袋。我一般先跑一次不带容量罚项的实验，看目标函数各分项的量级，再让容量罚系数比未覆盖惩罚高5~8倍。太大容易让算法过早收敛到少数几个可行解，太小则可能出现大量超容量解霸占种群。

4. Matlab代码实现：核心模块与可直接套用的骨架

4.1 数据组织与距离矩阵预处理

写代码之前，先把数据管理好。我习惯用三个矩阵：demandCoord是需求点坐标，candCoord是候选机巢坐标，demandW是需求点权重向量。候选点的建巢成本存在candCost向量里。

距离矩阵预处理是整个程序的第一个关键模块。如果坐标是经纬度，不要直接用pdist2算欧氏距离，那样误差很大。我一般先用projcrs投影到当地平面坐标系，或者用deg2km做近似。无人机巡检覆盖半径通常只有几公里到十几公里，投影后的平面坐标足够用。如果是小范围高精度需求，用UTM投影。

处理高差时，我可以把距离矩阵写成：

% avoid: pdist2 in geographic coordinates directly x1 = demandCoord(:,1); y1 = demandCoord(:,2); x2 = candCoord(:,1); y2 = candCoord(:,2); h1 = demandCoord(:,3); h2 = candCoord(:,3); dx = x1 - x2'; % nDemand x nCand dy = y1 - y2'; dh = h1 - h2'; horizDist = sqrt(dx.^2 + dy.^2); % 将累计爬升按比例计入等效飞行距离 climbFactor = 0.15; % 经验系数，看地形复杂度 D = sqrt(horizDist.^2 + (dh * climbFactor).^2);

climbFactor我取0.1~0.3，山区取大值。这个经验系数对应的是“额外爬升能耗折算成水平距离”，不要求很精确，只要能让算法避开高差过大的候选点即可。如果项目有DEM数据，可以把这部分替换成沿剖面的真实累计爬升，效果更准。

4.2 遗传算法主循环结构

遗传算法主循环我通常不用工具箱的ga，而是自己写一个短循环，方便在中间插入调试代码和自定义约束。主流程就是初始化种群、计算适应度、选择、交叉、变异、修复、重复迭代。

% 参数 popSize = 80; maxGen = 300; nCand = size(candCoord, 1); needSelect = 4; % 计划建巢数量 % 种群初始化：每行是一个染色体，1表示选中该候选点 pop = initPopMix(nCand, needSelect, popSize, D, R, demandW); bestFit = zeros(maxGen, 1); for gen = 1:maxGen fit = calcFitness(pop, D, R, demandW, candCost, budget, needSelect); bestFit(gen) = min(fit); % 选择 parents = tournamentSelect(pop, fit, 2, 3); % 交叉 newPop = crossoverUniform(parents, popSize); % 变异 newPop = mutateBitFlip(newPop, 0.05, nCand); % 修复：保证每个染色体的选中数等于 needSelect newPop = repairChromosome(newPop, needSelect); % 精英保留 pop = elitistReplacement(pop, newPop, fit, 2); end

选择我用锦标赛选择，锦标赛规模3；交叉用均匀交叉，每个基因位以0.5的概率交换父本染色体；变异采用位翻转，变异率0.05。修复函数把0/1个数调整到恰好等于needSelect，保证种群中所有解都满足数量硬约束。

4.3 适应度函数里最容易被忽略的细节

适应度函数是整个代码的灵魂，写错一个符号，算法结果就全偏了。我最容易踩的坑有两个：一是没有对空染色体设Inf，导致一窝蜂选择“什么都不建”的解；二是距离矩阵在覆盖判定时用了“所有选中机巢中最小距离”，但忘了给每个机巢加容量上限。

先看适应度函数骨架：

function [fit, info] = calcFitness(pop, D, R, demandW, candCost, budget, needSelect) nPop = size(pop, 1); nDemand = size(D, 1); fit = zeros(nPop, 1); info = zeros(nPop, 1); for k = 1:nPop sel = find(pop(k, :)); if length(sel) < needSelect fit(k) = Inf; % 硬性约束不满足 continue; end % 每个需求点到最近选中机巢的距离 minD = min(D(:, sel), [], 2); covered = minD <= R; % 覆盖收益归一化 coverRate = sum(demandW(covered)) / sum(demandW); % 成本项归一化 cost = sum(candCost(sel)); costTerm = max(0, cost - budget) / budget; % 容量罚项 serviced = sum(minD <= R, 2); % 被几个机巢覆盖 capacityViol = sum(max(0, serviced - 3)); % 假设每巢最多覆盖3个需求点(示例) % 目标越小越好：没覆盖惩罚 + 成本惩罚 + 容量罚 fit(k) = (1 - coverRate) + 0.3 * costTerm + 0.8 * capacityViol; end end

注意这里serviced = sum(minD <= R, 2)写的是每个需求点被多少个选中机巢覆盖，但容量罚应该是“每个机巢服务了多少需求点”，方向反了。实际代码里需要分别循环机巢统计覆盖数量，再对超额的机巢叠加惩罚。我故意把这个容易写反的地方点出来，因为这是我在调试时卡过一个下午的问题。

正确的容量统计思路是：对每个选中的机巢，统计落在其半径内的需求点集合，判断集合大小是否超过上限。若超过，把超出部分的覆盖率折算成罚项。实际项目中，我会把容量约束放进修复阶段而不是罚函数，这样迭代更快。但如果你希望保留少量超容量解以便后续调度调整，就留在罚函数里。

4.4 可视化与结果输出

算完不能只给一串0和1，要把结果画出来给现场评审看。我通常画三样东西：候选点和需求点分布图、机巢覆盖范围图、迭代收敛曲线。

覆盖范围图用viscircles画圆，展开来看是否真的覆盖了计划中的高权重目标。但我提醒一句：这个圆只是等效覆盖半径的示意，不是真实航迹范围，向领导汇报时最好标注“示意”二字，避免被误解为精确空域范围。

收敛曲线也有讲究。我关心的不是最后的适应度值，而是曲线是否在最后20代还继续下降。如果还在明显下降，说明迭代代数不够，要加大maxGen；如果前期就平了，可能是种群多样性丢失，要调高变异率或提高锦标赛规模。

5. 算例演示：一组模拟数据下，算法相比随机布点强在哪

5.1 测试参数设定

为了说明算法效果，我构造了一组模拟数据，尽量贴近实际。假设一片巡检区域内共有30个需求点，对应30基重要杆塔或线路巡检区段；预选候选机巢10个，计划建巢数量固定为4个；无人机等效覆盖半径R取9km；需求点权重按线路重要程度分成1、2、3三档；机巢建设成本在20万~35万之间，预算上限100万。

迭代参数：种群规模80，迭代300代，交叉概率0.8，变异概率0.05，锦标赛规模3，精英保留2个个体。因为成本约束用罚函数处理，所以还需要设定成本罚项权重。我设成本罚项权重为0.3，覆盖漏检权重为1，容量罚权重0.5。

5.2 结果对比与分析

先跑随机布点作为基准。随机从10个候选点里抽4个，重复50次，取覆盖效果最好的一次：覆盖需求点23个，覆盖权重和占总权重的81.6%，总建设成本83万元。

再用遗传算法跑一遍，结果选中4个机巢：覆盖需求点28个，覆盖权重和达到95.3%，总建设成本92万元。表面看成本增加了9万元，但漏检的重点需求点从4个降到1个，而且漏掉的那个点权重是最低的。从资产风险角度讲，这个增加非常划算。

方案差异的核心在于：随机布点往往把机巢扎堆放在需求点密集的区域，导致某些边缘塔位没人管；遗传算法在适应度函数里加了漏检权重惩罚，高权重的保供线路塔位一旦漏检会大幅拉低适应度，所以算法宁可多花点成本，也要把高权重目标覆盖掉。

5.3 权重变化对选址结果的影响

真正做项目时，预算与覆盖率的关系不会那么理想，通常是一个折中曲线。我通过调整目标函数中成本项的权重系数(\beta)，得到了一组曲线：当成本权重从0.1增加到0.6，算法选中的机巢数量从5个降到2个，覆盖权重占比从97.2%降到68.4%。这组数据说明一个问题：如果项目总预算压得太死，必然牺牲对部分重要杆塔的巡检覆盖。这个折中曲线应该提前算给决策者看，而不是等他们拍板之后再做方案。

我还尝试过把需求点权重全设为1，即不考虑重要性差异。这时算法倾向于均匀布点，覆盖率高但高价值线路的冗余覆盖少了，成本反而可能更高。实际操作中，权重设置要听取运维班组意见，他们会告诉你哪些塔在雷雨季最容易遭雷击，哪些线路段是外破高发区，这些信息比任何公式都值钱。

6. 参考文献清单与实战避坑经验

6.1 可直接检索的参考文献方向

“附Matlab代码参考文献”这个需求，其实是想给算法一个理论依据，避免方案评审时被说“不严谨”。我建议按下面几个方向查文献，都是设施选址和无人机调度领域的经典脉络。

要特别提醒一句：海外文献里无人机机巢更常见的词是“depot”或“landing site”，而不是“nest”。“nest”在英文文献里多是鸟巢或仿生结构。如果你拿“UAV nest placement”去搜，效果可能不理想，换“UAV depot location problem”或“battery swapping station location”会好很多。

6.2 踩坑记录：坐标系、时间窗和惩罚系数

这个算法我前后改了三版，踩过的坑值得单独记录。

第一，坐标系坑。最早版本直接用WGS84经纬度算距离，导致候选机巢在高纬度地区计算距离偏小、覆盖半径虚高。后来改成投影坐标才正常。只要项目范围跨几个县，就必须用当地中央经线的高斯-克吕格投影，否则覆盖边界会偏差好几公里。

第二，时间窗约束的“等效距离”一开始我写到了约束条件里，但罚函数系数和覆盖项打架。后来我把时间窗约束转成硬约束：凡是不满足响应时间的需求点，直接视为未覆盖，进入漏检惩罚项。这样比罚函数更干净，也方便解释结果。

第三，造价权重过大时，算法会倾向于建一个机巢都没有。这个情况初始化时就要避免，我通过硬约束确保选中机巢数不小于1，再在修复阶段把数量目标锁死。否则迭代前几代会出现大量全零染色体，适应度函数直接崩了。

第四，Matlab自带的ga函数虽然能用，但想加入容量罚和候选点通视过滤，还是要自己写主循环。工具箱函数适合交作业演示，不太适合工程上反复调整约束的场景。

6.3 从选址算法到巡检方案的后续扩展

这套代码跑通后，还可以往两个方向扩展。一是把单一机巢选址升级为“机巢+临时起降点”的两级部署，巡检线路特别长的区域，可以设置临时起降点，配合人工更换电池完成更远距离任务。二是把静态选址改为动态调度：当某个机巢故障或空域临时管控时，算法快速重算覆盖，把受影响任务转移给相邻机巢。这两个方向的Matlab框架都已经有了，后面有时间再单独写一篇展开。

最后分享一个我个人沿用的验证习惯：每次用启发式算法拿到结果，我都会把小规模问题（比如10个候选点选3个）用intlinprog跑一遍精确解，对比一下遗传算法的误差。如果差距超过5%，就去检查罚函数系数和变异算子，而不是急着改参数。这个习惯帮我抓出了好几次因为编码错误导致的“伪最优解”。