School of Traffic and Transportation Engineering, Central South University
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 较对比算法更好的平衡了全局搜索和局部搜索. 此外. 灵敏度分析实验表明无人机载重能力和无人机续航能力是影响包裹配送时间的两个关键因素.
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.