基于两阶段算法的多无人机船舶排放监测选址与路径优化  

Location and routing optimization problem for detecting multi-drone ship emissions based on a bi-stage algorithm

作　　者：胡碟 胡志华[1] 李姚娜 HU Die;HU Zhihua;LI Yaona(Logistics research center,Shanghai Maritime University,Shanghai 201306,China)

机构地区：[1]上海海事大学物流研究中心,上海201306

出　　处：《中国航海》2025年第1期165-173,共9页Navigation of China

基　　金：国家重点研发计划项目(2023YFE0113200);上海市自然科学基金面上项目(23ZR1426500)。

摘　　要：针对船舶与无人机同时运动和船舶航行不确定性的特点,建立多基站多无人机的选址路径随机规划模型。基于船舶(S策略)和无人机(D策略)构造子路径的序列插入解码算法,结合遗传算法与禁忌搜索算法,设计两阶段启发式算法。第一阶段考虑船舶运动不确定性,采用禁忌搜索算法求解基站选址问题;第二阶段基于基站选址结果,采用遗传算法优化无人机监测路径。数值试验表明,在相同的应用场景中,相比于S策略,D策略可使结果优化7%且求解时间缩短50%;当基站选址考虑船舶航行不确定性时无人机飞行距离可缩短10%。飞行距离对无人机数量配置具有显著敏感性,在2个基站3~5架无人机的场景中,每增加1架无人机,飞行距离增加15%以上;不同场景中飞行速度提升5%,飞行距离平均减少5%左右。该方法可有效生成满足运动船舶的多无人机巡检路径,为海事监管领域提供技术支持。A stochastic programming model is devised for the multi-base,multi-drone location and routing problem,considering the simultaneous movements of drones and ships as well as ship movement uncertainty.A decoding algorithm is developed to divide a sequence into sub-routes using ship-based and drone-based strategies.Furthermore,a bi-stage heuristic algorithm is proposed,combining a genetic algorithm and Tabu search.In the bi-stage algorithm,the first stage addresses ship movement uncertainty and employs Tabu search to solve the drone base station location problem.The second stage uses the genetic algorithm to route the drones for detection based on the location results.Numerical experiment results show that,in the same application scenario,the drone-based(D)strategy can optimize flying distance by 7%while reducing computing time by 50%compared to the ship-based(S)strategy.Considering ship movement uncertainty can reduce flying distance by 10%for the drone base station location solution.Flying distance is sensitive to the number of available drones.For example,in a scenario with two base stations and 3-5 drones,adding one drone may increase flying distance by 15%.Speeding up the drones by 5%may reduce flying distance by 5%.This method can effectively generate multi-UAV inspection paths that meet the requirements of moving ships,providing technical support for maritime supervision.

关 键 词：无人机路径问题 选址路径优化问题 船舶排放监测 遗传算法 两阶段算法 

分 类 号：U698.7[交通运输工程—港口、海岸及近海工程]