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

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

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [24]
  • |
  • 相似文献 [20]
  • | | |
  • 文章评论
    摘要:

    针对物流配送需求大、“最后一公里”交付困难等问题,提出带有动态能耗约束的多车辆与多无人机协同配送问题,并以最小化配送时间为目标建立混合整数规划模型(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.

    参考文献
    [1] Murray C C, Chu A G.The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery[J].Transportation Research---Part C: Emerging Technologies, 2015, 54: 86-109.
    [2] Scott J E, Scott C H.Drone delivery models for medical emergencies [J].Delivering Superior Health and Wellness Management with IoT and Analytics, 2019, 28: 69-85.
    [3] Rupinder B, Benedict H, Wai S L, et al.Google's wing drones deliver essentials during coronavirus pandemic[EB/OL].(2020-04-15)[2021-3-29].https:// www.dezeen.com/2020/04/15/google-wing-drone- delivery-coronavirus-virginia/.
    [4] Chen D W, Pan S L, Chen Q, et al.Vehicle routing problem of contactless joint distribution service during COVID-19 pandemic[J].Transportation Research Interdisciplinary Perspectives, 2020, 8: 100233.
    [5] UPS has a delivery truck that can launch a drone[EB/OL].(2017-02-21)[2021-3-29].https://www.theverge.com/2017/2/21/14691062/ups-drone-delivery- truck-test-completed-video.
    [6] Agatz N, Bouman P, Schmidt M.Optimization approaches for the traveling salesman problem with drone[J].Transportation Science, 2018, 52(4): 965-981.
    [7] Murray C C, Raj R.The multiple flying sidekicks traveling salesman problem: Parcel delivery with multiple drones[J].Transportation Research---Part C: Emerging Technologies, 2020, 110: 368-398.
    [8] Sacramento D, Pisinger D, Ropke S.An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones[J].Transportation Research---Part C: Emerging Technologies, 2019, 102: 289-315.
    [9] Chen C, Demir E, Huang Y.An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots[J].European Journal of Operational Research, 2021, 294(3): 1164-1180.
    [10] Kitjacharoenchai P, Ventresca M, Moshref-Javadi M, et al.Multiple traveling salesman problem with drones: Mathematical model and heuristic approach[J].Computers & Industrial Engineering, 2019, 129: 14-30.
    [11] Poikonen S, Golden B.Multi-visit drone routing problem[J].Computers & Operations Research, 2020, 113: 104802.
    [12] Dorling K, Heinrichs J, Messier G G, et al.Vehicle routing problems for drone delivery[J].IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2017, 47(1): 70-85.
    [13] Moshref-Javadi M, Hemmati A, Winkenbach M.A comparative analysis of synchronized truck-and-drone delivery models[J].Computers & Industrial Engineering, 2021, 162: 107648.
    [14] Ropke S, Pisinger D.An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J].Transportation Science, 2006, 40(4): 455-472.
    [15] 孙棣华, 杨陈成, 廖孝勇, 等.基于公交GPS数据的交叉口信号配时参数估计[J].控制与决策, 2018, 33(4): 724-730.(Sun D H, Yang C C, Liao X Y, et al.Signal timing estimation for intersections using bus GPS data[J].Control and Decision, 2018, 33(4): 724-730.)
    [16] 李国明, 李军华.基于混合禁忌搜索算法的随机车辆路径问题[J].控制与决策, 2021, 36(9): 2161-2169.(Li G M, Li J H.Stochastic vehicle routing problem based on hybrid tabu search algorithm[J].Control and Decision, 2021, 36(9): 2161-2169.)
    [17] Ric.How much weight can delivery drones carry? -UnmannedCargo.org[EB/OL].(2020-02-13) [2021-12- 14].http://unmannedcargo.org/how-much-weight-can- delivery.
    [18] Ya?mur E, Kesen S E.Multi-trip heterogeneous vehicle routing problem coordinated with production scheduling: Memetic algorithm and simulated annealing approaches[J].Computers & Industrial Engineering, 2021, 161: 107649.
    [19] Hansen P, Mladenovi N.Variable neighborhood search[M].Berlin: Springer, 2003: 145-184.
    [20] 何庆, 吴意乐, 徐同伟.改进遗传模拟退火算法在TSP优化中的应用[J].控制与决策, 2018, 33(2): 219-225.(He Q, Wu Y L, Xu T W.Application of improved genetic simulated annealing algorithm in TSP optimization[J].Control and Decision, 2018, 33(2): 219-225.)
    [21] Christofides N.The vehicle routing problem[J].Combinatorial Optimization, 1979, 10(1): 315-338.
    [22] Augerat P, Naddef D, Belenguer J, et al.Computational results with a branch and cut code for the capacitated vehicle routing problem[R].Grenoble: Université Joseph Fourier, 1995.
    [23] Liu Y, Luo Z H, Liu Z, et al.Cooperative routing problem for ground vehicle and unmanned aerial vehicle: The application on intelligence, surveillance, and reconnaissance missions[J].IEEE Access, 2019, 7: 63504-63518.
    [24] Derrac J, García S, Molina D, et al.A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms[J].Swarm and Evolutionary Computation, 2011, 1(1): 3-18.
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

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

复制
分享
文章指标
  • 点击次数:665
  • 下载次数: 1110
  • HTML阅读次数: 1840
  • 引用次数: 0
历史
  • 在线发布日期: 2022-12-23
  • 出版日期: 2023-01-20
文章二维码