基于自适应大规模邻域搜索算法的多车辆与多无人机协同配送方法  

The cooperative delivery of multiple vehicles and multiple drones based on adaptive large neighborhood search

作　　者：伍国华 毛妮 徐彬杰 马中强 赵苛欣 李志猛[2] WU Guo-hua;MAO Ni;XU Bin-jie;MA Zhong-qiang;ZHAO Ke-xin;LI Zhi-meng(School of Traffic and Transportation Engineering,Central South University,Changsha 410075,China;School of Systems Enginering,National University of Technology,Changsha 410073,China)

机构地区：[1]中南大学交通运输工程学院,长沙410075 [2]国防科技大学系统工程学院,长沙410073

出　　处：《控制与决策》2023年第1期201-210,共10页Control and Decision

基　　金：国家自然科学基金面上项目(62073341)。

摘　　要：针对物流配送需求大、“最后一公里”交付困难等问题,提出带有动态能耗约束的多车辆与多无人机协同配送问题,并以最小化配送时间为目标建立混合整数规划模型(MIP).为解决该问题,设计K-means聚类和最近邻协同的初始解生成算法,并提出基于问题领域知识的自适应大规模邻域搜索算法(adaptive large neighborhood search,ALNS).在不同规模算例上的实验结果表明,所提出的算法相比于模拟退火算法、变邻域搜索算法和遗传算法在求解质量和求解效率方面都具有一定的优势,求解质量分别平均提升23.8%、23.3%和5.7%,表明ALNS较对比算法能够更好地平衡全局搜索和局部搜索.此外.灵敏度分析实验表明,无人机载重能力和无人机续航能力是影响包裹配送时间的两个关键因素.To solve the problem of huge distribution demand and "last mile" distribution,this paper first proposes the cooperative delivery of multiple vehicles and multiple drones with dynamic energy consumption(CDMVMD-DEC),and provides a mixed integer programming model(MIP) aimed at minimizing the delivery time.To solve the problem efficiently,the adaptive large neighborhood search(ALNS) based on problem domain knowledge is proposed,along with the combination of the K-means clustering and the nearest neighbor for constructing the initial solution.Experiments on different-scale instances demonstrate that the ALNS outperforms the simulated annealing,variable neighborhood search and genetic algorithm in solution quality and computational time.In terms of solution quality,the performance of the ALNS is improved by 23.8 %,23.3 % and 5.7 % respectively.The results of experiments show that ALNS provides a better balance between global search and local search.Moreover,the results of the sensitivity test show that the load capacity and endurance of drone are the important factors affecting the delivery time.

关 键 词：车辆与无人机 协同配送 整数规划 动态能耗 路径规划 自适应大规模邻域搜索 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]