计算机工程与应用 ›› 2021, Vol. 57 ›› Issue (19): 259-266.DOI: 10.3778/j.issn.1002-8331.2011-0114

• 工程与应用 • 上一篇    下一篇

基于无人机-配送车联合配送的优化算法研究

熊兴隆,刘佳,李猛,马愈昭   

  1. 1.中国民航大学 天津市智能信号与图像处理重点实验室,天津 300300
    2.中国民航大学 电子信息与自动化学院,天津 300300
    3.中国民航大学 民航空管研究院,天津 300300
  • 出版日期:2021-10-01 发布日期:2021-09-29

Research on Optimization Algorithm Based on Drone-Delivery Vehicle Joint Delivery

XIONG Xinglong, LIU Jia, LI Meng, MA Yuzhao   

  1. 1.Tianjin Key Laboratory for Advanced Signal Processing, Civil Aviation University of China, Tianjin 300300, China
    2.College of Electronic Information and Automation, Civil Aviation University of China, Tianjin 300300, China
    3.Institute of Air Traffic Management, Civil Aviation University of China, Tianjin 300300, China
  • Online:2021-10-01 Published:2021-09-29

摘要:

针对物流配送领域的一种新型交付方式——无人机联合配送车协同配送包裹,研究无人机与配送车联合路径以最小化交付时间的问题,提出了一种新型优化迭代算法。该算法将问题分为两步,首先确定配送车路线及客户节点分配,然后固定配送车路线及无人机节点,确定二者汇合节点生成无人机配送路线。算法最后保留满足约束条件的无人机路线及对应配送车路线,得到联合配送总耗时。以此方式从最少的配送车节点开始迭代,通过更新全局上界得到最优解。通过对10、11节点的示例验证,表明该算法能够有效缩小搜索范围,提高运行效率,在合理时间内求解中小规模示例。

关键词: 路径优化, 新型优化迭代算法, 无人机, 配送车, 联合配送

Abstract:

Aiming at a new delivery method in the field of logistics distribution—drone combined with delivery vehicle to coordinate parcel delivery, and to study the joint path of drone and delivery vehicle to minimize delivery time, this paper proposes a new optimization iterative algorithm. The algorithm divides the problem into two steps: firstly, determine the delivery vehicle route and customer node allocation, then fix the delivery vehicle route and the drone node, and determine the two merging nodes to generate the drone delivery route. At the end of the algorithm, the drone route and the corresponding delivery vehicle route that meet the constraints are retained to obtain the total time for joint delivery. In this way, starting from the least delivery vehicle node, iteratively obtain the optimal solution by updating the global upper bound. The verification of examples on nodes 10 and 11 shows that the algorithm can effectively narrow the search range, improve operating efficiency, and solve small and medium-sized examples in a reasonable time.

Key words: route optimization, new optimization iterative algorithm, unmanned aerial vehicle, delivery vehicle, joint delivery