Abstract
Combining an energy-efficient drone with a high-capacity truck for last-mile package delivery can benefit operators and customers by reducing delivery times and environmental impact. However, directly integrating drone flight dynamics into the combinatorially hard truck route planning problem is challenging. Simplified models that ignore drone flight physics can lead to suboptimal delivery plans. We propose an integrated formulation for the joint problem of truck route and drone trajectory planning and a new end-to-end solution approach that combines optimization and machine learning to generate high-quality solutions in practical online runtimes. Our solution method trains neural network predictors based on offline solutions to the drone trajectory optimization problem instances to approximate drone flight times, and uses these approximations to optimize the overall truck-and-drone delivery plan by augmenting an existing order-first-split-second heuristic. Our method explicitly incorporates key kinematics and energy equations in drone trajectory optimization, and thereby outperforms state-of-the-art benchmarks that ignore drone flight physics. Extensive experimentation using synthetic datasets and real-world case studies shows that the integration of drone trajectories into package delivery planning substantially improves system performance in terms of tour duration and drone energy consumption. Our modeling and computational framework can help delivery planners achieve annual savings worth millions of dollars while also benefiting the environment.
Abstract (translated)
将节能型无人机与高载货量卡车结合用于最后一公里包裹递送,可以同时为运营商和客户减少配送时间并降低环境影响。然而,直接将无人机飞行动力学整合到组合难题的卡车路线规划问题中颇具挑战性。忽略无人机飞行物理学的简化模型会导致次优的交付计划。我们提出了一种针对卡车路线与无人机轨迹规划联合问题的整体建模方法,并引入一种新的端到端解决方案方法,该方法结合了优化和机器学习技术,能够在实际在线运行时间内生成高质量方案。 我们的解决策略基于离线解算出的无人机轨迹优化实例训练神经网络预测器来近似无人机飞行时间,并利用这些近似值通过增强现有的“先排序后分割”启发式算法来优化整体卡车与无人机递送计划。我们在无人机轨迹优化中显式地纳入了关键运动学和能量方程,从而超越了忽略无人机飞行物理学的最新基准方法。 通过对合成数据集及现实世界案例研究进行广泛的实验验证,我们发现将无人机路径整合到包裹配送规划之中显著提升了系统的性能指标,包括行程时间和无人机能耗。我们的建模与计算框架可以帮助递送计划者实现每年数百万美元的成本节省,并且对环境也有积极影响。
URL
https://arxiv.org/abs/2507.16259