3. 集中式任务分配方法

集中式任务分配的基本假设是：存在一个信息汇聚节点（地面站或集群中的领航/计算节点），它掌握全部无人机的位置、速度、剩余电量、载荷状态以及全部任务点的位置、优先级、时间窗等参数，并在此全局信息上求解一个统一的分配方案。与分布式方法相比，集中式方法的最大优势是解的质量有理论保证，代价是通信与计算开销集中在单点，且对信息时效性敏感。本节围绕四种典型方法展开：匈牙利算法、整数线性规划（ILP）、分支定界（B&B）与拍卖算法。

一、统一的问题描述：从物理任务到代价矩阵

设集群有 N 架无人机 U={u₁,…,u_N}，M 个任务 T={t₁,…,t_M}。集中式分配的第一步是把物理约束折算成一张代价矩阵 C，其中 c_ij 表示无人机 u_i 执行任务 t_j 的综合代价。工程上常用加权形式：

c_ij = w1 * d_ij / v_i          // 飞行时间代价
     + w2 * (E_need_ij / E_remain_i)  // 电量消耗比
     + w3 * risk_ij             // 威胁/禁飞区风险
     + w4 * (1 - fit_ij)        // 载荷-任务匹配度

其中 d_ij 为欧氏距离，v_i 为巡航速度，E_need_ij 为往返加作业的估算耗电，E_remain_i 为当前剩余电量，risk_ij 为路径穿越威胁区的风险值，fit_ij∈[0,1] 为载荷能力与任务需求的匹配度。权重 w1~w4 由任务类型决定，例如侦察任务可提高 w1、w3，而中继通信任务可提高 w4。若某无人机无法执行某任务（如载荷不匹配、电量不足），则令 c_ij = +∞，在求解时视为禁止分配。这一步是四种算法共同的输入，也是实际工程中最容易出错、最需要校验的环节。

二、匈牙利算法：一对一最优匹配

匈牙利算法（Kuhn-Munkres 算法）解决的是指派问题：N 架无人机与 M 个任务一一配对，使总代价最小。它要求 N=M 或通过补零行/列扩展为方阵，且每个任务只被一架无人机执行。算法核心是不断寻找增广路径，通过行归约、列归约与覆盖零元素，把代价矩阵逐步转化为含 N 个独立零元素的形式，最终得到最优指派。

以一个 4 机 4 任务示例说明：代价矩阵（单位：归一化代价）为

        t1   t2   t3   t4
u1      4    1    3    2
u2      2    0    5    3
u3      3    2    2    4
u4      1    3    2    5

行归约后每行减去本行最小值，再列归约，随后用最少的横竖线覆盖所有零元素。若覆盖线数小于 4，则对未被覆盖元素减去最小值、对交叉元素加上最小值，重复直至覆盖线数等于 4，此时可读出最优指派。该示例的典型最优解为 u1→t2、u2→t1、u3→t3、u4→t4，总代价为 1+2+2+5=10。匈牙利算法的复杂度为 O(n³)，在 N≤100 的集群规模下实时性可接受，但它只能处理“一机一任务”的硬指派，无法直接表达“一架无人机可依次执行多个任务”或“一个任务需要多机协同”的情形。

三、整数线性规划：可扩展的通用建模框架

ILP 把分配问题写成 0-1 决策变量 x_ij∈{0,1}，目标函数为最小化 ΣΣ c_ij x_ij，约束包括：每个任务至多被一架无人机执行 Σ_i x_ij ≤ 1；每架无人机至多执行一个任务 Σ_j x_ij ≤ 1；以及电量、时间窗、载荷等附加约束。相比匈牙利算法，ILP 的优势在于可以自然加入多任务序列、任务优先级、协同约束等，例如引入 x_ijk 表示无人机 i 依次执行任务 j 后执行任务 k，从而把路径规划与任务分配耦合起来。

ILP 的求解通常借助分支定界或割平面法。工程实现中常用求解器（如 CBC、GLPK、Gurobi）直接建模求解，也可用 Python 的 PuLP 或 OR-Tools 描述。需要注意：ILP 是 NP-hard 问题，当 N、M 增大到数百时求解时间可能急剧上升，因此实际系统常设置求解时间上限，超时后返回当前最优可行解（次优解）作为兜底。

四、分支定界：在解空间中剪枝搜索

分支定界并不直接求解 ILP，而是把 0-1 变量松弛为连续变量，先求线性松弛解。若松弛解恰好为整数，则它就是原问题最优解；若含小数，则选择一个小数变量分别固定为 0 和 1，形成两个子问题（分支）。每个子问题的松弛解给出该分支的下界，若某分支下界已大于当前已知可行解（上界），则该分支不可能产生更优解，直接剪枝。如此反复，直到所有分支被剪掉或求得整数解。

分支定界的效率高度依赖分支变量选择与下界紧致程度。在集群分配中，一个实用技巧是先用匈牙利算法或贪心法快速得到一个可行解作为初始上界，再启动分支定界，可显著减少搜索节点数。下表对比四种方法的关键特性。

五、拍卖算法：以竞价机制逼近最优

拍卖算法把任务看作待售物品，无人机作为竞标者。每架无人机对任务 j 的出价为 c_ij 减去当前价格 p_j，即净收益 a_ij = c_ij - p_j。每轮中，每架无人机选择净收益最大的任务并提交报价，任务价格按超出第二优报价的差额上浮。价格上升会逐步抑制冲突，最终每个任务被分配给净收益最高的无人机。集中式拍卖由中心节点统一收集报价并更新价格，分布式拍卖则由各机通过通信协商价格。

拍卖算法的优点是迭代结构简单、易于并行、对通信中断有一定容忍度，且当价格增量足够小时可收敛到接近最优的解。其代价是收敛速度受价格增量影响：增量太小则迭代次数多，增量太大则解质量下降。工程上常设置最大迭代次数与价格增量自适应策略，在实时性与最优性之间折中。

六、实现与选型建议

实际系统中，四种方法并非互斥。一种常见的分层策略是：先用匈牙利算法或拍卖算法在毫秒级给出初始分配，作为分支定界的上界；若时间允许，再用 ILP 或分支定界在限定时间内优化，超时则回退到初始解。对于任务数远大于无人机数、且允许一机多任务的场景，应优先使用 ILP 建模；对于强实时、大规模集群，拍卖算法更合适；对于小规模、要求严格最优的侦察任务，匈牙利算法与分支定界组合最为稳妥。

综上，匈牙利算法适合严格一对一且规模适中的最优指派；ILP 提供最通用的建模能力，但需接受求解时间的不确定性；分支定界是 ILP 的求解引擎，其效果取决于上界质量与剪枝策略；拍卖算法以迭代竞价换取可扩展性与实时性。理解四者的输入、约束表达能力和复杂度边界，才能在集群任务分配中做出合理的工程选型。