卡车-无人机混合配送的两阶段求解方法

Two-Stage Solution Method for Truck-Drone Hybrid Delivery

利用无人机成本低、受地面交通状况影响少的特点,考虑卡车-无人机混合配送路径优化问题,在多卡车同时配送且存在单个包裹重量超出无人机最大载重情形下,构建问题模型,并提出两阶段求解方法。第一阶段,采用变邻域模拟退火算法求解载重约束下卡车车辆路径问题,为货物指派配送车辆并确定需要的卡车数量;第二阶段,设计一种自适应K-means聚类方法,对每辆卡车运送包裹的目的地进行聚类,聚类中心即移动配送点,也是无人机发射点,再对无人机配送路径和卡车行驶路径进行协同优化,实现成本最小化。两个阶段均采用Python编程实现。仿真结果表明,本文提出的方法较文献中的方法具有更好的优化效果和普适性。

Based on the characteristics of low cost and less impact of ground traffic conditions of drones,a problem model was built and a two-stage solution method was proposed for the truck-drone hybrid distribution routing optimization problem,considering the simultaneous delivery of multipletrucks and the weight of a single package exceeding the maximum load of drones.In the first stage,the variable neighborhood simulated annealing algorithm was used to solve the truck routing problem under load constraint,assign the goods to each truck and determine the number of trucks needed.In the second stage,an adaptive K-means clustering method was designed to cluster the destinations of each truck delivering packages,and the clustering centers were the mobile distribution sites and the drone launching points.Then,a collaborative optimization of drone delivery paths and truck driving routes was carried out to minimize the cost.The two stages were all implemented using Python programming.The simulation results show that the proposed method has a better optimization effect and universality than the methods in the literature.