精读笔记

Problem Setting

这篇论文处理的是 packing-constrained pickup-and-delivery 中的 feasibility verification bottleneck，而不是完整意义上的 routing optimization breakthrough。2P-PDP 的难点在于 onboard set 随 pickup/delivery 交错非单调变化，物品一旦放置后不能 relocation，同时每个装卸操作必须从 rear side 可达。这样一来，route feasibility 不是若干独立 2D packing feasibility 的并列，而是一组带共享物品位置一致性的动态 packing states。以前 2L-VRP 类方法主要假设 depot loading 或弱化 pickup-delivery coupling；即使 PDP packing 方法能检查可行性，也通常对每个 state 从头做 packing search。关键矛盾是：routing search 会生成大量候选路线，需要频繁验证 packing；但每次 exact packing check 都很贵，而这些 checks 之间又明显存在结构冗余。

Motivation

已有路线不够的地方不在于缺少 CP、tree search 或 heuristic packing procedure，而在于没有利用“已验证可行状态”本身作为证据。作者观察到 LNS/iterative routing 中的候选路线通常来自局部扰动，因此许多 SOPP 的物品集合、顺序关系和几何需求会相似；如果把历史 packing plan 当成 reference structure，就可能用 dominance 推出新 SOPP 可行。关键缺口是 PDP 的 no-relocation 约束使普通几何 dominance 不再 sound：一个小物品能塞进旧布局的某块空间，并不意味着它在 pickup 和 delivery 顺序下可装可卸。因此需要的是 sequence-aware dominance，而不是简单 cache 或 static bin-packing dominance。

Core Idea

论文真正的核心是把 feasibility check 从“每个 SOPP 独立求解一个 packing problem”改成“查询已有 feasible packing certificate 并尝试嵌入”。已验证 SOPP 的物品布局被解释成一组 reference bins；待验证 SOPP 的物品作为 pieces 被映射到这些 bins。只要这种映射同时保持 pickup reverse order 与 delivery order，并能产生同一个几何 packing realization，就可以继承旧状态的可行性。

这个建模改变很重要：它把 packing feasibility 的信息流从 solver-local 变成 search-global memory。prior work 的 feasibility oracle 是 stateless 的；本文的 oracle 是 stateful 的，会积累可复用结构。新的 inductive bias 是“route search 中出现的 hard packing states 有局部重复性/相似性”，因此用 dominance repository 做 test-time retrieval 可以比反复 CP 更 scalable。它不是让单次 packing 更容易，而是减少进入 exact packing 的次数。

Method

方法上最关键的不是 LNS，也不是 MOS heuristic，而是三件事。第一，SOPP/NDPA 选择把 route-level checking 限定在最受约束的 open-pickup states：如果 NDPA 的 onboard set 可行，前面的子集状态通常可由 restriction 继承；这解决了“检查哪些状态”的问题。第二，OPM 把 reference packing plan 转换成可搜索的 dominance certificate：monotone mapping 保证 sequence compatibility，in-bin packing 保证几何 containment，共同 packing realization 保证 pickup-side 与 delivery-side 不互相打架。第三，repository retrieval 与 hot-store sampling 是为了控制 dominance 本身的计算代价：descriptor filter 先用必要条件缩小候选，candidate cap 防止最坏情况爆炸，recency bias 利用 iterative search 的局部性。核心变化是 feasibility oracle 从 CP-only fallback 变成 heuristic → dominance inference → CP 的分层筛查。

Key Insight / Why It Works

最值得保留的 insight 是：packing-constrained routing 里的 repeated feasibility checks 可以被视为 certificate reuse 问题，而不是纯 solver acceleration 问题。真正有效的部分大概率是 memory reuse + representation alignment：历史 SOPP 的 layout 以 reference bins 形式对齐新 SOPP 的物品序列，OPM 则把几何空间和时间顺序压到同一个可检验结构里。

OPM 是核心贡献，因为它补上了普通 dominance 在 PDP 下不 sound 的缺口。只做几何 containment 会忽略 no-relocation；只做 pickup 或 delivery 单侧顺序又可能得到两个互不一致的 packing plan。要求两侧映射诱导 common realization，是本文 dominance relation 成立的关键。

SOPP checkpointing 是合理但更接近已有思想的再利用；descriptor retrieval、candidate cap、hot-store bias 基本是 engineering 层的 overhead control。hot-store 的效果说明增益相当依赖 routing search 的局部相关性，本质上更像 retrieval/cache 命中，而不是形成了更强的 packing reasoning。若 search trajectory 更发散，或 instance 分布让 SOPP 结构重复度低，dominance stage 可能只是增加 test-time compute。

因此这篇的有效性不是 scaling 本身，而是把 solver cost 转移到一个有 soundness guarantee 的 retrieval-inference layer。它的上限也在这里：只有当 repository 覆盖了未来 SOPP 的结构邻域时，dominance 才有价值。

Relation To Prior Work

最接近的路线有三类：2L-VRP/2D loading 中的 packing feasibility checking、PDP with 3D loading 的 checkpoint/tree-search 方法、以及更一般的 dominance/caching 在 combinatorial search 中的复用思想。和 2L-VRP 的本质差异是，本文处理的是 pickup/delivery 交错导致的非单调 onboard evolution，而不是 depot 一次装载后的卸货可达性。和 Männel & Bortfeldt 类 PDP packing 方法的差异是，它不把每个 checkpoint 当作独立 packing problem，而是显式复用历史 feasible states。

看似新的 SOPP 层级检查并不完全新，更多是把已有 checkpoint idea 放进 dominance framework。实质创新在 sequence-aware dominance relation：把 reference plan 的几何布局与 pickup/delivery 双序列兼容性绑定起来，并给出 sound inference 条件。技术谱系上，它属于 exact/heuristic routing algorithm 外挂的 stateful feasibility oracle，而不是新的 routing metaheuristic 或新的 packing solver。

Dataset / Evaluation

evaluation 基本验证了它作为 screening module 的局部 claim：在给定 LNS 框架、给定 2L-PDP benchmark、给定参数范围下，dominance stage 能减少 CP exact calls，并在多数设置降低 runtime，同时不改变目标值。这与论文定位一致，因为它本来就不是要提升 solution quality。

但实验覆盖面有限。实例规模是 25 requests，主要通过 item size、shape、trunk width scaling 做扰动；这能测试几何 tightness 的敏感性，但不等价于真实跨场景泛化。没有真实世界 deployment，也没有大规模、多车厢异质、3D/重量/fragility 等 richer operational constraints。benchmark 是否充分验证“generic framework embeddable in broad algorithms”也不够，因为实验只嵌入 LNS。机制分析说明 CP-stage reduction 与 runtime gain 相关，但仍未完全排除增益主要来自该 LNS 轨迹下的 SOPP 重复性。

Limitation

最大限制是 dominance inference 的命中率不是理论保证，而是分布性质：routing search 必须产生足够多可由历史 SOPP 覆盖的新 SOPP。若问题更稀疏、更随机、请求形状差异更大，或者 routing operator 产生的结构变化更剧烈，repository 可能很快膨胀但有效候选很少。

第二，方法把难度从 CP exact check 部分转移到 OPM search 与 repository management。OPM 虽有 pruning，但组合规模仍可能很高；descriptor filter 只是必要条件，不能保证候选质量。所谓 generality 也有边界：它依赖 rectangular orthogonal packing、rear accessibility、no-relocation 和可分解的 reference-bin interpretation。扩展到 3D、stacking、重心、fragility、多入口装卸时，dominance relation 很可能需要重写。

第三，实验增益归因仍有未充分说明的部分。hot-store bias 有显著收益，说明 locality/cache effect 很强；这也意味着所谓 inference 更像 trajectory-specific retrieval，而不是对 packing feasibility landscape 的普适建模。文中未充分说明 repository 在跨实例复用时是否仍有效，也未证明该机制能随 request size 扩展保持收益。

Takeaway

• 第一，packing-constrained routing 的一个重要方向不是继续加强单次 packing oracle，而是让 feasibility certificates 在 search 过程中可复用。
• 第二，PDP 场景下任何 dominance/reuse 都必须显式处理顺序约束；几何可嵌入本身不够。
• 第三，stateful feasibility oracle 是一个可迁移 insight：在很多 routing + resource feasibility 问题中，历史可行状态可以成为 test-time memory，而不是只作为日志。
• 第四，未来真正有价值的是让 dominance information 反向进入 route generation，主动生成 packing-compatible routes；仅作为后验筛查，收益上限受 repository 命中率限制。

一句话总结

这篇论文把 2P-PDP 的 packing feasibility verification 从 stateless exact checking 推进到有 soundness guarantee 的 dominance-based memory reuse，是一种面向 routing-packing 联合问题的 retrieval/inference 化 feasibility oracle，而不是新的 packing solver。