arXiv:2509.18162cs.LG2025-09

用强化学习优化无人机与卡车协同配送,显著缩短配送时间。

A Simple and Reproducible Hybrid Solver for a Truck-Drone VRP with Recharge

  • 结合自适应大邻域搜索与小型注意力策略,动态规划无人机起降时机。
  • 在50个节点的实例上平均完成时间比传统算法快2.73%。
  • 适合研究物流优化、智能调度及可复现算法设计的读者。

我们研究带电池管理的一车一机最后一公里配送问题:无人机飞行速度为卡车两倍,每次飞行需满足续航约束,每次送货后必须在卡车上充电才能再次起飞。提出一种混合强化学习求解器,将基于ALNS的卡车路径(含2-opt/3-opt和Or-opt)与小型指针/注意力策略相结合,该策略通过硬性可行性掩码处理续航与充电约束,利用快速精确的时间线模拟器计算真实完工时间,并支持掩码贪婪/束搜索解码。在欧几里得实例中,当节点数N=50,续航率E=0.7,充电率R=0.1时,平均完工时间为5.203±0.093,优于ALNS的5.349±0.038和神经网络方法的5.208±0.124,平均提升2.73%,且仅比最优神经网络低0.10%。每种子实验中,强化学习调度器均不低于ALNS表现,且在三个种子中有两个超过神经网络。对完工时间的分解显示各算法在卡车等待时间上的权衡,所学调度器有效平衡二者以最小化总完成时间。提供配置优先实现方案,包含绘图与显著性检验工具,便于复现。

原文摘要 · Abstract (English)

We study last-mile delivery with one truck and one drone under explicit battery management: the drone flies at twice the truck speed; each sortie must satisfy an endurance budget; after every delivery the drone recharges on the truck before the next launch. We introduce a hybrid reinforcement learning (RL) solver that couples an ALNS-based truck tour (with 2/3-opt and Or-opt) with a small pointer/attention policy that schedules drone sorties. The policy decodes launch-serve-rendezvous triplets with hard feasibility masks for endurance and post-delivery recharge; a fast, exact timeline simulator enforces launch/recovery handling and computes the true makespan used by masked greedy/beam decoding. On Euclidean instances with $N{=}50$, $E{=}0.7$, and $R{=}0.1$, the method achieves an average makespan of \textbf{5.203}$\pm$0.093, versus \textbf{5.349}$\pm$0.038 for ALNS and \textbf{5.208}$\pm$0.124 for NN -- i.e., \textbf{2.73\%} better than ALNS on average and within \textbf{0.10\%} of NN. Per-seed, the RL scheduler never underperforms ALNS on the same instance and ties or beats NN on two of three seeds. A decomposition of the makespan shows the expected truck-wait trade-off across heuristics; the learned scheduler balances both to minimize the total completion time. We provide a config-first implementation with plotting and significance-test utilities to support replication.

物流优化强化学习无人机配送可复现

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。