李绍斌， 姜大立， 杨西龙， 刘书俊

(1. 陆军勤务学院军事物流系， 重庆 401311； 2. 陆军勤务学院油料系， 重庆 401311)

当前，战时前线部队的物资保障主要采取车辆配送方式，由于车辆的机动能力不足且极易受战场交通环境的限制，难以满足紧急情况下物资保障任务的要求；而且在情况紧急下出动直升机完成物资器材的配送任务时，由于目标暴露大，对直升机与机组人员的安全威胁也大。无人机配送是解决战场物资“最后一公里”保障的有效方式，其既能完成战时需求物资器材的应急配送，同时又可最大限度地保证后勤保障人员的生命安全，因此未来战场物资的保障将越来越趋向于无人化配送。其中，多无人机配送任务分配决策是提升无人机配送能力的核心基础之一，其目的是将战场物资保障任务在时间和空间上最优地分配到具体的各架无人机，以充分利用现有资源快速高效地完成物资配送任务，实现最佳的物资配送效能，最大限度地提高和维持部队的战斗力。

目前，国内外学者对无人机任务分配问题的研究已取得了一定的研究成果。如：符小卫等[1]研究了通信约束对侦察无人机多机协同搜索任务分配的影响，提出了一种通信约束条件下的多无人机协同侦察目标分配方法；李原等[2]对存在侦察时间窗口与侦察器材限制的多基地、多无人机协同侦察任务进行规划，对无人机基地、侦察器材类型以及侦察目标序列同时进行优化；周小程等[3]重点研究了分布式控制结构的无人机任务分配，针对分布式控制结构的特点，提出了基于拍卖机制原理的动态任务分配算法；SHETTY等[4]对单基地不同型号打击无人机的任务分配进行求解，同时考虑目标点的优先级，应用禁忌搜索算法求解了模型；杨尚君等[5]以侦察、攻击、毁伤评估3类无人机的任务协同为目标，建立了以最大航程与最长任务时间为目标的任务分配优化模型，并采用改进鱼群算法求解模型；马焱等[6]对打击无人机的目标分配进行研究，建立了以目标价值收益、飞行距离、耗弹量成本以及目标覆盖度为目标的任务分配模型，并采用自适应烟花算法求解模型。配送无人机作为当前新兴的技术装备，现有文献对其配送任务分配的研究报道较少，只有少部分文献对民用物流无人机的配送任务规划进行了研究，如：SONG等[7]对无人机实施岛屿货物配送进行了研究，以配送任务总成本最小为目标构建了混合整数优化模型；HA等[8]对单基地的无人机配送任务分配进行了研究，将无人机配送过程转换为传统的旅行商问题(Traveling Salesman Problem,TSP)，以配送成本最小化为目标构建了单基地的无人机配送任务分配模型，并以贪婪随机自适应搜索算法求解了模型；RABTA等[9]对无人机在应急救援“最后一公里”配送中的应用进行了研究，在无人机有效载荷和航程的约束下，以无人机总行驶距离最小化为目标，构建了混合整数线性规划模型并进行了求解。

综上所述，现有研究对战场物资无人机配送任务分配问题鲜有报道，配送无人机在战场执行物资配送任务的独特性，决定了其与侦察无人机、通信无人机、打击无人机以及民用物流无人机的任务分配问题存在差异，配送无人机具有航时限制、载荷约束，配送过程时效性强、面临需求点多等实际情况。因此，针对复杂战场环境下多基地、多无人机保障多需求点的任务分配开展研究具有重要的现实意义。为了更加真实地描述战场物资无人机配送的过程，以多约束条件下的多车场车辆路径问题(Multi-De-pots Vehicle Routing Problem with Multiple Constraints，MDVRPMC)为基础，建立符合实际的战场物资无人机配送任务分配模型。由于传统算法的计算量大，求解效率不高，笔者以遗传算法为基础，引入克拉克-怀特节约里程法(Clarke and Wright saving me-thod，C-W saving method，简称节约里程法)和最近邻算法(the Nearest Neighbor Heuristic，NNH)，有效提升了模型求解的效率，解决了实际战场环境下的多无人机配送任务分配问题，实现了多基地、多无人机的配送协同。

1 问题描述与分析假设

1.1 问题描述

考虑战场前沿的应急补给任务多、强度大，通常同时面临多个作战力量的物资需求。为了缓解单个无人机保障基地的压力，以更高效地完成物资配送任务，通常在战场前沿的野战仓库配属多个无人机保障基地，以集群保障模式及时响应作战力量的物资需求。在战场物资无人机配送任务分配问题中，无人机基地的数量与位置是确定的，每个无人机基地都储存了足量的保障物资，基地内配备具有一定载荷的无人机，来负责为各作战单元补给物资，作战单元的物资需求以及位置坐标可通过指挥信息系统获得。为了更加直观地描述战场物资无人机配送的过程，将多基地、多无人机的配送过程进行简化，如图1所示。

在该战场物资配送问题中，共有B1、B2两个无人机基地，其地理坐标已知，配送无人机的最大载荷为14个标准单位，各作战单元的物资需求量以及地理坐标也是确定的，其中5号作战单元的地理坐标为(10,15)，其物资需求量为8个标准单位。在该示例中，需求点1-6的保障任务由基地B1完成，需求点7-12的保障任务由基地B2完成，2基地都分别形成了2个闭环路线，其中每个闭环路线代表一架配送无人机保障任务的集合，闭环路线中的箭头方向代表无人机在单次配送任务中的保障顺序。由示例可以看出:2个无人机基地共派出了4架配送无人机，按顺序完成了12个需求点的物资保障任务。

无人机的多任务协同分配模型有2个常用的目标函数：各无人机总的飞行航程最小和实施所有配送任务的时间最短[10]。前者能有效降低基地内执行配送的无人机数量，使战场物资的配送能同时兼顾经济性和军事性，参与保障的配送无人机数目越少，则相应所需的人力、物力也就越少，保障成本相应也越低，同时，可以最大限度地为后续保障任务预留无人机，增加后续可利用的配送无人机数。但该目标函数将使部分无人机执行的配送任务要比其他无人机多，从而使距任务点较远的无人机分配不到保障任务，导致完成所有配送任务的时间增加。后者追求完成所有配送任务的总时间最短，以最短的时间完成各战术单元的紧急保障任务，确保战场物资配送的效率，但该目标函数将造成除最后完成配送任务的无人机之外，其余无人机的航程均变长，而且使参与配送的无人机数量大幅增多。由此可见：2个目标函数相互之间是互斥的，因此在实际战场物资配送过程中，决策者需视具体的情况权衡2个目标的权重，在满足供需平衡以及无人机性能约束的条件下，优化无人机配送任务的分配方案，使物资资源能按需、保质、保量地完成配送，同时使完成配送任务的时间最短，且出动配送无人机的数量也最少。

1.2 模型假设

多基地、多无人机战场物资配送任务的分配是一个复杂的NP-Hard(Non-deterministic Polynomial-Hard)问题，涉及的目标多、影响因素复杂，为了更加方便地进行定量化研究，同时最大限度地确保与战场物资无人机配送的实际相符合，对模型构建作如下合理的假设：

1) 配送无人机基地作为战术补给的前沿阵地，应具备满足该作战方向物资保障的能力，其储备有足够的补给物资，不存在配送时物资缺额的情况。

2) 战术型配送无人机相对轻便，运送的物资量小，在作战后勤保障中执行应急保障任务。为满足所有作战分队的物资紧急需求，通常保证基地内配备的无人机数量足够。因此，假设基地内拥有足够的无人机可随时应对物资的紧急需求，同时基于无人机单次运输的物资量相对较小，对基地内的物流设备能力不会产生太大压力，在模型中暂不考虑物资备货、装卸的时间。

3) 战时无人机的配送能够通过后勤保障指挥信息系统实时地感知战场保障态势，结合实时的物资需求信息，在无人机实施配送任务前已将不同的物资资源进行组套化包装，因此模型将不考虑物资的种类区分，以基数化、标准化的物资量进行计算。

4) 配送无人机只有在其载荷超过需求点的需求时才实施配送保障行动，当需求点的物资需求量超过无人机的载荷时，可将该需求点分解为多个具有相同参数的子需求点，因此，假设任一战场需求点只能由一架无人机负责配送保障，且各配送无人机完成配送任务后需回到原出发基地。

2 模型构建

MDVRPMC是在多约束条件下将运输物资由多辆车从多个车场向多个需求点运输的问题[11]。本文借鉴MDVRPMC问题对多基地、多无人机配送任务分配问题进行建模，具体的模型参数设置如下：

设{B1,B2,…,BM}为M个无人机基地的集合，Bm(m=1,2,…,M)之间既可以是上级加强的配送力量，也可以是友邻保障力量；{A1,A2,…,AN}为N个任务需求点(任务节点)的集合，其中Ai、Aj表示2个不同编号的任务节点；有k架配送无人机；dij为任务节点Ai与Aj间的距离；Ci为任务节点Ai的物资需求量；Q为配送无人机的最大载荷；v为无人机的飞行速度；D为配送无人机的最大航程数。

1) 决策变量为

2) 约束条件为

(1)

(2)

(3)

(4)

(5)

(6)

其中：式(1)表示任一物资需求点只由一架无人机进行保障；式(2)表示任一无人机的保障任务量不能超过其最大载荷；式(3)表示任一无人机保障任务行程不能超过其最大航程；式(4)-(6)表示每架配送无人机均是从基地出发按顺序完成保障任务后，最终返回基地，确保了每架无人机配送任务的连续性。

记满足上述配送约束的方案为有效分配方案φ={φ1,φ2,…,φM}，其中φm(m=1,2,…,M)为基地Bm的配送任务方案;c(s)为有效分配方案的单一保障路线中各任务节点的先后顺序；nk为保障无人机k路线上的任务节点数量；gm为基地Bm中无人机路线的数量。则

配送无人机的多任务协同分配是在符合战场实际的情况下，实现多无人机的整体保障效能最大化，通常采用各无人机飞行的总航程最小和完成所有配送任务的时间最短来评价无人机的协同保障效能，因此，笔者将其作为评价配送无人机协同保障任务分配方案优劣的重要指标。

1) 多无人机配送的总航程数最小。多无人机配送的总航程数为各基地内各架无人机航程数之和，即

(7)

式中：c(0)为无人起飞的基地。

2) 多无人机完成所有配送任务的时间最短。多基地、多无人机完成所有配送任务的时间以各基地中完成配送任务时间最长的基地进行计算，其中单个基地完成配送任务的时间以基地内配送时间最长的无人机进行计算，因此以各基地中最长的配送时间作为多基地多无人机完成所有配送任务时间最短指标指标值，即

(8)

各基地中最长的配送时间决定了完成所有配送任务的时间，假设无人机的飞行速率为恒定的，则无人机完成配送任务的时间与其飞行距离成正比，因此式(8)中的无人机配送时间可采用飞行里程来表征。

根据式(7)、(8)，可得目标函数为

(9)

式中：w1,w2∈[0,1]，为2个子目标的权重系数，且w1+w2=1。

以式(9)为目标函数对每次生成的有效分配方案φm进行评估，其中目标函数值最小的为最优配送无人机协同保障任务分配方案。

3 模型求解流程

遗传算法(Genetic Algorithm，GA)是在模拟自然界生物的遗传与进化过程中,形成的自适应全局优化搜索算法，能够自动获取和积累有关搜索空间的知识，并自适应地控制搜索过程以求得最优解。其搜索寻优的自组织、自适应和自学习性等特点，使其成为求解NP-Hard问题的有效方法[12]。应用GA求解多基地、多无人机的战场物资配送任务分配问题，首先，需将其分解细化为3部分：1)将保障任务分配给各无人机基地，主要解决各任务节点分群问题；2)对归属同一保障基地的各任务节点进行分组，主要解决基地内各无人机的任务分工问题；3)确定同一组中各任务节点的保障顺序，主要解决无人机保障任务的顺序问题，具体如图2所示。

由此可知：多基地、多无人机的战场物资配送任务分配问题是由任务分组、任务分工以及任务顺序3个子问题组成，其中任何一个子问题都较为复杂，以至于求解难度较大。由于传统遗传算法的求解效率不高，笔者将遗传算法与节约里程法、最近邻算法相结合，形成混合遗传算法(Hybrid Genetic Algorithm，HGA)来提升模型求解的效率，求解流程如图3所示。

由图3可知，HGA算法与GA算法的主要区别在于初始解与初始种群的生成:在GA算法中，每个初始解均随机产生，生成的初始种群也是随机的；在HGA算法中，初始解的生成过程引入了节约里程法与最近邻算法，针对性地优化提升了初始解的质量，生成的初始种群更接近最优解。遗传算法求解的实质是随机化搜索寻优的过程，初始种群相对较优，意味着算法寻优的空间与范围大大缩小，寻优的方向性得到增强。因此，在相同条件下，HGA算法得到最优解的概率将大大增加，同时收敛的速度更快。

4 模型求解步骤

4.1 产生初始解与初始种群

为使模型解能直观地反映各基地、各无人机的保障任务顺序，首先以无人机保障任务的顺序对染色体进行编码，每条保障路线代表1架无人机的任务安排。以单架无人机基地为例，某时刻对编号1-6的任务节点进行物资配送，优化的无人机保障方案为(0 2 5 3 0 6 1 4 0)，由此可知：需要2架无人机实施物资配送(或者单架无人机实施2阶段的物资配送)，其中一架无人机从基地(以0表示)出发，按顺序完成任务节点2、5、3的任务后返回基地；另一架无人机的保障路线也是从基地出发，按顺序完成6、1、4的保障任务后也返回基地。同理，当有m个无人机基地参与保障时，每条染色体中将包含着m个子片段序列，多基地的染色体实数编码如图4所示。

图4 染色体编码

由图3可知，HGA初始化阶段分为3个步骤：

1) 完成所有任务节点的分组工作，要求模型目标函数中完成配送任务的时间最短，因此基于任务节点与基地之间的距离远近将各任务节点分配至距离最近的无人机基地，即

(1) 当d(Ai,Bm)=min(d(Ai,B1),d(Ai,B2),…,d(Ai,BM)), 其中，m=1,2,…,M,i=1,2,…,N时，Ai分配给Bm基地；

(2) 当d(Ai,B1)=d(Ai,B2)=…=d(Ai,BM)时，Ai随机分配给任一基地 。

其中：

(10)

为任务节点Ai至基地Bm的距离。

2) 解决同属于一个基地的保障任务分工问题，使完成配送任务的总航程数最小。采用节约里程法将各个基地负责的任务节点分配给基地内各架无人机。节约里程法的经典节约量计算公式为[13]

S(Ai,Aj)=d(Ai,Bm)+d(Aj,Bm)-d(Ai,Aj)，

(11)

式中：S(Ai,Aj)为节约的航程数。

计算各基地中所有任务节点两两之间节约的航程数，在满足无人机载荷与航程约束的条件下，将节约航程数较大的2个节点安排在同一架无人机的单次保障路线中。

3) 解决单架无人机保障路线中各任务节点的保障顺序，即明确具体无人机的保障任务顺序，这实质上是一个典型的TSP问题。采用最近邻算法(NNH)确定无人机保障任务的顺序，最近邻算法(NNH)的原理是在同属于一个保障基地、一条保障路线的任务节点中，随机选择一个任务节点作为初始任务节点，在剩下的任务节点中选择与初始任务节点距离最近的任务节点作为第2个节点；依次类推，直至该路线中最后一个任务节点的任务完成，无人机返回基地。以图1为例说明HGA初始可行解的产生过程，如图5所示，生成的一个初始可行解为(5 4 1 3 6 2 8 9 12 10 7 11)。按照初始可行解的生成方法，随机生成一个规模为R的初始种群，并以种群中的初始可行解作为迭代的初始点。

4.2 选择操作

以目标函数为适应度函数，计算种群中各染色体的适应度值，根据适应度值的大小选择染色体。笔者采用轮盘赌的方法选择染色体，通常适应度值越大的染色体，其被选中的概率越大。设fg为第g个染色体的适应度值，则第g个染色体被选择的概率

(12)

4.3 交叉操作

交叉算子是遗传算法中最重要的操作之一。对染色体上的基因进行重组生成新的个体，通过交叉操作可大幅提升遗传算法的寻优能力。在混合遗传算法中，每次按一定的概率pc，采用传统顺序交叉(order crossover)方式产生2个子代，具体步骤如图6所示。首先，在父代染色体1中随机选择一段基因(6 2 8 9)，将该段基因复制于子代染色体1的相同位置；然后，将父代染色体2中相同的基因剔除，剩下的基因片段从左至右重新排列；最后，将重新排列的基因组按从左至右的顺序，依次填入子代染色体1中的空缺位置，形成完整的子代染色体1：(1 4 7 10 6 2 8 9 5 12 3 11)。同理，选择父代染色体2中相应位置的一段基因，复制至子代染色体2的相同位置，剔除父代染色体1中相同的基因，采用相同的方法产生子代染色体2。

4.4 变异操作

变异算子是对种群中的个体基因值进行变动。变异算子具有局部随机搜索能力，可加速向最优解收敛；同时通过基因突变，生成的新的子代染色体，维持了种群的多样性，进而防止出现早熟收敛现象，因此设置合理的变异概率pm，可提高算法寻优能力，同时也可避免陷入早熟收敛。由于单一变异算子存在一定的随机性、盲目性，变异的效果得不到保证，为了在算法运行过程中提升变异的质量，笔者同时采取交换变异策略与倒置变异策略。

1) 交换变异策略。以一定的变异概率在种群中选择一条父代染色体，随机选择3个基因；列出3个基因的所有排列组合，每一个排列组合都作为一个子代。设w1=w2=0.5，则交换变异策略操作过程如图7所示。

2)倒置变异策略。以设定的变异概率在种群中选择一条父代染色体，在父代染色体中随机选择一串基因片段，对基因片段的顺序进行倒置生成新的子代染色体，以确保种群的多样性。倒置变异策略操作如图8所示。

4.5 结束条件

当达到设定的迭代次数时，算法终止。并对染色体进行解码，生成近似最优解。

5 算例分析

为了验证模型与算法的合理性和有效性，通过仿真算例对GA与HGA两种算法的计算效果进行对比。随机设置2种情况：30个、50个任务节点，2个无人机基地。无人机基地与各任务节点的位置分布如图9所示，其中各任务节点的物资需求量已知，配送无人机的运输性能确定，无人机的性能约束以及供需平衡要求明确。

设置种群大小为100，当任务节点数为30时，设置迭代次数为200；当任务节点数为50时，设置迭代次数为500；交叉概率pc=0.8，变异概率pm=0.05。利用GA与HGA算法分别求解30个任务节点的任务分配，其收敛曲线对比如图10所示，相对应的任务分配结果如图11所示。

由图10可知：GA算法优化的适应度值始于297.65，在进化至110代时收敛于183.22；HGA方法优化的适应度值始于196.81，在进化至100代时收敛于172.98。由图11可知，2种算法求解得到的任务分配结果不同，如：在GA优化算法中任务节点2、18由同一架无人机保障，而在HGA算法中任务节点2、20由同一架无人机配送，任务节点18则与任务节点21由同一架无人机配送。图11中的闭环表示1架无人机完成的配送任务，其中GA算法求解的任务分配结果显示2个无人机基地共需出动无人机13架次，HGA算法求解的任务分配结果中2个无人机基地共需出动无人机12架次。

采用GA与HGA算法分别求解50个任务节点的任务分配，其收敛曲线对比如图12所示，相对应的任务分配结果如图13所示。由图12可知：GA算法优化的适应度值始于525.68，在进化至300代时收敛于330.76；HGA算法优化的适应度值始于345.26，在进化至270代时收敛于313.02。由图13可知：2种算法求解得到的配送任务分配方案不同，对应的2个基地需出动无人机的数量均为21架次。

由图10、12可以看出：HGA算法收敛曲线的始点均远远低于GA算法的收敛曲线，说明HGA算法可产生质量更优的初始解与初始种群。这是由于HGA算法中采用了节约里程法与最近邻算法产生初始解，同时HGA算法的收敛曲线整体都远低于GA算法，HGA算法的优化效果优于传统的GA算法。因此，节约里程法与最近邻算法对初始解、初始种群的优化在配送任务分配决策中起着至关重要的作用。为了更加直观地反映HGA算法的优势，引入优化率α与提升率β指标，计算公式分别为

(13)

(14)

通过求解优化率指标α与提升率指标β，得出2种方法的具体性能对比，如表1所示。

表1 HGA与GA算法性能的对比

由表1可以看出：HGA算法的优化率分别为12.11%、9.34%，显著低于GA算法的38.44%、37.08%。这主要是由于HGA算法的初始种群、初始解的质量明显优于传统GA算法随机生成的初始解，使得HGA算法优化的起点更高，更接近于全局最优解，可优化的幅度空间相对较小，因此，HGA算法优化的幅度低于传统GA算法。提升率指标反映了保障30个任务节点时HGA算法提升解质量的幅度达到5.59%，保障50个任务节点时HGA算法提升解质量的幅度达到5.36%，在同等条件下HGA算法的寻优能力更强。同时，从达到稳定的进化代数也可发现HGA算法的收敛速度更快，计算效率更高。综上所述，混合遗传算法能更好地求解多基地、多无人机战场物资协同配送任务分配优化问题。

6 结论

研究探索战场物资无人机配送任务分配的优化方法，提高无人机协同配送的效率效益，是实现无人机在未来战场物资配送中常态化运行的重要基础。笔者重点研究了多基地、多无人机的战场物资协同配送任务分配优化问题，以多约束条件下的多车场车辆路径问题为基础，建立了多基地、多无人机的协同配送优化模型，构造了融合节约里程法、最近邻算法的混合遗传算法求解模型，并与传统遗传算法的收敛性、优化质量进行了对比分析。结果表明：混合遗传算法在相同条件下的求解质量优于传统遗传算法，在一定迭代代数下可得到更为满意的解，这对于解决战场物资无人机配送任务分配问题具有重要的参考意义。但该模型中未考虑实际战场物资保障过程中多种运输工具协同配送的问题，下一步将重点围绕无人机与传统车辆联合配送任务分配优化问题展开研究。