Two-Layer Planning Approach for Coordinated Scheduling of Heterogeneous UAVs and USVs in Emission Control Area Inspection Operations
-
摘要:
为提高无人机巡检船舶尾气排放效率，考虑了异质无人机与无人艇协同调度路径规划问题，采用双层规划模型解决无人机与无人艇配置和路径优化问题。上层模型利用改进的自适应模拟退火算法求出无人机与无人艇配置方案；下层模型以最短无人机飞行总时间为目标，结合无人机、无人艇和船舶实时动态性特征，利用改进的遗传算法求出无人机检测序列与飞行路径和无人艇航行路径。算例实验结果表明：异质无人机与无人艇协同调度相较于固定配置下同质无人机与无人艇在飞行总时间上平均减少24.98%，无人机成本平均减少23.57%，无人艇成本平均减少42.20%；无人机速度每提升15 km/h，飞行总时间平均减少23.02%，无人机成本平均增加26.45%；无人艇速度每提升5 km/h，无人艇成本平均增加37%。
Abstract:To enhance the efficiency of Unmanned Aerial Vehicles (UAVs) in inspecting ship emissions, this study addresses the coordinated scheduling and routing planning problem for heterogeneous UAVs and Unmanned Surface vessels (USVs), employing a two-layer planning model to tackle the configuration and path optimization issues. The upper-layer model implements an improved adaptive simulated annealing algorithm to determine the allocation of UAVs and USVs. Meanwhile, the lower-layer model seeks to minimize the total flight time of UAVs by integrating the real-time dynamic characteristics of UAVs, USVs, and ships, utilizing an improved genetic algorithm to formulate the UAV detection sequence, flight path, and USV navigation path. Experimental results indicate that the coordinated scheduling of heterogeneous UAVs and USVs significantly reduces average flight time by 24.98%, UAV costs by 23.57%, and USV costs by 42.20% when compared to fixed configurations with homogeneous UAVs and USVs. Additionally, increasing UAV speed by 15 km/h results in an average reduction of 23.02% in flight time, while the UAV cost rises by 26.45%. Furthermore, for every 5 km/h increase in USV speed, the average USV cost escalates by 37%.
-
为响应国家碳达峰和碳中和的目标，降低船舶航行过程中排放的CO2等气体和颗粒物对环境及人类健康产生的负面影响，各国政府制定排放控制区(Emission Control Area, ECA)政策以限制船舶尾气排放[1]。利用无人机进行船舶排放检测可同时兼顾作业效率与安全性。无人机配置尾气嗅探技术的遥感检测系统，通过感应气体成分的传感器来检测船舶排放的有害物质以及追踪船舶一段距离实现对船舶污染物排放的动态监测[2]。利用无人艇作为无人机充电站可以克服电量限制并增加检测覆盖面积，提高船舶检测效率，为环境监管提供更准确的数据支持。
针对多无人机协同调度优化问题，KHOSIAWAN等[3]对室内环境下无人机调度问题展开研究，将提出的启发式算法与粒子群算法相结合，在短时间内获得了最优的调度方案；YANG等[4]、LIU[5]等提出了无人机群调度方法，以降低人工成本、提高操作能力；ZENG等[6]通过建立任务同步无人机资源调度模型，有效提升了无人机群执行任务的效率；陆玲玲等[7]在应急物流的背景下提出了一种用于车辆和无人机的协同配送路径优化模型，实现了无人机飞行总时间最短和总配送成本最少的目标；QADIR等[8]通过改进算法实现无人机在不同情景下无碰撞路径优化。对于求解无人机飞行路径的算法有很多，包括遗传算法[9]、A*算法[10]、粒子群算法[11]等。
针对利用双层规划模型求解路径规划问题，WANG等[12]提出一种结合全局和局部路径规划的双层规划混合算法，设计了改进粒子群优化和人工势场算法，有效提升了环境监测无人设备在复杂海域导航条件下的动态路径规划问题。李杨飞等[13]通过解析BIM的IC标准文件提取空间信息构建动态路径矩阵，提出优化Diiksra算法构建基于Unilv3D场景的最优三维路径，实现基于消防设备的动态灭火引导路径规划。杨秀娟等[14]基于YOLOv5的无人机航拍改进目标检测算法Dy-YOLO对于无人机航拍检测任务具有较好的性能。
现有研究未广泛考虑动态特性、移动充电支持和异质无人机的综合影响。本文针对ECA海域的异质无人机与无人艇协同调度与路径优化问题，提出了双层规划模型并设计了自适应模拟退火算法和改进的遗传算法分别求解上下层模型。退火算法的强大跳跃能力和遗传算法的全局搜索能力能够相互补充，结合应用可以显著提升优化效果。本文的创新点：①考虑了基站、无人机与船舶动态移动特征下的VRP问题；②考虑了不同参数的无人机与无人艇执行检测任务的配置问题；③针对无人机与无人艇协同调度与无人机路径优化问题建立了双层规划模型，设计相关算法对模型进行求解。本文取得的成果：①建立了融合会合模型的MVRP模型；②求解了不同参数的无人艇和无人机组合下无人机飞行时间，确定不同型号设备对飞行时间的影响率，进而找出不同场景下最优配置方案；③设计了双层规划模型和配套求解方法，针对不同场景输出不同设备调度及具体检测方案。
1. 研究方法
1.1 问题描述
本文研究无人机与无人艇协同调度下的ECA海域检测问题。检测海域中往往通行不同类型、不同航向、不同速度的船舶，每艘待检测船舶需由一架无人机执行船舶尾气检测任务，执行检测作业的无人机均由无人艇统一运载与回收。考虑到无人机与无人艇的使用成本和检测作业的时间要求，本文所提出的无人机与无人艇协同调度问题包括：①无人艇与无人机配置问题；②无人机检测任务路径问题；③无人艇路径问题。无人艇与无人机配置问题旨在确定无人艇出动的数量以及各出动的无人艇上无人机载配情况。
本文假设所有的无人艇与无人机均由统一的调度中心指挥，不同的无人艇与无人机具有不同的速度和运行成本。此时无人机检测任务路径被描述为访问待检船舶的顺序，无人艇路径描述为回收执行完所有检测任务的无人机顺序，其中无人艇与无人机的轨迹将由会合模型描述。无人机路径优化过程满足以下假设：①无人机、无人艇和待检测船舶在运行时速度恒定，其中待检测船舶航行轨迹固定且已知；②无人机与无人艇在ECA海域中的轨迹由直线段组成，即无人机、无人艇及待检船舶2次会合点之间的轨迹为直线；③无人机、无人艇及船舶间的空间防撞避让时间忽略不计，将无人机检测时间计入总飞行时间中；④无人机与无人艇运行成本与运行时间呈线性关系，其中运行成本定义为电量消耗。基于上述假设，本文优化目标可从两方面描述：一方面，无人机调度研究主要考虑无人机总飞行时间最小[15]，出动速度越大的无人机和无人艇意味着总飞行时间越小。另一方面，当出动的无人机和无人艇速度越大意味着其单位运行成本越高。因此，针对ECA区域船舶尾气检测任务，合理配置出动的无人机与无人艇是一个较为复杂的问题。此外，即使考虑固定配置的无人机与无人艇，其作业路径问题仍然是一个NP-hard问题[16]。
无人艇基站调度无人机执行船舶排放检测任务问题可看作车辆路径问题(Vehicle Routing Problems，VRP)的变种[17]。传统的VRP问题中运输成本是固定不变的，而多无人艇调度多无人机排放检测问题考虑无人艇、无人机和船舶的实时动态性，且无人机检测序列的变化影响无人机总飞行时间。图 1为无人机与无人艇协同执行检测任务的轨迹图。由图 1可知，无人机检测船舶排放可定义为：对于待检测船舶集合I，无人艇选择投放点o′k，并投放多架无人机执行船舶尾气检测任务。无人艇以总飞行时间最短为目标确定无人机回收顺序，并依次驶往回收点d′k完成回收，每架无人机与无人艇路径组成一个闭合回路。
![]()
图 1 船舶排放检测无人艇与多无人机轨迹图Figure 1. Ship emissions inspection USV with multiple UAV trajectories1.2 无人机与无人艇协同调度双层规划模型
本文提出了一个双层规划模型，用于处理ECA海域中无人机与无人艇协同调度的船舶尾气检测问题。模型考虑降低船舶等待时间和政府运营成本。上层模型决定不同类型无人机与无人艇的数量及其配置，下层模型优化无人机的巡检路径和无人艇的回收路径。通过提高无人机与无人艇的速度，可减少船舶的等待时间，但也可能增加电量消耗和使用成本。
1.2.1 上层模型
上层模型为考虑无人机总飞行时间的无人机与无人艇配置问题。
\min f(h, q)+\boldsymbol{\omega}^{\mathrm{T}} \boldsymbol{L}(h, g), (1) \text { s.t. } \sum\limits_{g \in G} h_g \geqslant 1 \text {, } (2) \sum\limits_{k \in K} q_k^g \geqslant h_g \quad g \in G, (3) \sum\limits_{k \in K} q_k^g \leqslant M h_g \quad g \in G, (4) \sum\limits_{g \in G} q_k^g \leqslant 1 \quad k \in K, (5) h_g \in\{0, 1\} \quad g \in G, (6) q_k^g \in\{0, 1\} \quad(g \in G, k \in K), (7) 目标函数(1)由无人机飞行总时间函数f、执行检测任务总成本(无人机和无人艇单位时间的耗电量)向量L和单位转换系数向量ω组成。其中二维成本向量L中一维表示无人机成本，二维表示无人艇成本。向量ω的作用是：①时间转换系数；②对无人机与无人艇使用成本的不同侧重。约束式(2)表示执行检测任务时至少出动1艘无人艇；约束式(3)和(4)表示若无人艇出动，其必须运载至少1架无人机，其中M表示惩罚数，取值为1 000；约束式(5)表示无人机最多选择1艘无人艇作为基站；约束式(6)和(7)表示条件满足的状态。
(1) 集合
G：无人艇基站集合。K：所有无人机集。Kg：基站g上载配的无人机集合，g∈G。I：船舶集合。N：节点集合。
(2) 参数
hg：出动无人艇的数量。qkg：出动的无人机数量。dk：无人机k的初始投放点，k∈Kg，g∈G。d0：所有无人艇基站的虚拟结束点。Tok：无人机k的投放时刻，k∈Kg，g∈G。Tog：基站g投放无人机的时刻，g∈G。
(3) 决策变量
xijk：表示无人机k的检测顺序，k∈Kg, g∈G。ydpdqg：表示基站, 接收无人机p、g的顺序，g∈G, p, q∈Kgω。Sik：无人机k到达船舶节点i, i∈I的时刻，k∈Kg, g∈Gω。cij：无人机在船舶节点间飞行的时间。
1.2.2 下层模型
下层模型结合无人机、无人艇与船舶同步动态性考虑给定无人机与无人艇配置下的路径优化，涉及无人机检测任务路径与无人艇回收无人机路径。考虑到该问题与VRP问题的相似性质，下层采用网络流建模方式，以无人机飞行总时间最小化为目标。相关约束如下：
[\mathrm{VRP}] \min f(h, q)=\sum\limits_{g \in G} \sum\limits_{k \in K^g} \sum\limits_{i, j \in N^k, i \neq j} c_{i j} x_{i j}^k, (8) \sum\limits_{\mathrm{j} \in 1} x_{0^{kj}}^k=1 \quad\left(\forall k \in K^g, g \in G\right), (9) \sum\limits_{\mathrm{j} \in \mathrm{I}} x_{\mathrm{id} k}^k=1 \quad\left(\forall k \in K^g, g \in G\right), (10) \sum\limits_{g \in G} \sum\limits_{k \in K^g} \sum\limits_{i \in I U\left\{o_k\right\}} x_{i p}^k-\sum\limits_{g \in G} \sum\limits_{k \in K^g} \sum\limits_{j \in I U \left\{\hat{d}_k\right\}} x_{p j}^k=0 \quad \forall p \in I, (11) \sum\limits_{g \in G} \sum\limits_{k \in K^g} \sum\limits_{i \in N^k} x_{i j}^k=1 \quad \forall j \in I, (12) S_i^k+c_{i j}-M\left(1-x_{i j}^k\right) \leqslant S_j^k \quad\left(\forall i, j \in I, i \neq j, k \in K^g, g \in G\right), (13) S_i^k \leqslant M \sum\limits_{j \in N} x_{i j}^k \quad\left(\forall i \in I \cup\left\{o_k\right\}, k \in K^g, g \in G\right), (14) \sum\limits_{\substack{q \in K^g \\ q \neq k}} y_{o_k d_q}^g=1 \quad\left(\forall k \in K^g, g \in G\right), (15) \sum\limits_{\substack{q \in K g \\ q \neq k}} y_{d_p d_0}^g=1 \quad\left(\forall k \in K^g, g \in G\right), (16) \sum\limits_{p \in K^g} y_{d_p d_k}^g-\sum\limits_{q \in K^g} y_{d_k d_q}^g=0 \quad\left(\forall k \in K^g, g \in G\right), (17) B_{d_p}^g+c_{d_p d_q}-M\left(1-y_{d_p d_q}^g\right) \leqslant B_{d_q}^g \quad\left(\forall p, q \in K^g, p \neq q, g \in G\right), (18) B_{d_p}^g \leqslant M \sum\limits_{\substack{q \in K^g \\ d_p \neq d_q}} y_{d_p d_q}^g \quad\left(\forall p \in K^g, g \in G\right), (19) S_{d_k}^k=B_{d_k}^g \quad\left(\forall p \in K^g, g \in G\right), (20) x_{i i}^k=0 \quad\left(\forall i \in N^k, k \in K^g, g \in G\right), (21) S_{o_k}^k=T_0^k \quad\left(\forall k \in K^g, g \in G\right), (22) y_{d_p d_p}^g=0 \quad\left(\forall p \in K^g, g \in G\right), (23) B_{o_k}^g=T_0^g \quad\left(\forall k \in K^g, g \in G\right), (24) x_{i j}^k \in\{0, 1\} \quad\left(\forall i, j \in N^k, k \in K^g, g \in G\right), (25) y_{d_p d_q}^g \in\{0, 1\} \quad\left(\forall p, q \in K^g, g \in G\right), (26) 目标函数(8)表示无人机的总飞行时间；约束式(9)表示无人机从无人艇投放点ok出发后一次只能选择1艘船舶进行检测；约束式(10)表示无人机检测完任务序列中全部船舶后必须飞到回收点，无人艇在回收点完成无人机回收任务；约束式(11)为流平衡约束，表示每艘船舶节点被无人机检测的次数和离开次数相等，其中xipk为0~1变量；约束式(12)表示1艘船舶只能被1架无人机检测；约束式(13)、(14)表示无人机与船舶i的会合时刻与无人机从船舶i出发与j船舶会合的过程时间之和等于无人机到达与船舶j会合位置的时间，以约束无人机访问船舶的时间关系，其中M是惩罚数，取值为100；约束式(15)、(16)表示无人艇基站的起点和终点，为了便于求解本文引入无人艇收回全部无人机后驶到虚拟终点d0，所需要的时间t=0；约束式(17)为流平衡约束，表示无人艇投放和收回无人机的数量相等；约束式(18)、(19)表示无人艇需依次收回所有无人机；约束式(20)表示无人艇基站与执行完全部检测任务的无人机在同一时刻会合；约束式(21)~式(26)表示相关约束与条件满足的状态。
本文在解决无人机路径优化问题时融入了无人机、无人艇与船舶动态性特征，因此在[VRP]模型中引入了会合模型[18]。会合模型的计算过程可描述为：通过船舶和无人机的速度、初始位置、移动方向等已知条件，利用经典相遇问题的解方程方法[19]，根据两点间距离公式推导出船舶速度在横纵2个方向上的分量，分别以无人艇位置和船舶位置为圆心，以t时刻下无人艇行驶的距离和船舶航行的距离为半径作2个圆，两圆的交点即为会合点。该模型可计算出无人艇K的无人机与船舶i的会合位置和飞行时间。无人机与每个检测船舶会合的时间累加即为无人机飞行总时间，其中无人机被回收时与无人艇会合视为无人机与最后一艘船舶相会合。
1.3 模型求解
针对无人艇与无人机协同调度模型设计了混合启发式求解算法，上层模型采用自适应模拟退火算法，下层算法采用改进遗传算法求解。上下层模型的求解算法适应度分别为对应模型的目标函数。
1.3.1 自适应模拟退火算法
针对上层问题，本文所提出的自适应模拟退火算法可自适应控制邻域大小，进而调节搜索节奏[20]。考虑到上层问题为无人机与无人艇配置问题，在自适应模拟退火算法中编码采用单层编码。
编码长度等于可用无人机数量，每一个编码索引表示对应的无人机编号(图 2)。每一个编码表示唯一无人艇编号(如1、2、3等)。编码0表示一艘虚拟无人艇并解释为：分配到该无人艇的无人机不参与任何船舶尾气巡检任务。图 2中，出动的无人艇配置无人机情况为：无人艇1搭载无人机1、3、6；无人艇2搭载无人机2；无人艇3搭载无人机4；无人机5不参与检测任务。
基于上述编码，令X={x1, x2, …, xm}表示解，其中m表示无人机数量，xi∈{0, 1, 2, …, n} (i=1, 2, …, m)表示无人机i由无人艇xi运载执行检测任务。
算法1 自适应模拟退火算法
输入：初始温度T；降温系数K；最大迭代次数mIter；解的扰动概率p；适应度幅度q；最大连续失败次数cFail；最大连续成功次数cSuccess。
输出：最优解。
步骤：
步骤1 初始解生成。随机生成初始解作为当前解Xcur，并计算其目标函数值Ycur，设置Xbest=Xcur，Ybest=Ycur，迭代次数iter=0，失败次数nF=0，成功次数nS=0，Nfail=0。
步骤2 邻域算子。根据当前解Xcur与扰动概率p生成新解Xnew，计算目标函数值Ynew。
步骤3 更新解。计算Δ=Ybest-Ynew。采用Metropolis抽样准则，若Δ>0，则设置Xbest=Xcur=Xnew，Ybest=Ycur=Ynew，nS=nS+1，nF=0，Nfail=0；若Δ>0，则计算Paccept=exp(qΔ/T)，并根据接受概率nS=0判断是否接受新解作为当前解，nF=nF+1，nS=0，Nfail=Nfail+1。
步骤4 更新参数。若nS≥cSuccessp=max \left\{\frac{p}{2}, p_{\min }\right\} n S=0；若nF≥cFailp=min{2p, pmax}nF=0；若Nfail=0，令q=1+\frac{T \ln 2}{\varDelta} ；若Nfail>Nfail，令q=1－ \frac{T \ln 2}{\varDelta}，置Nfail=0；T=T×K，iter=iter+1。
步骤5 终止条件。迭代次数达到最大时停止。
步骤2~4将不断循环操作直至达到步骤5的终止条件。目标函数值计算时需将配置方案输入到下层模型中，下层求解完毕后得到上层目标函数值。基于上述算法流程，对关键步骤进行解释说明。
针对步骤2邻域算子的说明：依据当前解Xcur，对每一架无人机按照扰动概率p选择是否更改所选择的无人艇，若更改则按照邻域算子进行扰动。邻域算子包括2种类型：第一种是等概率算子，即该无人机等概率地从无人艇集合{0, 1, 2, …, n}中选择一艘无人艇；第二种是异概率算子，首先按照0.5概率判断该无人机是否出动，若不出动则xi=0。否则，从无人艇集合{0, 1, 2, …, n}中随机选择一艘无人艇。
针对步骤3更新解的说明：q为适应度幅度，该值表示对最优解与新解目标函数差值的增幅或减幅。当q较大时，新解的接受概率paccept将越小；当q较小时，新解的接受概率paccept将越大，该值在一定程度上控制了算法全局与局部搜索能力。
针对步骤4更新参数的说明：扰动概率p的更新与算法连续求解成功次数与连续求解失败次数有关，当算法连续求解成功次数超过一定限度时，扰动概率p减小，此时算法局部搜索能力增强；而当算法连续求解失败次数超过一定限度时，扰动概率p增大，此时算法全局搜索能力增强。其中pmax, pmin分别表示扰动概率的最大值与最小值。失败次数Nfail不同于nF，该失败次数用于更新适应度幅度q，当失败次数Nfail大于设定的阈值Nfail时，算法希望下一次解的接受概率增大即：exp(qΔ/T)=2exp(Δ/T)，此时 q=1-\frac{T \ln 2}{\varDelta}，而当算法找到比当前最优更好的解时，Nfail=0，此时算法希望下一次解的接受概率减小，即exp(qΔ/T)=exp(Δ/T)/2，此时q=1+\frac{T \ln 2}{\varDelta} 。
根据上述分析可以看出，本文设计的自适应模拟退火算法可根据算法连续求解情况平衡算法局部搜索能力与全局搜索能力，并能定量地对解的邻域进行调整以及对解的接受概率进行增减幅。
1.3.2 改进的遗传算法
多无人艇与无人机协同路径规划问题属于NP-hard问题，遗传算法(Genetic Algorithm，GA)是借鉴生物界的进化规律及其机制的随机搜索算法，具有内在的隐并行性和全局寻优能力。因此针对下层路径优化问题采用改进的遗传算法进行求解。
(1) 染色体编码与解码：采用双层独立编码的编码将问题的解表示为染色体结构，上层编码表示无人艇基站对无人机的回收顺序，下层编码表示无人机执行船舶检测的顺序，该编码方式有助于提高解的多样性，提高算法求解效率和优化结果质量。图 3展示了一种编码方式，上层编码表示无人艇基站对无人机的回收顺序，图中无人艇1回收无人机的顺序为1→2→3，无人艇2对无人机的回收顺序为5→6→4。下层编码表示无人机检测船舶尾气顺序，其中0元素为分割符，图 3获得的无人机检测方案为：无人艇1中的无人机1执行检测任务的顺序为：船舶1→船舶3；无人机2执行检测任务的顺序为：船舶2→船舶5；无人机3执行检测任务的顺序为：船舶6→船舶4。无人艇2同理。
![]()
图 3 下层模型双层独立编码示意图Figure 3. Schematic diagram of two-layer independent coding in the lower model(2) 选择策略：采用选择锦标赛选择策略从种群中选择个体进入下一代，从种群中随机选择一定数量的个体，从中选取适应度最高的个体作为父代，进入下一代的交叉和变异操作。
(3) 交叉策略：本文采用基于位置的交叉策略。随机选择Xi和Xj中一些相同的位置，每个位置以50%的概率入选。把Xi和Xj中不在这些位置的无人机设置为0，得到Xi和Xj；删除Xi中包含在Xi中的无人机得到\hat{X}_i ，删除Xi中包含在Xj中的无人机得到\hat{X}_j ；用\hat{X}_i 中的无人机顺序替换Xi中的无人机0得到子代染色体 \tilde{X}_i，用\hat{X}_j 中的无人机顺序替换Xj中的无人机0得到子代染色体 \tilde{X}_j。图 4给出了一个基于位置交叉的例子。
(4) 变异策略：随机插入变异。在解向量中随机选择一个变异位置a和插入位置b，其中a≠b。把位于位置a的无人机插入到位置b。
(5) 修复：通过交叉变异操作后的无人机船舶检测任务序列可能存在2个0元素相邻的情况。为避免进化过程中可能会导致的种群多样性减少，使得个体在局部区域内集中并可能错过全局最优解，本文引入随机修复算子。当染色体中出现了0元素相邻的情况时，对其中一个0的位置进行重置，以增加种群的多样性。修复过程如图 5所示。
(6) 适应度计算：下层模型的目标函数是最小化无人机飞行总时间，因此适应度函数应当使得较好的解具有较小的适应度值。
2. 结果与讨论
本文数值试验分为两部分，第一部分为固定无人机与无人艇配置下的路径问题算例实验；第二部分为无人机与无人艇协同调度模型算例实验。通过2.1章节的实验找到可进一步优化的点，对其进行了优化与效果对比。
2.1 固定无人机与无人艇配置下的算例实验
2.1.1 数据集设置
数据集采用随机生成，设置ECA为20 km×10 km的矩形海域，无人机速度在30~50 km/h之间，无人艇速度在10~20 km/h之间，船舶速度在10~50 km/h之间且移动方向随机。无人机集合中所有无人机均同质，无人艇集合中所有无人艇均同质。数据集名称的格式为“FfKkSsVvV′v′”，其中F表示无人机数量；K表示无人艇数量；S表示船舶数量；V表示无人机速度；V′表示无人艇速度；f, k, s, v, v′表示相应数值。
2.1.2 下层算法稳定性测试
选取“F5K3S30V30V′10”数据集，船舶速度随机生成范围为10~50 km/h，每艘无人艇固定配置5架无人机。交叉概率与变异概率取值集合均为[0.1, 0.2, …, 0.9]。通过不同交叉与变异概率组合实验确定GA的参数：交叉概率为0.7；变异概率为0.4；迭代次数为500。进一步选取“F5K3S30V30V′10”数据集，船舶速度随机生成范围为10~30 km/h，每艘无人艇固定配置5架无人机。由图 6可知：①本文改进的遗传算法收敛性良好；②下层模型的目标函数值，即特定配置下无人机飞行总时间最优值为0.54 h。
![]()
图 6 下层GA算法收敛示意图Figure 6. Schematic representation of convergence for the lower GA algorithm2.1.3 灵敏度分析
选取“F2K2S20”数据集，无人机飞行速度测试集合为[30,35,40,45,50], 无人艇行驶速度范围集合为[15,20,25]，单位均为km/h。针对无人机与无人艇的不同速度采用控制变量法进行15组测试，测试结果如表 1所示。从图 7可知：①无人机或无人艇速度变化对无人机飞行总时间有较大影响；②无人艇速度不变时，无人机速度越快，总飞行时间减小；无人机速度不变时，无人艇速度与总飞行时间没有明显的线性关系。原因是无人艇速度增加可能导致其他优先完成检测任务的无人机无法在无人艇回收目标无人机的途中与之相遇，使得无人艇只能按照回收顺序回收无人机，从而增加了总飞行时间。因此，应建立双层规划模型将无人艇速度的选取作为多无人艇基站配置多无人机路径优化问题的一部分，进一步说明本文所建模型的必要性。
表 1 无人机与无人艇速度的灵敏性分析实验结果Table 1. Experimental results of sensitivity analysis for UAV and USV speeds无人艇速度/(km·h-1) 无人机速度/(km·h-1) 30 35 40 45 50 15 0.798 0.704 0.669 0.617 0.562 20 0.541 0.731 0.642 0.616 0.530 25 0.743 0.760 0.604 0.636 0.587 ![]()
图 7 无人艇与无人机不同速度对无人机飞行时间的影响Figure 7. Impact of different speeds of USVs and UAVs on UAV flight time2.2 非固定无人机与无人艇协同调度算例实验
通过固定无人机与无人艇配置实验可以得到结论：当无人艇、无人机的速度不同时，对无人机总运行时间具有较大的影响。因此需进一步考虑异质无人机与无人艇协同调度问题并进行算力分析，设置三类不同速度与电量消耗的无人机和无人艇(表 2)。
表 2 异质无人机与无人艇参数设置Table 2. Parameter settings for heterogeneous UAVs and USVs类型 类别 速度区间/(km·h-1) 电量消耗/(kW·h-1) 数量 无人机 A 20 4 10 B 35 8 10 C 50 12 10 无人艇 Ⅰ 10 80 5 Ⅱ 15 120 5 Ⅲ 20 160 5 注：“数量”表示该ECA区域共拥有的设备数。 由于无人机与无人艇固定成本与可变成本(耗电量)差别较大，因此，设置上层目标函数中成本转换系数ωT=(0.1, 0.01)其中无人机系数取0.1，无人艇系数取0.01。
2.2.1 算法稳定性与有效性验证
(1) 两种邻域的扰动算子测试。选取数据集“F30K15S40”，船舶速度随机生成范围为10~50 km/h，船舶航向为对向交叉。其中各类型设备使用数量：无人机A、B、C各10架；无人艇Ⅰ、Ⅱ、Ⅲ各5艘。上层自适应模拟退火算法参数设置：初始温度为100；降温系数为0.98；最大迭代次数为100；Nfail=10；最大连续失败次数为3；最大连续成功次数为3；初始扰动概率为0.5。下层改进的遗传算法参数设置：交叉概率为0.7；变异概率为0.4；最大迭代次数为500，染色体数量为20。2种邻域算子下算法各独立运行5次。由图 8、图 9的实验结果可知：①使用异概率算子相较于等概率算子平均求解效果更优；②无人艇平均成本随迭代次数增加而波动下降，无人机平均成本随迭代增加波动较大。说明无人机与无人艇配置是影响协同调度的关键。
(2) 不同初始扰动的概率测试。采用与(1)相同的数据集不同概率算子，初始扰动概率P取值集合为{0.1, 0.2, 0.3, 0.4, 0.5}。结果如图 10所示，不同初始扰动概率下上层目标函数值最终都收敛于区间(170, 180)，说明算法稳定性较好。
![]()
图 10 不同扰动概率对上层目标函数值的影响Figure 10. Effect of different perturbation probabilities on the upper objective function value(3) 无人机与无人艇的配置问题实验。选取“F5K3S30V30V′10”数据集，设置A、B、C三类无人机与Ⅰ、Ⅱ、Ⅲ三类无人艇交叉组合成9种不同配置方案，9种组合中的无人机集合与无人艇集合均为同质。并设置考虑不同类型无人机与无人艇协同调度实验。由表 3可知：①无人机速度每提升15 km/h，飞行总时间平均减少23.02%，无人机成本平均增加26.45%；无人艇速度提升对飞行总时间影响较小，但无人艇速度每提升5 km/h，无人艇成本平均增加37%。②协同调度相较于固定配置下同质无人机与无人艇在飞行总时间上平均减少24.98%，无人机成本平均减少23.57%，无人艇成本平均减少42.20%。说明了将无人机路径优化问题设计为协同调度问题一部分的优越性。
表 3 不同配置无人机与无人艇组合的实验结果Table 3. Experimental results for different combinations of UAV and USV configurations配置 上层目标函数值 下层目标函数值/h 无人机成本/(kW·h-1) 无人艇成本/(kW·h-1) A-Ⅰ 136.437 9.090 29.783 487.823 A-Ⅱ 180.925 8.597 29.418 714.552 A-Ⅲ 219.504 8.681 32.265 892.792 B-Ⅰ 116.973 6.760 42.363 339.250 B-Ⅱ 148.205 6.823 42.490 494.463 B-Ⅲ 182.055 6.269 41.940 669.231 C-Ⅰ 108.294 5.380 46.882 280.156 C-Ⅱ 132.119 5.088 46.774 401.286 C-Ⅲ 153.594 5.009 46.911 508.370 协同 97.115 5.143 30.474 307.494 2.2.2 实验与灵敏度分析
选取数据集“F30K15S20”，船舶航向为对向交叉。各类型设备使用数量：无人机A、B、C各3架；无人艇Ⅰ、Ⅱ、Ⅲ各2艘。生成船舶数据集如表 4所示，由于生成的船舶轨迹均平行于X轴，因此船舶速度在Y轴上的分量为0。基于上述实验数据，上下层模型分别使用自适应模拟退火算法与改进的遗传算法求解。随着不断迭代寻优，无人机与无人艇协同调度求解结果朝着最优进化。图 11展示了目标函数值最优情况下无人机和无人艇协同调度路径优化结果，其中不同颜色实线表示不同无人机路径，蓝色虚线表示无人艇路径。表 5为优化结果的相应配置及检测方案详细数据。
表 4 待检测船舶数据集的具体数据Table 4. Specific data for the dataset of vessels to be inspected船舶编号 进入ECA区域X坐标 进入ECA区域Y坐标 速度在横坐标上的分量Vx/(kW·h-1) 速度在纵坐标上的分量Vy/(kW·h-1) 1 0 1 10 0 2 0 2 11 0 3 0 3 12 0 4 0 4 13 0 5 0 5 14 0 6 0 6 15 0 7 0 7 16 0 8 0 8 17 0 9 0 9 18 0 10 0 10 19 0 11 20 0.5 -10 0 12 20 1.5 -11 0 13 20 2.5 -12 0 14 20 3.5 -13 0 15 20 4.5 -14 0 16 20 5.5 -15 0 17 20 6.5 -16 0 18 20 7.5 -17 0 19 20 8.5 -18 0 20 20 9.5 -19 0 注：“负数”表示X轴负方向上的速度分量。 ![]()
图 11 无人机与无人艇协同调度方案路径轨迹图Figure 11. Diagram of the path trajectory of the UAVs and USVs cooperative scheduling programme表 5 详细实验结果数据Table 5. Detailed experimental results data无人艇编号与型号 回收无人机顺序 无人机编号与型号 无人机检测顺序 飞行距离/km 飞行时间/h 无人机成本/(kW·h-1) 无人艇成本/(kW·h-1) 1(Ⅰ) 3→1→2 1(A) 17→19→14→6→4 16.647 0.858 3.433 2(B) 16→9→7 17.922 0.539 2.157 3(B) 1→2→8→12 25.543 0.858 10.298 68.655 2(Ⅲ) 5→4 4(C) 15→18→11→13 25.570 0.518 7.763 5(C) 3→5→10→20 20.259 0.427 6.403 82.810 由于无人机飞行时间与飞行成本是对立相关关系，减少飞行时间意味着增加飞行成本，反之降低飞行成本意味着牺牲飞行时间。因此本节研究二者权重不同对无人机飞行时间和飞行成本的影响，将权重系数W(W∈{0, 1})添加至双层规划模型的目标函数中。上层模型目标函数：
\min W f(h, q)+(1-W) \boldsymbol{\omega}^{\mathrm{T}} L(h, g), (27) 其中，f为下层模型的目标函数，L为无人机与无人艇总电量消耗且与时间呈线性关系。使用与2.2.1 (1)相同的数据集进行实验，图 12为改变权重系数对双层规划模型目标值的影响。由图 12可知：①目标函数值随权重系数取值变化而波动，证明了算法有较强泛化能力；②不同的权重系数对无人机总飞行时间、无人机与无人艇的成本是有影响的，选取合适的权重系数会影响路径优化效果。
![]()
图 12 权重系数对双层模型结果的影响Figure 12. Influence of weighting coefficients on the results of the two-layer model3. 结论
以ECA区域中无人机巡检船舶尾气排放作为研究背景，融合无人机、无人艇和船舶同步动态移动问题特征，重点研究异质无人机与无人艇协同调度无人机路径优化问题，构建了相互嵌套的双层模型能有效表征上下两层间的交互关系。上层模型使用自适应模拟退火算法求解无人机与无人艇配置方案，下层模型使用改进的遗传算法求解无人机路径优化问题，引入并分析了权重系数对无人机飞行时间和成本的影响。通过实验验证，本文设计的模型与算法能够有效求解不同规模的数据集。后续研究中可结合考虑无人机避障策略、无人机检测时长等因素，进一步结合实际场景以提升研究的科学性与严谨性。希望本文为引入无人艇基站平台的异质无人机与无人艇船舶排放检测方案提供参考，也为使用双层规划模型求解较高复杂性VRP问题提供一种可行的求解思路。
-
![]()
图 1 船舶排放检测无人艇与多无人机轨迹图
Figure 1. Ship emissions inspection USV with multiple UAV trajectories
![]()
图 3 下层模型双层独立编码示意图
Figure 3. Schematic diagram of two-layer independent coding in the lower model
![]()
图 6 下层GA算法收敛示意图
Figure 6. Schematic representation of convergence for the lower GA algorithm
![]()
图 7 无人艇与无人机不同速度对无人机飞行时间的影响
Figure 7. Impact of different speeds of USVs and UAVs on UAV flight time
![]()
图 10 不同扰动概率对上层目标函数值的影响
Figure 10. Effect of different perturbation probabilities on the upper objective function value
![]()
图 11 无人机与无人艇协同调度方案路径轨迹图
Figure 11. Diagram of the path trajectory of the UAVs and USVs cooperative scheduling programme
![]()
图 12 权重系数对双层模型结果的影响
Figure 12. Influence of weighting coefficients on the results of the two-layer model
表 1 无人机与无人艇速度的灵敏性分析实验结果
Table 1 Experimental results of sensitivity analysis for UAV and USV speeds
无人艇速度/(km·h-1) 无人机速度/(km·h-1) 30 35 40 45 50 15 0.798 0.704 0.669 0.617 0.562 20 0.541 0.731 0.642 0.616 0.530 25 0.743 0.760 0.604 0.636 0.587 
下载: 导出CSV
表 2 异质无人机与无人艇参数设置
Table 2 Parameter settings for heterogeneous UAVs and USVs
类型 类别 速度区间/(km·h-1) 电量消耗/(kW·h-1) 数量 无人机 A 20 4 10 B 35 8 10 C 50 12 10 无人艇 Ⅰ 10 80 5 Ⅱ 15 120 5 Ⅲ 20 160 5 注：“数量”表示该ECA区域共拥有的设备数。
下载: 导出CSV
表 3 不同配置无人机与无人艇组合的实验结果
Table 3 Experimental results for different combinations of UAV and USV configurations
配置 上层目标函数值 下层目标函数值/h 无人机成本/(kW·h-1) 无人艇成本/(kW·h-1) A-Ⅰ 136.437 9.090 29.783 487.823 A-Ⅱ 180.925 8.597 29.418 714.552 A-Ⅲ 219.504 8.681 32.265 892.792 B-Ⅰ 116.973 6.760 42.363 339.250 B-Ⅱ 148.205 6.823 42.490 494.463 B-Ⅲ 182.055 6.269 41.940 669.231 C-Ⅰ 108.294 5.380 46.882 280.156 C-Ⅱ 132.119 5.088 46.774 401.286 C-Ⅲ 153.594 5.009 46.911 508.370 协同 97.115 5.143 30.474 307.494
下载: 导出CSV
表 4 待检测船舶数据集的具体数据
Table 4 Specific data for the dataset of vessels to be inspected
船舶编号 进入ECA区域X坐标 进入ECA区域Y坐标 速度在横坐标上的分量Vx/(kW·h-1) 速度在纵坐标上的分量Vy/(kW·h-1) 1 0 1 10 0 2 0 2 11 0 3 0 3 12 0 4 0 4 13 0 5 0 5 14 0 6 0 6 15 0 7 0 7 16 0 8 0 8 17 0 9 0 9 18 0 10 0 10 19 0 11 20 0.5 -10 0 12 20 1.5 -11 0 13 20 2.5 -12 0 14 20 3.5 -13 0 15 20 4.5 -14 0 16 20 5.5 -15 0 17 20 6.5 -16 0 18 20 7.5 -17 0 19 20 8.5 -18 0 20 20 9.5 -19 0 注：“负数”表示X轴负方向上的速度分量。
下载: 导出CSV
表 5 详细实验结果数据
Table 5 Detailed experimental results data
无人艇编号与型号 回收无人机顺序 无人机编号与型号 无人机检测顺序 飞行距离/km 飞行时间/h 无人机成本/(kW·h-1) 无人艇成本/(kW·h-1) 1(Ⅰ) 3→1→2 1(A) 17→19→14→6→4 16.647 0.858 3.433 2(B) 16→9→7 17.922 0.539 2.157 3(B) 1→2→8→12 25.543 0.858 10.298 68.655 2(Ⅲ) 5→4 4(C) 15→18→11→13 25.570 0.518 7.763 5(C) 3→5→10→20 20.259 0.427 6.403 82.810
下载: 导出CSV
-
[1] 殷缶, 梅深. 2022年交通运输行业发展统计公报[J]. 中国水运, 2023(7): 29-33. YIN F, MEI S. 2022 Statistical bulletin on the development of the transportation industry[J]. China Water Transport, 2023(7): 29-33.
[2] MANDLOI D, ARYA R, VERMA A K. Unmanned aerial vehicle path planning based on A* algorithm and its variants in 3D environment[J]. International Journal of System Assurance Engineering and Management, 2021, 12(5): 990-1000.
[3] KHOSIAWAN Y, PARK Y, MOON I, et al. Task scheduling system for UAV operations in indoor environment[J]. Neural Computing and Applications, 2018, 31(9): 5431-5459.
[4] YANG J, YOU X, WU G, et al. Application of reinforcement learning in UAV cluster task scheduling[J]. Future Generation Computer Systems, 2019, 95: 140-148. doi: 10.1016/j.future.2018.11.014
[5] LIU W H, ZHENG X, DENG Z H. Dynamic collision avoidance for cooperative fixed-wing UAV swarm based on normalized artificial potential field optimization[J]. Journal of Central South University, 2021, 28(10): 3159-3172. doi: 10.1007/s11771-021-4840-5
[6] ZENG J, YANG X, YANG L, et al. Modeling for UAV resource scheduling under mission synchronization[J]. Journal of Systems Engineering and Electronics, 2010, 21(5): 821-826. doi: 10.3969/j.issn.1004-4132.2010.05.016
[7] 陆玲玲, 胡志华. 海岛无人机配送中继站选址-路径优化[J]. 大连理工大学学报, 2022, 62(3): 299-308. LU L L, HU Z H, Location-routing optimization of island drone delivery relay station[J]. Journal of Dalian University of Technology, 2022, 62(3): 299-308.
[8] QADIR Z, ZAFAR M H, MOOSAVI S K R, et al. Autonomous UAV path-planning optimization using metaheuristic approach for predisaster assessment[J]. IEEE Internet of Things Journal, 2021, 9(14): 12505-12514.
[9] OUELMOKHTAR H, BENMOUSSA Y, BENAZZOUZ D, et al. Energy-based USV maritime monitoring using multi-objective evolutionary algorithms[J]. Ocean Engineering, 2022, 253: 111182/1-8.
[10] SUN X, ZHANG L, SONG D L, et al. A novel path planning method for multiple USVs to collect seabed-based data[J]. Ocean Enginneering, 2023, 269: 113510/1-12.
[11] GUO X H, JI M J, ZHAO Z W, et al. Global path planning and multi-objective path control for unmanned surface vehicle based on modified particle swarm optimization (PSO) algorithm[J]. Ocean Engineering, 2020, 216: 107693/1-16.
[12] WANG Z, LI G F, REN J. Dynamic path planning for unmanned surface vehicle in complex offshore areas based on hybrid algorithm[J]. Computer Communications, 2021, 166: 49-56.
[13] 李杨飞, 江辉仙. 基于BIM的消防灭火动态路径规划研究[J]. 福建师范大学学报(自然科学版), 2022, 38(1): 69-75;116. LI Y F, JIANG H X. Study on dynamic planning of fire fighting path based on BlM[J]. Journal of Fujian Normal University (Natural Science Edition), 2022, 38(1): 69-75;116.
[14] 杨秀娟, 曾智勇. 基于YOLOv5的无人机航拍改进目标检测算法Dy-YOLO[J]. 福建师范大学学报(自然科学版), 2024, 40(1): 76-86. YANG X J, ZENG Z Y. Dy-YOLO: improved UAV image target detection algorithm base on YOLOv5[J]. Journal of Fujian Normal University (Natural Science Edition), 2024, 40(1): 76-86.
[15] SHEN Y, ZHU Y L, KANG H W, et al. UAV path planning based on multi-stage constraint optimization[J]. Drones, 2021, 5(4): 144/1-26.
[16] ZHOU F, ZHU L T, ZOU J, et al. Tracking and measuring plumes from sailing ships using an unmanned aerial vehicle[J]. IET Intelligent Transport Systems, 2023, 17(2): 285-294.
[17] CHEN X T, LI Q, LI R H, et al. UAV Network Path Planning and optimization using a vehicle routing model[J]. Remote Sensing, 2023, 15(9): 22-27.
[18] 胡碟, 胡志华, 田曦丹. 考虑船舶实时位置的船舶尾气排放检测无人机路径优化[J]. 大连海事大学学报: 2024, 50(1): 28-38. HU D, HU Z H, TIAN D X. Routing drones for ship exhaust emission detection considering real-time ship location[J]. Journal of Dalian Maritime University, 2024, 50(1): 28-38.
[19] HU Z H, LIU T C, TIAN X D. A drone routing problem for ship emission detection considering simultaneous movements[J]. Atmosphere, 2023, 14(2): 373/1-23.
[20] VENKATACHALAM S, SUNDAR K, RATHINAM S. A two-stage approach for routing multiple unmanned aerial vehicles with stochastic fuel consumption[J]. Sensors, 2018, 18(11): 3756/1-13.
计量
- 文章访问数: 39
- HTML全文浏览量: 3
- PDF下载量: 526
