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

1. 中南大学 交通运输工程学院,长沙 410075;2. 国防科技大学 系统工程学院,长沙 410073

作者简介:

通讯作者:

E-mail: zmli@nudt.edu.cn.

中图分类号:

TP273

基金项目:

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


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

1. School of Traffic and Transportation Engineering,Central South University,Changsha 410075,China;2. School of Systems Enginering, National University of Technology,Changsha 410073,China

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    针对物流配送需求大、“最后一公里”交付困难等问题,提出带有动态能耗约束的多车辆与多无人机协同配送问题,并以最小化配送时间为目标建立混合整数规划模型(MIP).为解决该问题,设计K-means聚类和最近邻协同的初始解生成算法,并提出基于问题领域知识的自适应大规模邻域搜索算法(adaptive large neighborhood search,ALNS).在不同规模算例上的实验结果表明,所提出的算法相比于模拟退火算法、变邻域搜索算法和遗传算法在求解质量和求解效率方面都具有一定的优势,求解质量分别平均提升23.8$%$、23.3$%$和5.7$%$,表明ALNS较对比算法能够更好地平衡全局搜索和局部搜索.此外.灵敏度分析实验表明,无人机载重能力和无人机续航能力是影响包裹配送时间的两个关键因素.

    Abstract:

    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.

    参考文献
    相似文献
    引证文献
引用本文

伍国华,毛妮,徐彬杰,等.基于自适应大规模邻域搜索算法的多车辆与多无人机协同配送方法[J].控制与决策,2023,38(1):201-210

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期: 2022-12-23
  • 出版日期: 2023-01-20
文章二维码