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

中南大学交通运输工程学院

作者简介:

通讯作者:

中图分类号:

TP273

基金项目:

国家自然科学基金项目(面上项目,重点项目,重大项目)


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

School of Traffic and Transportation Engineering, Central South University

Fund Project:

The National Natural Science Foundation of China (General Program, Key Program, Major Research Plan)

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

    针对物流配送需求大、“最后一公里”交付困难等问题, 本文首次提出带有动态能耗约束的多车辆与多无人机协同配送问题, 并以最小化配送时间为目标建立了混合整数规划模型 (MIP). 为解决该问题, 设计了 K-means聚类和最近邻协同的初始解生成算法, 并提出了基于问题领域知识的自适应大规模邻域搜索算法(Adaptive LargeNeighborhood 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 eighborhood Search (ALNS) based on problem domain knowledge is proposed, along with the combination of K-means Clustering and Nearest Neighbor for constructing the initial solution. Experiments on different-scale instances demonstrate that ALNS outperforms Simulated Annealing, Variable Neighborhood Search and Genetic Algorithm in solution quality and computational time. In terms of solution quality, the performance of 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 sensitivity test prove that the load capacity and endurance of drone are the important factors affecting the delivery time.

    参考文献
    相似文献
    引证文献
引用本文
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-12-29
  • 最后修改日期:2022-11-06
  • 录用日期:2022-04-15
  • 在线发布日期: 2022-05-02
  • 出版日期: