EDP Sciences logo
Submit your paper
Search
Menu
All issues Volume 44 / No 1 (February 2026) JNWPU, 44 1 (2026) 102-111 Full HTML
Open Access
Issue
JNWPU
Volume 44, Number 1, February 2026
Page(s) 102 - 111
DOI https://doi.org/10.1051/jnwpu/20264410102
Published online 27 April 2026

© 2026 Journal of Northwestern Polytechnical University. All rights reserved.

Licence Creative CommonsThis is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

现代战场环境充满了不确定性和复杂性, 任务需求各不相同, 而飞机的性能也存在显著差异1], 这使得任务预分配面临着巨大挑战。任务预分配不仅需要在广阔的解空间中寻找最优或近优解, 而且还需要满足多个约束条件, 如任务的优先级、资源的分配限制、平台的性能特征等2-3]。由于任务需求的多样性和飞机性能特点各异, 模型可能展现出多个潜在的局部最优值, 进而使得求解流程变得复杂且计算成本上升。然而, 在任务预分配阶段, 得益于较为宽松的时间安排, 研究者得以深入进行计算与评估。因此, 他们更加重视构建合理的分配策略4-6], 旨在确保任务执行的高效性以及平台资源的最优化部署。任务预分配阶段的优化方案将直接影响后续任务动态分配的效果, 因此, 对预分配方案的优化研究至关重要。

为了更系统、更高效地解决多机协同任务预分配问题, 许多学者已经采用了多种数学模型和求解方法。例如, 整数规划模型7]、旅行商问题(TSP)模型8-9]、资源分配模型10-11]等方法被广泛应用于任务分配研究。群体智12-15]凭借其快速的收敛速度和强大的种群多样性保持能力, 在多目标组合优化问题的求解领域内得到了广泛应用。

针对任务预分配问题, 将大规模邻域搜索算法(large neighborhood search, LNS)和沙猫群算法(sand cat swarm optimization, SCSO)结合, 提出了改进沙猫算法(LNSCSO)。首先分析了沙猫群算法的基本原理, 并指出其易早熟和种群多样性降低等问题。为此, 引入了非线性收敛因子和外部存储集更新策略, 并将其与大规模邻域搜索算法结合, 添加了破坏算子和修复算子。最后在带时间窗的车辆路径问题和多异构有人/无人机的对地侦察/攻击任务分配场景中进行验证。仿真结果表明, 改进沙猫群算法在任务分配问题中具有较强的有效性。

1 多机协同任务分配

1.1 问题描述

设飞机集合U由M架飞机组成, 表示为U={Ui|i=1, 2, …, M}, 其中Ui代表第i架飞机。设任务集合T, 包含N个任务, 记作T={Ti|i=1, 2, …, N}, Ti代表第i个任务。

我方飞机划分为侦察与攻击2类, 任务也分为侦察和攻击2种。在执行任务时, 不同飞机在执行相同或不同任务时, 收益和威胁均有所不同, 这导致任务分配的结果可能多种多样。在多机协同任务分配流程中, 首要步骤是全面搜集战场敌我双方的信息。然后, 通过任务效能评估模型计算和判断每架飞机执行特定任务的适合程度。最后, 依据这些计算结果, 生成一系列任务执行顺序的候选方案。多机协同任务分配模型框图如图 1所示。

Thumbnail: 图1 Refer to the following caption and surrounding text. 图1

多机协同任务分配模型框图

1.2 任务分配评价指标

本文所提出的任务分配模型是在综合考虑毁伤概率、任务价值、任务时序等多个因素的基础上构建的。每一项因素都直接影响任务执行的效果和风险, 因此必须全面评估并合理权衡。为便于后续表达, 定义了相应的决策变量Xij。

Mathematical equation(1)

式中：Xij代表飞机Ui执行任务Tj的决策变量; Xij=0代表飞机Ui不执行任务Tj; Xij=1代表飞机Ui执行任务Tj。

针对任务集合T中的任意元素Tj, 其属性集包括IT, LT, VT, ST, QT, TT, NT。IT是任务的唯一身份标识; LT指明了任务发生的地理坐标; VT评估了任务的重要性或潜在价值; ST是一个矩阵, 用于定义任务间的执行先后关系, 其中ST=1表明Tj紧随Ti之后执行, 若ST=0则无特定顺序要求; 飞机需求QT代表了执行该任务所需的最少飞机数; 类型TT将任务分为2类, 1代表侦察, 2代表攻击; 有效性NT是一个标志位, NT=1意味任务处于有效状态, NT=0则表明任务无效。

针对集合U中的任意飞机实例Uj, 其属性集合包括IU, LU, VU, DU, WU, PUD, PUW, PUI。飞机编号IU是每架飞机的唯一身份标识; 坐标位置LU表明了飞机的当前地理位置; 飞机价值VU是对飞机整体性能的评估; 最大侦察任务数DU和最大攻击任务数WU分别限定了飞机可执行侦察与攻击任务的最大数量; 目标探测概率集PUD详细列出了飞机对各个潜在目标的探测能力; 目标毁伤概率集PUW则揭示了飞机对各目标的破坏能力; 任务存活概率集PUI综合反映了飞机在执行各类任务时面对不同威胁的生存几率。任务分配的作战收益、威胁代价、航程代价、总体效能数学模型如下所示。

1) 多机协同作战收益

飞机Ui完成侦察任务Tj, 获得的收益RijD为

Mathematical equation(2)

飞机Ui完成攻击任务Tj, 获得的收益RijW为

Mathematical equation(3)

当m架飞机, 编号为Ui, i取1, 2, …, m均参与执行侦察任务Tj时, 它们分配任务后得到的侦察效益表示为CjD。

Mathematical equation(4)

当m架飞机, 编号为Ui, i取1, 2, …, m, 共同参与并执行任务Tj时, 这些飞机在任务分配后所能获得的收益记为CjW。

Mathematical equation(5)

多无机执行对地作战任务中的收益RT为

Mathematical equation(6)

2) 多机协同作战威胁代价

当飞机Ui执行任务Tj(j=1, 2, …, r)时, 飞机Ui执行任务的威胁代价Cik为

Mathematical equation(7)

类比任务分配的总体收益, 总体威胁代价CTk具体形式为

Mathematical equation(8)

3) 多机协同作战航程代价

假设飞机Ui执行任务Tj(j=1, 2, …, r)时, j为飞机执行的顺序并且任务之间没有障碍, 单架飞机执行任务集合的航程代价Cid为

Mathematical equation(9)

类比可知总体航程代价CTd为

Mathematical equation(10)

在实战情境下, 飞行路线的成本会受到禁飞区、山地风险、防空系统等多种因素的制约。为应对这一问题, 构建了一个(M+N)×N的矩阵, 其初始赋值暂以飞机与任务、或任务之间的直接几何距离作为替代。随着算法迭代及航迹规划工作的深入, 矩阵会根据实际飞行中对障碍物的规避情况不断更新, 从而确保飞行成本估算的精确性。

4) 飞机协同作战的总体效能

多机协同作战鉴于任务效益、威胁损耗及飞行路程等因素间的内在冲突, 导致最终的最优方案并非固定不变。为此, 本文拟采用加权策略, 将多个性能指标整合成一个统一的优化目标。鉴于这些指标的量纲各不相同, 需要先进行归一化处理, 以确保它们在同一基准上进行比较。在此基础上, 整体效能的评估公式为

Mathematical equation(11)

在此模型中, ω1, ω2, ω3被设定为任务总效益、威胁代价及飞行总距离的权重因子, 它们的具体数值由指挥决策者根据任务需求进行分配, 且必须满足总和为1的条件。VT, m代表任务集合内任务价值的最高值; VU, m为飞机集合中性能最优飞机的价值; dm是利用凸包算法得出的最小包围周长, 作为评估飞行距离的一个基准值。

1.3 任务分配约束条件

为了更精确地模拟战场实际情况, 本文设计了以下约束条件模型。

1) 飞机任务承载量限制

鉴于飞机在执行任务时的载荷与性能限制, 每架飞机可执行的任务数量被设定在一定范围内。因此, 引入了任务承载量上限的约束, 确保每架飞机的任务分配量不超过其最大承载能力。

Mathematical equation(12)

2) 任务目标所需飞机数量约束

指挥中心根据任务类型, 确定每个任务需要多少架飞机参与执行。因此, 对于每个任务, 都有一个明确的飞机数量需求。该约束确保每个任务能够分配足够数量的飞机。

Mathematical equation(13)

3) 飞机最大航程约束

由于飞机之间存在性能差异, 且每架飞机的油量有限, 因此需要保证飞机在完成任务后, 能够安全返回机场。此约束确保飞机在执行任务后有足够的油量, 以完成往返航程并安全着陆。

Mathematical equation(14)

2 改进沙猫算法

2.1 SCSO算法

沙猫群算法(SCSO)由Seyyedabbasi等16]研究者在2022年首次提出。该算法通过模拟沙猫在沙漠中捕猎和觅食的行为, 设计了一种高效的优化方法。沙猫群算法可分为探索阶段和开发阶段2个阶段17-18]。

1) 搜索阶段

沙猫能够感知并响应低于2 kHz的低频声波, 这使其在夜间或在视距较远的情况下寻找猎物时具有显著的优势。结合这种特性, 算法对沙猫个体灵敏度范围进行设计。在寻找猎物的搜索阶段, 根据其低频感知能力, 假设沙猫灵敏度范围从2 kHz到0, 搜索时沙猫利用随机向量R来指导其搜索过程。当 R >1时, 表明沙猫检测到的低频信号强度已经超过了某一临界值, 从而促使其进行进一步的猎物搜索。听觉范围rG为

Mathematical equation(15)

式中: sM为初始收敛因子最大值, 由于sM值受到沙猫听力特征的启发, 因此假设其值为2。iC代表种群当前迭代次数, im代表种群最大迭代次数。

在沙猫算法的搜索过程中, R作为一个关键的引导参数, 决定了沙猫在当前迭代中是进行全局探索(搜索)还是局部聚焦(开发)行为。随着迭代次数的增加, 参数R会根据沙猫当前位置的动态变化进行调整, 从而实现从广泛搜索到精确攻击的平滑过渡。R的更新方式为

Mathematical equation(16)

在算法初始化阶段, 各沙猫个体的搜索空间被随机设定在预设的边界范围内。搜索过程中, 个体位置更新依据随机选取的参考点进行动态调整。为避免算法陷入局部最优, 系统为每个个体设置了差异化的灵敏度参数: r表征个体特定的灵敏度阈值, 而rG则表示全局基准灵敏度范围。参数r作用于搜索与攻击阶段的局部优化过程, 而rG则通过调节全局引导因子R来协调不同阶段间的转换机制。这种双层级灵敏度调控策略既保障了个体探索的自主性, 又维持了种群整体的协同演化方向。

Mathematical equation(17)

沙猫算法在更新其位置时, 采用了一种基于全局最优解Pb(t)、自己当前位置Pc(t)以及灵敏度范围r的策略, 从而有效地引导沙猫朝着猎物的位置靠近。

Mathematical equation(18)

2) 开发阶段

沙猫攻击时的活动范围为圆形, 其移动导向由圆上任一随机角度θ确定, 该角度θ随机分布在0°~360°间, 对应数值范围从-1~1, 在探索区域内, 群体内的每只沙猫都能按照各自独特的圆周轨迹移动。SCSO算法借助轮盘赌选择策略, 为每只沙猫分配一个随机角度, 从而避开局部最优解。位置更新如图 2所示，其位置更新策略为：

Mathematical equation(19)

Mathematical equation(20)

Thumbnail: 图2 Refer to the following caption and surrounding text. 图2

迭代中的位置更新

3) 搜索和开发阶段

搜索与开发阶段的切换通过自适应参数rG和引导因子R协同实现。其中, R的数学期望与rG呈线性关联, 其变化幅度随rG的衰减而逐步收敛。具体而言, R的取值范围被约束为[-2rG, 2rG], 而rG本身在迭代过程中由初始值2线性递减至0。当|R|≤1时, 算法进入攻击模式, 此时沙猫的位置更新策略调整为

Mathematical equation(21)

在引导参数|R|>1时进行搜索, 其更新方式如(22)式所示。

Mathematical equation(22)

2.2 非线性收敛因子

在SCSO中, 算法的搜索和开发过程主要通过收敛因子rG来进行控制。LNSCSO算法流程图如图 3所示。

Thumbnail: 图3 Refer to the following caption and surrounding text. 图3

LNSCSO算法流程图

在传统方法中, 收敛因子往往线性衰减, 这意味着随着迭代次数增加, 收敛因子值逐渐减小。然而, 这种线性衰减方式可能无法充分挖掘搜索空间中的潜在解, 容易导致搜索范围过于狭窄。本文提出了一种非线性收敛因子rG的设计方案, 具体表达式为

Mathematical equation(23)

式中：sM为初始收敛因子的最大值；t为当前的迭代次数；tm为最大迭代次数。这种非线性设计使得收敛因子的变化不再是单纯的线性衰减, 收敛因子在算法初期会保持较高值, 从而增强探索能力; 随着迭代次数增加, 收敛因子逐渐减小, 促进算法在解空间中聚焦于潜在的最优解。

2.3 外部存储集更新

在LNSCSO算法的迭代升级中, 个体位置的更新始终围绕全局最优个体的选定展开, 这一选择对LNSCSO的寻优性能与搜索速度具有重要影响。外部存储集更新策略借助非支配排序方法从种群中筛选出最优的Pareto前沿解集, 随后将其整合至外部存储库中。随着种群的迭代更新, 新的Pareto前沿解集会不断被添加到外部存储库, 并重新进行非支配排序, 以保障所有非支配解得以保留。为了有效管理外部存储库的大小, 一旦存储库中的个体数目超出预设的最大容量, 本研究设计了一种轮盘赌选择策略, 依据个体对应的概率pi决定并剔除冗余的个体。概率pi的计算公式为

Mathematical equation(24)

式中: ni指围绕第i个解决方案的相邻解决方案数量。对于全局最优解的挑选, 采用轮盘赌选择机制, 并依据特定的概率qi完成, 概率qi的计算公式为

Mathematical equation(25)

通过该机制, 能够在外部储存集个体中根据拥挤度进行选择, 使得较为拥挤的区域能够被有效减少, 从而保持解集的多样性, 并提高全局搜索的效率。

2.4 破坏算子和修复算子

大规模邻域搜索算法(LNS)在处理复杂的、规模较大的问题时, 能够有效地探索解空间并寻找近似最优解19-20]。LNS的核心思想是在当前解的基础上对其进行局部修改, 从而探索更大的解空间, 并在此过程中通过“破坏”当前解并“修复”其结构来改善解的质量。

破坏因子控制着从当前解中移除或修改部分元素的比例, 从而“破坏”当前解的结构。破坏的目标是将当前解的某些部分进行随机删除或调整, 以创造出一个新的解空间, 避免陷入局部最优解。根据相似性, 破坏算子从路径中剔除若干相似性较高的顾客, 计算公式为

Mathematical equation(26)

式中, c′ij为将cij标准化后的值, 范围在[0, 1];cij为i与j之间的欧氏距离。

Mathematical equation(27)

当任务点i和任务点j位于同一路径时, Vij值为0;若不在同一路径, 则Vij值为1。R(i, j)用于衡量任务点和任务点j之间的关联度, R(i, j)越大, 说明两者之间的关联性越强。设定总任务点数为N, 需移除的任务点数为q, 并引入随机变量D。破坏算子的伪代码如算法1所示。

算法1  破坏算子的伪代码

输入: 当前解S，要移除的任务点数目q，随机元D

输出: 破坏后的解Sd，移除任务点的集合I

1: while |I| >q do

2: 随机选择任务点ic，ic属于集合I

3: i < j⇒R(ic, L[i]) < R(ic, L[j])

4: k→[randD|L|]//计算随机选择任务点序号

5: I→I∪{Lk}

6: end while

7: return Sd和I

修复算子在符合弹药装载约束和时间窗约束的前提下, 将之前移除的客户重新分配到最合适的插入位置, 从而最小化飞机行驶总距离。修复算子伪代码如算法2所示。

算法2   修复算子的伪代码

输入: 破坏后的解Sd，移除任务点的集合I

输出: 修复后的解S

1: 从解S中随机选出任务点is，并把is放入集合I中

2: S←Sd

3: while |I| do

4:   计算I中任务点的最小插入成本zi=minΔfi, k //minΔfi, k是距离增量

5:   计算zi对应的插回路径编号ri和该路径上的插回位置posi

6:   i<j⇒R(ic, L[i]) < R(ic, L[j]) //将排序结果存储在排序序列L中

7:   若无路径添加任务点i，新建路径添加任务点i

8:   从I中选择maxzi的任务点iz

9:   将任务点iz插入到S中第ri, z条路径上第posi, z个位置

10:   将任务点iz从I中移除

11: end while

12: return S

破坏因子决定了当前解的破坏程度, 进而决定了算法在解空间中的探索范围。修复因子则用于修复破坏后的解, 确保修复后的解合法并且具备改进的潜力。破坏因子和修复因子在大规模邻域搜索算法中往往是紧密结合的, 二者的相互作用决定了算法的搜索策略和局部搜索能力。

2.5 算法性能对比

为了验证改进沙猫算法在解决VRPTW优化问题中的有效性与优越性, 本文采用了遗传算法、鲸鱼算法以及狐猴算法进行对比实验。这些算法均添加破坏算子和修复算子, 以提高在复杂问题求解中的表现。在实验设计中, 各个算法的种群规模均设置为50, 最大迭代次数设为200。为了消除初始条件对实验结果的干扰, 所有算法均采用相同的编码方式, 并随机生成初始种群。

同一仿真实验中, 4种不同算法分别经200次迭代, 以车辆行驶总距离为算法适应度值, 最终得到了各自的适应度变化曲线, 如图 4所示。通过对比分析, 改进的沙猫算法在初期迭代中表现出较快的适应度提升, 而在后期阶段逐渐收敛至较优解, 显示出较强的全局搜索能力。实验结果充分体现了各算法在不同阶段的优化能力, 以及其在特定问题条件下的适应性和有效性。

Thumbnail: 图4 Refer to the following caption and surrounding text. 图4

各类算法适应度变化曲线

由于智能算法本身具有一定的随机性, 为了避免单次仿真实验中可能出现的偶然性影响, 对上述4种算法进行了30次独立的仿真实验。最优解是指算法最终得到的路径方案对应的最小行驶距离值, 衡量了路径优化的质量。平均收敛代数表示算法在找到最优解过程中所经历的平均迭代次数, 反映了算法的收敛速度。具体的统计数据如表 1所示。

表1

求解VRPTW问题的仿真结果对比

由各类算法在仿真实验中的结果可知, 算法均在规定的迭代次数内达到收敛。对于加入破坏算子和修复算子的对比算法, 如遗传算法、狐猴算法和鲸鱼算法, 它们能够有效地提升搜索结果并确保在有限的迭代代数内收敛。但这些方法在增强整体搜索效能上有所欠缺, 特别是在迭代过程后期, 它们常常难以跳出局部最优解。因此, 这些算法虽然能够在短时间内找到较好的解, 但其全局优化能力和避免局部最优的能力仍有待加强。其中, 遗传算法在仿真实验中存在收敛速度较慢的问题, 尤其在面对需要快速求解的任务分配问题时, 这一缺点尤为突出。收敛速度较慢可能会影响算法在时间限制较为严格的应用场景中的表现, 导致求解过程不能在规定时间内完成。

相比之下, 在给定的迭代次数内, 改进沙猫算法找到的最优解比其他算法所找到的最优解更具优势, 表现出了更优的优化效果。LNSCSO算法在保证较快收敛速度的同时, 增强了个体跳出局部最优解的能力, 尤其对于任务分配等离散型优化问题, 展现了良好的优化效果。因此, LNSCSO算法不仅能有效避免陷入局部最优解, 还能在较短的时间内找到较为优越的解, 适合解决带时间窗的任务分配问题。

3 仿真实验与结果分析

3.1 任务分配问题粒子编码设计

LNSCSO算法将每个沙猫个体映射为任务分配方案解, 通过群体智能的协同搜索与位置迭代优化实现问题最优解的逼近。动态环境中任务持续时间、目标消失时间及飞行速度的不确定性为异构平台任务分配带来多重约束。任务执行需满足载荷资源限制、时序逻辑关联以及时间窗匹配等复合约束条件, 同时需协调多机间的竞争协作关系以最大化整体作战效能。为了应对这些挑战, 本文提出了一种基于实数向量编码方式的优化方法, 确保任务分配方案满足以下关键约束条件:

1) 时序约束: 确保侦察任务与打击任务的时序关系得到遵循;

2) 任务并行限制: 任何时刻, 每架飞机仅能专注于执行单一任务;

3) 任务与飞机类型匹配原则: 确保每项任务被分配至相应类型的飞机执行。

在此基础上, 本文采用了基于实数向量的编码方法, 并在此编码方案中建立了沙猫位置与任务分配解的映射关系。沙猫的位置在LNSCSO算法中由一个实数向量表示, 其维度与任务数量相同。每个维度上的数值均代表着特定的任务分配情况, 共同作用于整个任务调度的规划之中。

沙猫个体的定位包含整数与小数2个组成部分, 它们共同界定了任务的分配策略。其中, 整数部分[M]标识了任务将被指派给的具体飞机编号, 而拥有相同整数部分的任务将由同一架飞机来执行。为了保证飞机与任务的匹配性, 本文设置了沙猫位置整数部分的上下界, 以确保每个任务仅被分配给具有相应能力的飞机类型执行。小数部分{M}则反映了任务在飞机任务队列中的排序, 小数部分值越小, 意味着该任务拥有更高的执行优先级, 其被执行的时间点也会相对提前。通过这种方式, 可以确保任务在各飞机上的执行顺序符合时序约束, 特别是侦察任务和打击任务之间的时序依赖。

在任务分配方案的编码过程中, 沙猫位置的整数部分定义了任务与飞机的匹配关系, 而小数部分则为每架飞机的任务分配顺序。以下是一个具体的示例。假设有3架飞机和7个任务(T1~T7), 沙猫的编码表示如表 2所示。

表2

任务序列编码

根据编码规则, 可以通过解码得到每架飞机的任务执行序列。

飞机P1的任务序列为: T2→T5; 飞机P2的任务序列为: T3→T1→T6; 飞机P3的任务序列为: T7→T4。

在解码过程中, 任务序列会根据小数部分的值被排序, 以确保任务的执行顺序符合实际时序需求。这样, LNSCSO算法通过不断更新沙猫个体的位置, 在多次迭代后搜索到一个最优的任务调度方案。通过这种编码与解码方式, LNSCSO算法能够在不确定环境下, 满足异构平台任务分配问题中的时序约束、任务执行约束及匹配约束。

3.2 仿真实验与结果分析

验证模型功能后, 设计实验对算法性能进行验证, 假设我方有8架异构有/无人机, 它们将共同执行25个对地任务, 包括侦察任务和攻击任务。本实验采用基于加权评价指标的方法来计算任务分配的适应度值, 具体通过任务收益、威胁代价和配送效率3项指标的加权组合来衡量。其中, 任务收益w1、威胁代价w2和配送距离w3的权重分别为0.3, 0.4和0.3。此外, 为确保方案的可行性, 引入了容量约束α和时间窗约束β的惩罚系数, 分别为10和100, 以应对任务超出资源限制或时间窗口违规的情况。利用本节所提出的改进沙猫算法对任务分配模型进行求解, 种群规模设置为50, 最大迭代次数为300。最终的任务分配方案如表 3所示，分配结果二维示意图如图 5所示。

表3

有/无人机对地任务分配方案

Thumbnail: 图5 Refer to the following caption and surrounding text. 图5

对地任务分配结果二维示意图

实验结果表明, 不同飞机执行的任务序列呈现出明显的差异, 这反映了沙猫算法在寻找最优解过程中考虑了任务之间的不同优先级、距离、资源消耗等因素。该方案能够有效平衡任务之间的关系, 最大化任务的执行效益, 最优适应度值为421.666 3。算法的适应度变化曲线如图 6所示。

Thumbnail: 图6 Refer to the following caption and surrounding text. 图6

改进沙猫算法适应度变化曲线

带时间窗的任务甘特图作为一种可视化工具, 能有效地展示任务调度的过程和结果。任务甘特图时间轴在横轴上表示, 任务的执行按照时间顺序排列。任务条形表示每个任务的开始和结束时间, 条形的长度表示任务的执行持续时间。本实验的任务甘特图如图 7所示。通过图 7能够直观地观察任务的排程情况以及不同时间段内资源的使用情况。通过观察任务条形的长度和分布, 可以帮助分析任务的分布是否均衡, 如飞机1的任务分布比较分散, 而飞机8的任务分布比较紧密。

Thumbnail: 图7 Refer to the following caption and surrounding text. 图7

对地任务分配结果任务甘特图

实验结果表明, 改进沙猫算法能够在综合考虑任务收益、威胁代价、配送效率以及约束条件的基础上, 平衡各项因素, 找出最优的任务分配方案。随着迭代次数的增加, 适应度值最终收敛至较优解。在算法的迭代初期, 最优适应度呈现出快速下降趋势, 这表明算法在搜索过程中迅速排除了较差解并向较优解逼近; 而在算法的中后期, 收敛速度逐渐减缓, 算法进入精细搜索阶段, 围绕当前较优个体进行局部搜索, 从而逐步逼近全局最优解。最终, 经过约110代的迭代, 算法达到了收敛, 此时适应度值稳定, 表明最优解已经被有效地确定。

4 结论

本文对SCSO算法的改进, 引入了非线性收敛因子和外部存储更新机制, 并融合LNS算法, 通过整合破坏算子和修复机制, 创新性地提出了LNSCSO算法。随后, 将LNSCSO算法应用于解决复杂的带有时间窗的车辆路径问题(VRPTW), 并通过与多种智能优化算法的对比, 展示了其在处理此类组合优化问题时的显著效果和优势。针对异构多无人机协同任务预分配的难题, 设计了一种基于实数向量的编码策略。仿真实验的结果进一步验证了LNSCSO算法在解决任务预分配问题上的有效性和适用性。

References

  1. Liang Zibin, Li Qing, Fu Guodong. Multi-UAV collaborative search and attack mission decision-making in unknown environments[J]. Sensors, 2023, 23(17): 7398–7418 [Article] [Google Scholar]
  2. Wang Xinyao, Cao Yunfeng, Sun Houjun, et al. Modeling for cooperative combat system architecture of manned/unmanned aerial vehicle based on DoDAF[J]. Systems Engineering and Electronics, 2020, 42(10): 2265–2274 (in Chinese) [Google Scholar]
  3. Cramer Martijn, Kellens Karel, Demeester Eric. Probabilistic decision model for adaptive task planning in human-robot collaborative assembly based on designer and operator intents[J]. IEEE Robotics and Automation Letters, 2021, 6(4): 7325–7332 [Article] [Google Scholar]
  4. Ye Wen. Mission planning for unmanned aerial vehicles[M]. Beijing: National Defense Industry Press, 2015 (in Chinese) [Google Scholar]
  5. Keller J. DARPA adds two companies to OFFSET swarm reconnaissance drone research project[J]. Military & Aerospace Electronics, 2018, 29(4): 30–31 [Google Scholar]
  6. Khamis A, Hussein A, Ehnogy A. Multi-robot task allocation: a review of the state-of-the-art[J]. Studies in Computational Intelligence, 2015, 604: 31–51 [Google Scholar]
  7. Ni Yao, Zhou Deyun, Ma Yunhong, et al. The air-to-ground tasks assignment for multi-UAV based mixed integer linear programming[J]. Fire Control & Command Control, 2008, 33(11): 62–65 (in Chinese) [Google Scholar]
  8. Xue Yang, Wang Jiesheng. Application of improved ant colony optimization algorithm on traveling salesman problem[C]//Chinese Control and Decision Conference, Yinchuan, China, 2016: 2156–2160. [Google Scholar]
  9. Reinelt Gerhard. The traveling salesman: computational solutions for TSP applications[M]. Berlin: Springer-Verlag, 1994 [Google Scholar]
  10. Fang Ye, Jie Chen, Yuan Tian, et al. Cooperative multiple task assignment of heterogeneous UAVs using a modified genetic algorithm with multi-type-gene chromosome encoding strategy[J]. Journal of Intelligent & Robotic Systems, 2020, 100(2): 1–13 [Google Scholar]
  11. Bai Xiaoshan, Li Chang, Zhang Bo, et al. Efficient performance impact algorithms for multirobot task assignment with deadlines[J]. IEEE Trans on Industrial Electronics, 2024, 71: 14373–14382 [Article] [Google Scholar]
  12. Bi Wenhao, Zhang Mengqi, Gao Fei, et al. Review on UAV swarm task allocation technology[J]. Systems Engineering and Electronics, 2024, 46(3): 922–934 (in Chinese) [Google Scholar]
  13. Hu Jiawei, Jia Zequn, Sun Yantao, et al. Survey of analysis and solutions for multi-UAV cooperative mission planning problem under multi-constraint conditions[J]. Computer Science, 2023, 50(7): 176–193 (in Chinese) [Google Scholar]
  14. Mao Yingchi, Mu Chao, Bao Wei, et al. Multi-type task assignment and scheduling oriented to spatial crowdsourcing[J]. Journal of Computer Applications, 2018, 38(1): 6–12 (in Chinese) [Google Scholar]
  15. Bai Xiaoshan, Yan Weisheng, Ge Shuzhi Sam. Efficient task assignment for multiple vehicles with partially unreachable target locations[J]. IEEE Internet of Things Journal, 2021, 8(5): 3730–3742 [Article] [Google Scholar]
  16. Seyyedabbasi Amir, Kiani Farzad. Sand cat swarm optimization: a nature-inspired algorithm to solve global optimization problems[J]. Engineering with Computers, 2022, 39(4): 2627–2651 [Google Scholar]
  17. Hu Kun, Mo Yuanbin. Hybrid sand cat algorithm for solving dynamic optimization problems in chemical engineering[J]. Chemical Engineering, 2024, 52(5): 85–90 (in Chinese) [Google Scholar]
  18. Oluwatayomi Rereloluwa Adegboye, Afi Kekeli Feda, Oluwaseun Racheal Ojekemiet al.. DGS-SCSO: enhancing sand cat swarm optimization with dynamic pinhole imaging and golden sine algorithm for improved numerical optimization performance[J]. Scientific Reports, 2024, 14(1): 1491 [Article] [Google Scholar]
  19. Zhan Yue, Jiang Zhaoqin, Liu Zhenyuan. Optimization model and revised adaptive large neighbourhood search algorithm for multi-structured on-site service scheduling problem[J]. Control and Decision, 2024, 39(3): 947–955 (in Chinese) [Google Scholar]
  20. Bai Xiaoshan, She Anqi, Zheng Xinquan, et al. Task assignment for multiple USVs and AUVs based on improved minimum marginal cost algorithm[J]. Control and Decision, 2025, 40(1): 119–127 (in Chinese) [Google Scholar]

All Tables

表1

求解VRPTW问题的仿真结果对比

In the text
表2

任务序列编码

In the text
表3

有/无人机对地任务分配方案

In the text

All Figures

Thumbnail: 图1 Refer to the following caption and surrounding text. 图1

多机协同任务分配模型框图
In the text
Thumbnail: 图2 Refer to the following caption and surrounding text. 图2

迭代中的位置更新
In the text
Thumbnail: 图3 Refer to the following caption and surrounding text. 图3

LNSCSO算法流程图
In the text
Thumbnail: 图4 Refer to the following caption and surrounding text. 图4

各类算法适应度变化曲线
In the text
Thumbnail: 图5 Refer to the following caption and surrounding text. 图5

对地任务分配结果二维示意图
In the text
Thumbnail: 图6 Refer to the following caption and surrounding text. 图6

改进沙猫算法适应度变化曲线
In the text
Thumbnail: 图7 Refer to the following caption and surrounding text. 图7

对地任务分配结果任务甘特图
In the text

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.