改进混合粒子群算法求解带时间窗的无人机与车辆协同路径调度问题  

Improved hybrid particle swarm optimization algorithm for vehiclerouting problem with drone and time window

作　　者：叶立威 吴钧皓 戚远航 罗浩宇 黄戈文[3] 王福杰 Ye Liwei;Wu Junhao;Qi Yuanhang;Luo Haoyu;Huang Gewen;Wang Fujie(School of Computer Science,University of Electronic Science&Technology of China,Zhongshan Institute,Zhongshan Guangdong 528402,China;School of Automation,Guangdong University of Technology,Guangzhou 510006,China;Information&Network Center,Jiaying University,Meizhou Guangdong 514015,China;Elite Engineers College of Dongguan University of Technology,Dongguan Guangdong 523808,China)

机构地区：[1]电子科技大学中山学院计算机学院,广东中山528402 [2]广东工业大学自动化学院,广州510006 [3]嘉应学院信息网络中心,广东梅州514015 [4]东莞理工学院卓越工程师学院,广东东莞523808

出　　处：《计算机应用研究》2024年第8期2336-2342,共7页Application Research of Computers

基　　金：国家自然科学基金资助项目(62203116);广东省基础与应用基础研究基金资助项目(2022A1515240058);广东省普通高校重点领域专项(2022ZDZX4049,2022ZDZX1045,2023ZDZX1040);广东省普通高校青年创新人才项目(2022KTSCX138,2022KQNCX153,2023KQNCX102);中山市社会公益与基础研究项目(2021B2063);嘉应学院人才科研启动项目(2022RC127)。

摘　　要：为提高物流配送效率,考虑时间窗、无人机换电以及无人机多点连续配送等因素,提出了一种带时间窗的车辆与无人机协同配送问题,并设计一种带局部搜索的混合粒子群算法进行求解。该算法以混合粒子群算法为核心,通过构建高效的编解码策略实现了问题解空间到算法搜索空间的转换。进一步,该算法融合单点插入策略、车辆更换策略、无人机更换策略组成局部搜索策略,以此提高算法寻优能力。实验结果表明:所提模型比纯车辆配送的模型效率更高,节省了31.51%的成本;所提算法优于四种对比算法,优化率最高达到82.08%。In order to improve the delivery efficiency of logistics,this paper proposed a vehicle routing problem with drone and time window considered by the time window,UAV(unmanned aerial vehicle)power change and multi-point continuous delivery of UAV.Then,this paper proposed a hybrid particle swarm optimization algorithm with local search to solve it.Based on the hybrid particle swarm optimization algorithm,the proposed algorithm transformed the problem solution space into the algorithm search space by constructing an efficient encoding and decoding strategy.Further,the proposed algorithm combined a single point insertion strategy,a vehicle replacement strategy and a UAV replacement strategy to form a local search strategy to improve the optimization ability.The experimental results show that the proposed model is more efficient than the model of pure vehicle distribution and saves 31.51%of the cost.The proposed algorithm is better than the four comparison algorithms,and its highest optimization rate is 82.08%.

关 键 词：无人机 车辆调度 粒子群 时间窗 车辆路径问题 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]