【任务分配】共识的捆绑算法CBBA多无人机多任务调度【含Matlab源码 3609期】

✅博主���介：热爱科研的Matlab仿真开发者，修心和技术同步精进，Matlab项目合作可私信。

个人主页：海神之光

代码获取方式：

海神之光Matlab王者学习之路—代码获取方式

⛳️座右铭：行百里者，半于九十。

更多Matlab仿真内容点击

Matlab图像处理（进阶版）

路径规划（Matlab）

神经网络预测与分类（Matlab）

优化求解（Matlab）

语音处理（Matlab）

信号处理（Matlab）

车间调度（Matlab）

⛄一、 带时间窗的多UAV航迹规划问题的两阶段启发式算法

本文采用一种两阶段启发式算法用于问题求解, 算法的第一阶段利用“最迟完成服务节点优先” (Latest-Service-Finished-First, 简称LSFF) 算法求得问题的初始解, 第二阶段利用模拟退火算法 (SA算法) 改善初始解, 获得“满意解”。

1 LSFF算法

LSFF算法是一种逆向计算的迭代算法, 其基本思想是:从返回机场开始, 逆向迭代计算从待服务节点飞往后继节点的最迟动身 (完成物资投放) 时间, 并选择最晚可服务节点优先服务, 重复上述过程直至全部节点均被服务为止;这里只接受可行解。

假设当前后续节点为succ, 其最迟抵达时间为maxatsucc, 待服务节点i的最迟动身时间为maxdepti, 则LSFF算法的流程可描述如下:

步骤1:创建空航行线路为当前航迹, 令succ=0, maxatsucc=l0;

步骤2:计算所有的maxdepti=max{maxatsucc-ti, succ, lsucc+stsucc}, 并进行约束条件校验, 从可行节点中选择满足maxdeptk=max{maxdepti}的节点k作为优先服务节点;

步骤3:将节点k插入至航段间, 令succ=k, maxatsucc=maxdeptk-stk, 更新节点k的服务标志;

步骤4:重复步骤2、步骤3, 直至无节点可服务为止。若仍有节点未服务, 创建新路径, 令succ=0, maxatsucc=l0, 转步骤2;否则转步骤5;

步骤5输出初始解sinit。

从上述描述显见, LSFF算法是一种“头插式”算法, 新节点的插入位置必定是航迹的第一条航段之间。由此可将时间窗约束的处理方法修正如下:计算UAV从机场出发抵达新节点i的最早时间minati=e0+t0i, 若maxdepti同时满足式 (14) 、式 (15) , 则时间窗约束满足, 否则不满足。

2 SA算法

利用LSFF算法产生初始解后, 进一步利用SA算法改进初始解, 下面分别对SA算法的邻域结构和算法流程进行描述。

(1) 邻域结构

本文采用两种邻域变换:remove操作和insert操作来构造邻域, 如图1所示。

(2) 算法流程

步骤1:设置起始温度btemp和etemp, 设置温度迭代步长tstep, 令当前温度temp=btemp, 令当前解x=sinit, 当前最优解s=sinit, 初始化内循环次数maxcnt;

步骤2:如果temp>etemp, 重复执行步骤3~步骤5;

步骤3:令内循环次数cnt=1, 重复步骤4, 直至cnt=maxcnt为止;

步骤4:随机选择交换节点node, 利用remove和insert操作, 将其插入任一条可行路径, 产生邻域解x’;令f (·) 表示解·对应的目标函数值, rand_max为随机数的上限, 比较f (x’) 和f (x) , 如果f (x’)