精读笔记

Problem Setting

论文《Efficient Routing for Multitruck Multidrone Package Delivery With Precedence Constraints》（IEEE Transactions on Robotics / 2025）实际处理的是一个带偏序约束的 multitruck–multidrone delivery routing/scheduling 问题。关键不只是“多车 + 多机 + 先后顺序”，而是 precedence 会改变 truck–drone 协同的时间结构：一个 drone sortie 在几何上可行，不代表在 schedule 上可行，因为 customer 的服务时间可能被跨车辆 predecessor 推迟，进而让 drone 在空中等待并消耗 endurance。

以前 truck–drone routing 方法主要卡在它们通常把 drone sortie 当作局部并行化选择：给定 truck path，找可行 release、service、retrieve 即可。但这里 service time 不再只是 arrival time，而是 max(arrival, predecessor completion)。这使得 endurance feasibility 不再是局部距离约束，而变成全局偏序传播后的时间约束。另一方面，传统 precedence-constrained MRTA 通常每个 task 被一个 robot 访问一次，缺少 truck–drone rendezvous 这种“同一 location 可能同时是服务点、释放点、回收点”的结构。

这个任务的核心矛盾是：要利用 drone 的并行性减少 makespan，但 precedence constraints 会引入等待，等待又可能抵消并行性甚至破坏 endurance。好的算法必须同时避免 hybrid route 空间的组合爆炸，以及避免把 precedence 处理成事后简单过滤。

Motivation

作者的动机不是提出一个更复杂的 exact formulation，而是找到一个可搜索的表示。直接在 hybrid truck–drone solution 上做 ALNS/VNS，需要同时维护四件事：customer assignment、truck order、drone release/retrieve、precedence-feasible schedule。任何 destroy/repair 都可能破坏 endurance 或偏序约束，导致修复代价高、搜索噪声大。

作者的核心观察是：truck-only route 可以作为一种“服务顺序骨架”。只要这个骨架本身尊重 precedence，那么 drone 的作用可以被看作在骨架上的局部 shortcut/parallelization。这样做不保证覆盖所有优解，但能把最难维护的全局偏序可行性放在 route order 层处理，把 drone dispatch 放在 decoder 层处理。

因此，关键缺口是缺一个面向 precedence-constrained truck–drone routing 的中间表示：既比纯 truck route 丰富，能诱导 drone 并行；又比完整 hybrid route 简单，便于做可行性检查和邻域搜索。ESD 的设计基本就是围绕这个表示展开。

Core Idea

论文真正的核心思想是把问题重参数化为“precedence-feasible truck-only routes + deterministic truck–drone splitting”。搜索不直接发生在 hybrid route 空间，而发生在 truck-only route 空间；每次得到一个 truck-only 骨架后，再用 splitting 自动决定哪些 customer 由 drone 服务、release/retrieve 放在哪里，并用 endurance checking 处理 precedence wait 造成的额外飞行时间。

这个机制理论上/直觉上有效，是因为 truck-only route 同时承担两种角色：一是给多 truck 分配客户并确定偏序兼容的服务骨架；二是给 drone dispatch 提供有序候选区间。这样 precedence checking 可以转化为在原 DAG 上加入 route-adjacent directed edges 后检测 cycle，而不是在完整 schedule 空间里反复求复杂可行性。

和 prior 的本质区别在于，它不是“在 ALNS 中加入 precedence repair”，而是换了搜索空间。prior hybrid-route perturbation 的每一步都可能破坏复杂结构；ESD 则让扰动只发生在 truck-only sequence 上，drone 部分由 splitting decoder 重新生成。这是一种典型的 representation/inductive-bias gain，而不是单纯算子更强。

Method

方法中最关键的是三类机制，而不是三阶段本身。

1）EMA 生成 truck-only 骨架。它解决的是：在存在偏序约束时，怎样快速得到一个 makespan 不太差的多 truck customer order。EMA 通过 topological feasible set 保证只插入当前可服务客户，同时用 timestamp 更新传播 predecessor completion time。marginal cost 不是纯距离，而是插入后最后服务时间的变化，因此它把 precedence-induced waiting 纳入路线构造。

2）Splitting 作为 hybrid decoder。它解决的是：给定 truck order 后，如何在不改变该 order 的情况下用 drone 提供并行服务。其核心变化是把 release、drone customer、retrieve 限定在 route order 的三元组上，使 drone assignment 变成沿序列的动态规划/最短路式选择。这降低了搜索自由度，但让问题可控。

3）Endurance check 是对 precedence 的 schedule-level 修正。普通 splitting 只知道飞行距离/时间，不知道某个 drone-served customer 是否因 predecessor 未完成而延迟服务。该 check 反复更新时间戳，一旦发现某个 sortie 的实际空中时间超过 T，就取消该 drone dispatch，把客户退回 truck。它本质上是 feasibility repair，而不是全局优化。

4）VND 只扰动 truck-only routes。IR、IS、IIR 的价值不在算子本身多新，而在于每次扰动后都重新运行 hybrid decoder。尤其 IIR 能跨 route 改变客户归属和局部顺序，因此更可能改变 makespan bottleneck。precedence check 通过给 route 相邻节点加边并检测 cycle，提供了一个简洁的 feasibility oracle。

Key Insight / Why It Works

最重要的 insight 是：在这个问题里，直接搜索完整 truck–drone schedule 太复杂，而 truck-only route 是一个足够强的 latent structure。它把“全局偏序一致性”和“局部 drone 并行化”解耦。ESD 的有效性主要来自这种更好的 inductive bias，而不是来自某个单独 heuristic 的神奇性能。

为什么它能比 ALNS 快：ALNS 在 hybrid space 中 destroy/repair，会频繁产生需要修复的 infeasible structure；ESD 每次只在 truck-only order 上移动客户，precedence feasibility 用 DAG cycle check 很快判断，drone assignment 由 splitting 重新生成。这相当于把复杂的 repair burden 转移给一个 deterministic decoder，减少了无效搜索。

为什么它能有不错解质量：EMA 初始解已经把 precedence waiting 和多 truck makespan 平衡考虑进去；VND 再通过 truck-only perturbation 改变骨架；splitting 在每个骨架下尽可能提取 drone 并行收益。也就是说，算法并非先粗糙分配再小修，而是在“骨架质量”和“并行化收益”之间反复重新对齐。

最可能的核心贡献是 truck-only perturbation + re-splitting 这个搜索组织方式，以及面向跨 route precedence 的 cycle-based feasibility check。EMA、splitting、VND 各自都不是全新思想，更像已有技术的结构化重组。endurance checking 是必要补丁，但其修复策略偏保守。

这不是 scaling-driven 方法，也不是 learning/data coverage 方法；它更接近 classical combinatorial optimization 中的 better representation + handcrafted decoder。增益主要来自搜索空间设计。部分实验优势也可能来自 baseline 在该 representation 上不占优，而不是 ESD 已经逼近全局最优。

Relation To Prior Work

最接近的路线有三条：FSTSP/VRPD 中的 truck-first drone-second splitting 方法，precedence-constrained MRTA 中的 topological insertion/auction 方法，以及 ALNS/VNS 类 large-neighborhood routing heuristic。ESD 本质上是这三条线的组合，但组合点比较关键。

相对 FSTSP/VRPD splitting，新增问题是 precedence-induced waiting 会破坏原本局部 endurance 判断。论文的 endurance check 正是针对这个 gap。相对 precedence-constrained MRTA，新增结构是 customer 可以成为 release/retrieve 点，truck 和 drone 可能共同访问同一节点；因此不能简单把客户分给某个 robot 后排序。

相对 ALNS，真正差异不是局部搜索算子，而是搜索表示。ALNS 通常在完整解上破坏/修复；ESD 在 truck-only latent space 中扰动，再用 splitting decoder 生成完整解。这个设计降低了解结构维护成本。

看似新的部分中，EMA、splitting、VND 都有明显 prior lineage；实质创新在于把这些模块组织成适合 precedence-constrained multitruck–multidrone 的 pipeline，并提出跨 route precedence feasibility 的 cycle-check 方式。它属于 classical heuristic optimization 谱系中的 decomposition + decoder-based local search，而不是新的优化范式。

Dataset / Evaluation

评估覆盖随机数据、LaDe 真实城市配送数据和小规模真实 robot/drone 实验。这个组合基本能支撑“该方法在多种实例上比常用 ALNS 和若干三阶段 baseline 更高效”这一 claim。随机数据区分 sparse/dense precedence，有助于观察偏序约束密度对可行空间和等待的影响；LaDe 提供真实地理分布，但 precedence 是由 time-window end time 转换而来，和真实优先级/业务约束是否等价文中未充分说明。

实验最有说服力的点是：ESD 在中等规模实例上通常用远少于 ALNS 的时间得到更好 makespan，说明 representation-level search 确实有效。消融也支持 IIR relocation 是主要改进来源，IR/IS 更像辅助收敛。

但 evaluation 没有充分验证最优性 gap。没有 exact solver 小规模对照，也没有系统展示在极端 precedence graph、不同 drone speed/endurance ratio、不同 customer spatial clustering 下的退化行为。ALNS 固定 300s，且经过作者加入 endurance/precedence repair，baseline 调优公平性仍不完全清楚。真机实验规模小，更多证明 pipeline 可执行，而不是证明真实部署鲁棒性。

Limitation

最核心限制是 expressivity：ESD 搜索的是能由 truck-only route 诱导出的 hybrid solutions。这个 representation 很强，但也会排除一些潜在更优结构，尤其是需要更自由 rendezvous、非 customer rendezvous、多 drone overlapping dispatch 或更复杂 sortie chaining 的场景。

第二，endurance repair 过于单向。发现 sortie 因等待超时后直接取消，而不是尝试调整 release/retrieve 或重新分配 drone customer。这保证快，但可能损失大量并行收益。也就是说，方法把一部分难度从搜索转移到了 decoder 的保守性上。

第三，假设偏理想化：忽略服务时间、装卸/换电时间，确定性速度，一架 truck 一架 drone，drone 单包单客户，release/retrieve 只能在 customer/depot，不允许 drone loop。这些假设让模型干净，但真实系统中很多时间项会改变 precedence waiting 和 endurance feasibility。

第四，scalability 上限仍不明确。虽然实际实验快，理论复杂度到 O(N n^7)，且 VND 枚举邻域会随规模快速膨胀。大规模城市级实例、多 depot、多 time windows、多 drone per truck 时是否仍可用，文中未充分说明。

第五，增益归因不完全清楚。ESD 同时换了初始解构造、hybrid decoder、VND 搜索空间和 feasibility check；虽然有一些 ablation，但不足以完全分离“好初始解”“好 representation”“更强邻域”“baseline 不适配 precedence”的贡献。

Takeaway

• 1）对复杂 robot routing/scheduling 问题，直接在完整解空间搜索未必最好；找到一个能保留主要结构、又便于 feasibility checking 的 latent route representation，往往比设计更复杂 destroy/repair 更有效。
• 2）truck-only route 在 truck–drone delivery 中可以作为强 inductive bias：它提供全局服务骨架，drone 负责局部并行化。
• 这一思想可迁移到其他 heterogeneous routing 问题，例如 ground robot + UAV inspection、mobile manipulator + helper drone 等。
• 3）precedence constraints 不应只作为 route-level ordering constraint 处理；在多机器人异步系统中，它会通过 waiting time 影响 resource feasibility。

一句话总结

这篇论文在 precedence-constrained multitruck–multidrone delivery 中的主要贡献，是把 hybrid route 搜索重构为 precedence-feasible truck-only 骨架上的 decoder-based local search，属于经典启发式优化中通过更好表示和可行性 oracle 获得效率增益的方法演化。