计算机工程与应用 ›› 2023, Vol. 59 ›› Issue (12): 326-332.DOI: 10.3778/j.issn.1002-8331.2204-0152

• 工程与应用 • 上一篇    

限制区下货车联合无人机配送路径问题研究

杨雷博,周俊   

  1. 上海工程技术大学 机械与汽车工程学院,上海 201620
  • 出版日期:2023-06-15 发布日期:2023-06-15

Research on Distribution Path Problem of Truck Combined with UAV in Restricted Area

YANG Leibo, ZHOU Jun   

  1. School of Mechanical and Automotive Engineering, Shanghai University of Engineering Science, Shanghai 201620, China
  • Online:2023-06-15 Published:2023-06-15

摘要: 考虑到在灾区、疫情区等存在限制区的情况,且物流配送中末端配送耗时长、效率低等问题,物流企业尝试结合货车与无人机自身特点,扬长避短,采用“货车+无人机”联合配送模式进行配送。提出了一种在限制区下一辆车携带多架无人机的货车支持无人机配送解决方案,并构造了以最小服务时间为优化目标的双层规划求解方法,第一层,针对货车停靠点的选取,设计了一种结合DBSCAN聚类和[K]-means聚类不同特点的多阶段融合聚类算法,第二层,以车辆路径问题为基础设计采用蚁群-模拟退火融合算法构造了一车携带多架无人机形式的配送路线;通过对不同算例的求解,验证了算法的计算性能和融合聚类的优越性,以某县物流配送为实例进行求解,结果表明在有效解决区域限制问题的情况下,相比传统配送模式在最终服务时间也缩短了41.4%,有效地提高了末端物流配送的效率。

关键词: 综合运输, 车机联合, 聚类算法, 限制区物流, 路径研究

Abstract: Considering that there are restricted areas in disaster areas, epidemic areas, etc., as well as long time and is low efficiency in logistics distribution, logistics companies try to combine the characteristics of trucks and drones to maximize strengths and avoid weaknesses, and “truck+drone”, delivery mode is adopted for delivery. This paper proposes a solution for the delivery of UAVs supported by a truck carrying multiple UAVs for the next vehicle in the restricted area, and constructs a two-layer solving method with the minimum service time as the optimization goal. The first layer, a multi-stage fusion clustering algorithm that combining the different characteristics of DBSCAN clustering and [K]-means clustering for the selection of truck stops is designed. The second layer, based on the vehicle routing problem, is designed and constructed using the ant colony-simulated annealing fusion algorithm. One vehicle carries a distribution route in the form of multiple UAVs. Through solving different examples, the computational performance of the algorithm and the superiority of fusion clustering are verified. Taking a county logistics distribution as an example, the results show that it is an effective solution. In the case of regional restrictions, the final service time is also shortened by 41.4% compared with the traditional distribution mode, which effectively improves the efficiency of terminal logistics distribution.

Key words: integrated transportation, vehicle-drone combination, clustering algorithm, restricted area logistics, path research