Abstract: As a critical link in urban logistics, the “last mile” delivery faces challenges of low efficiency due to geographical constraints and traffic regulations that limited traditional truck-based distribution. The truck-drone collaborative delivery mode has the potential to overcome obstacles and improve timeliness; however, it imposes high requirements on drone takeoff and landing site configuration and truck-drone coordination. Considering potential drone takeoff and landing sites and comprehensive operational capabilities, a linear integer programming model that minimized total delivery time was constructed and an adaptive large neighborhood search (ALNS) algorithm incorporating a dynamic threshold acceptance criterion was proposed. Numerical experiments were conducted based on Solomon benchmark instances and real JD.com delivery cases to verify the validity of the proposed model and algorithm. The results show that: in small-scale benchmark instances, the improved ALNS can obtain a solution that is close to that of Gurobi (with an average of 415.00 seconds) within an average of 6.70 seconds, with an average Gap1 not exceeding 0.30%; in medium-scale and large-scale instances, Gurobi fails to find solutions within the prescribed time, while the improved ALNS achieves overall better delivery time than the traditional ALNS does, with a Gap2 of 9.40%. In two 100-node instances, the actual gap between the improved ALNS solution and the theoretical optimal solution does not exceed 15.20%. Compared with the truck-only mode, the collaborative delivery mode reduces delivery time by up to 19.20%, with an average saving of 13.80%. In practical examples, the collaborative delivery model can save 23.90% of the overall delivery time compared to the truck-only model. The convergence results of the algorithm indicate that the improved ALNS can accelerate convergence by dynamically adjusting the acceptance threshold. Sensitivity analysis indicates that when the drone endurance exceeds approximately 3,960 s and the payload capacity exceeds approximately 12,000 g, the improvement in delivery time diminishes significantly. In medium-scale instances, collaborative delivery efficiency is optimized when the number of potential takeoff and landing sites is approximately 7 and the spatial spacing is approximately 4,600 m. The improved ALNS based on site-feature operators reduces average delivery time by 0.40%, 1.30%, and 3.00% in small-scale, medium-scale, and large-scale instances, respectively.

Key words: traffic and transportation engineering; truck-drone collaborative delivery; drone takeoff and landing stations; adaptive large neighborhood search algorithm; route optimization

摘要： “最后一公里”作为城市物流的关键环节，传统卡车配送受地理环境和交通管制限制，配送效率低下。卡车-无人机协同配送模式具备跨越障碍、提升时效的潜力，但对无人机起降站点设置及车机协同要求较高。考虑无人机潜在起降站点和综合能力，构建最小化总配送时间的线性整数规划模型，提出融合动态阈值接受准则的自适应大邻域搜索(adaptive large neighborhood search,ALNS)求解算法。基于Solomon标准算例和京东实际配送算例开展数值试验，验证模型及算法的有效性。结果表明：在小规模标准算例中，改进ALNS算法在平均6.70 s内即可获得与Gurobi算法在平均415.00 s接近的解，平均相对误差不超过0.30%；在中、大规模算例中，Gurobi算法已无法在规定时间内求解，而改进ALNS算法求得的配送时间整体优于传统ALNS算法，其相对误差为9.40%；在2个100节点算例中，改进ALNS算法解相对于理论最优解的实际相对误差不超过15.20%。与仅卡车模式相比，协同配送模式的配送时间最高可降低19.20%，平均节省13.80%；在实际算例中，协同配送模型较仅卡车模型可将整体配送时间节省23.90%。算法收敛性结果表明，改进ALNS算法能通过动态调整接受阈值加速收敛。敏感性分析表明：当无人机续航超过约3 960 s、载重能力超过约12 000 g后，配送时间的改善幅度明显减小；在中等规模算例中，当潜在起降站点数约为7个、空间间距约为4 600 m时，协同配送效率最优；基于站点特征算子的改进ALNS算法，于小、中、大规模算例求解的平均配送时间降幅分别为0.40%、1.30%和3.00%。

关键词: 交通运输工程；卡车-无人机协同配送；无人机起降站点；自适应大邻域搜索算法；路径优化