精读笔记

Problem Setting

论文标题：Impact of Scaling and Rounding on Metaheuristic Performance for the Vehicle Routing Problem with Time Windows（arXiv preprint / 2026-06-09）。

这篇论文实际解决的是 VRPTW benchmark 的“实例语义漂移”问题：经典 Solomon / Homberger 欧氏实例天然产生浮点 travel time，但大量 solver 和竞赛流程为了速度、稳定性、可复现性把它们缩放并取整。问题是这个变换不是中性的。它不仅改变 arc cost 的数值精度，还改变 time-window feasibility、等待时间传播、局部搜索 move 的相对收益以及最终解能否映射回原始 float 实例。

真正困难点不是如何 round，而是如何判断一个 solver 的性能到底属于哪一个问题：整数化后的 IP，还是原始浮点实例 I。过去很多比较把这两者混在一起：DIMACS 使用 scaled/truncated convention，SINTEF BKS 又基于 float evaluation。于是同一个 solution 在整数空间可能是好解，在 float 原问题可能不可行；同一个 solver 的 ranking 也可能随 evaluation space 翻转。

关键矛盾是：低精度 / 乐观 rounding 往往让整数实例更容易优化，但它降低了对原问题的 fidelity；高精度 / 保守 rounding 保证 transfer，但可能让搜索空间更硬、更慢。这篇论文的价值就在于把这个 trade-off 明确化。

Motivation

已有路线不够的地方在于，VRPTW 社区长期把 scaling 和 rounding 视为文件格式或实现细节，而不是 benchmark definition 的一部分。对熟悉该领域的人来说，这其实很危险：time window constraint 对 travel-time perturbation 极其敏感，尤其是长 route 上误差会累积；一个边级别小于 1/P 的误差，经过路径选择和优化偏置后，不一定仍是无害噪声。

作者的核心观察是：整数化方案有方向性。floor travel time + 放宽 time window 不是“近似”，而是在构造外近似；ceil travel time + 收紧 time window 是内近似；nearest 虽然看起来最自然，但没有 feasibility guarantee，而且在欧氏整数坐标下 fractional part 分布本身可能有偏。这个观察把问题从 numerical precision 提升到了 feasible-region approximation。

关键缺口是缺少系统证据来说明 preprocessing choice 会不会足以改变 solver 结论。论文不是要证明某个 rounding 最优，而是要证明：如果不报告 rounding/scaling/evaluation space，VRPTW benchmark comparison 本身就可能不可解释。

Core Idea

核心思想是把整数化后的 VRPTW 实例 IP 看成原始浮点实例 I 的有偏 surrogate，并同时分析两个空间中的性能。pessimistic scheme 给出 inner approximation：任何 IP 可行解都能安全转回 I；optimistic scheme 给出 outer approximation：I 的可行解都保留在 IP 中，但 IP 可能包含大量 float-infeasible 解；nearest scheme 牺牲可行性单调性，换取平均数值失真较小的直觉目标。

这个建模改变了 preprocessing 的角色：rounding 不再是误差项，而是给搜索过程施加的 inductive bias。optimistic rounding 的 bias 是“放松约束、压低 travel cost”，因此更像在一个简化可行域上做 search；pessimistic rounding 的 bias 是“保守 margin”，因此更像 robust feasibility filter；nearest 的 bias 则是看似无偏但实际受距离分布与优化选择共同驱动的 cost underestimation。

与 prior 的本质区别不是提出新的 VRPTW solver，而是重新定义了评测问题：solver performance 必须分成 integer-internal convergence 和 float-grounded benchmark fidelity 两个维度。这个拆分解释了为什么一些配置在 solver 内部看起来非常强，但在原 benchmark 上没有可比性。

Method

方法的关键机制只有三件。

第一，构造三种 rounding scheme 的可行域语义。pessimistic 通过 travel/service ceil、time-window 内收缩，解决的是 transfer safety；它牺牲原问题中一部分边界可行解，换取 IP feasible ⇒ I feasible。optimistic 通过 travel/service floor、time-window 外扩张，解决的是保留原可行解和简化搜索；它带来的核心变化是扩大可行域，因此 integer objective 更容易优化，但 transfer 不安全。nearest 解决的是平均数值失真，而不是约束安全；它的核心变化是去掉方向性保证，把风险转移给后验 float feasibility check。

第二，区分 scaled-back integer cost 与 true float cost。论文显式把 IP 上的整数代价除以 P 得到 scaled-back cost，但对 optimistic/nearest 的解必须重新在 I 上检查 time-window feasibility；不可行则在 float-grounded evaluation 中视为无效。这一步很关键，因为否则会把 surrogate objective 上的收益误认为原问题收益。

第三，用 trajectory-level metric 而非只看 final solution。AUC/primal-integral 风格指标让论文能观察 convergence path：某些配置可能早期快速下降，但最终大多不可转移；某些配置收敛慢但始终可行。这个设计比单点 final gap 更适合暴露 rounding 对 landscape 的影响。

solver 选择上，HGS 和 OR-Tools 只是探针，不是方法贡献。它们用于检验机制是否跨不同 metaheuristic architecture 仍成立。

Key Insight / Why It Works

最重要 insight 是：rounding 的主要影响不是“目标值有一点误差”，而是“搜索器被引导到不同的可行域边界”。VRPTW 的 time-window feasibility 是累积型约束，route 上早期 travel-time 的微小低估会沿到达时间传播；optimistic rounding 系统性创造 slack，solver 会自然利用这些 slack 去减少 route count 或 travel cost。一旦回到 float 原实例，这些 slack 消失，解就可能失效。

因此 optimistic/P=1 在 integer-internal AUC 上强，并不说明 solver 找到了更好的 VRPTW structure，而更可能说明它在一个更松、更粗、更容易的 surrogate problem 上优化得快。这里的收益本质上主要来自 scaling / landscape simplification，不是算法能力提升。反过来，pessimistic 或 P≥1000 在 float-grounded metric 上强，也不是因为它更会优化，而是因为它减少了 surrogate-original mismatch。

nearest rounding 的分析是论文里比较有迁移价值的部分。通常大家会默认 nearest 是低偏差选择，但文中显示欧氏整数坐标下距离小数部分并不均匀，低 P 时更常落在向下取整区域；更关键的是 optimizer’s curse：solver 会偏好那些在 rounded metric 下被低估的 edges/routes，于是原本 edge-level 的小偏差被 search selection 放大。这个机制在很多 combinatorial optimization surrogate 中都存在：只要优化器能选择误差项，误差就不会保持零均值。

最可能的核心贡献是“evaluation-dependent ranking inversion”的机制化证明。它清楚说明 benchmark conclusion 不是 solver-only property，而是 solver × instance transformation × evaluation space 的交互产物。辅助部分是具体统计检验和两个 solver 的实证覆盖；这些增强可信度，但不是本质创新。

需要直接判断的是：论文中所谓 performance improvement 的一部分明显不是求解器改进，而是问题被改写后的 easier instance effect。若未来论文用低精度 optimistic rounding 报告更快 convergence，却拿 float BKS 作暗含参照，这种比较应被视为 evaluation bias。

Relation To Prior Work

最接近的 prior 不是新的 VRPTW metaheuristic，而是 benchmark convention、DIMACS VRPTW track、SINTEF BKS 以及整数化建模实践。论文站在这些 convention 的缝隙里：DIMACS 的 scaled truncated/optimistic 风格强调整数空间可操作性，SINTEF 传统强调 float Euclidean evaluation；两者长期并存但语义不同。

和常规 HGS/OR-Tools 性能论文的本质差异是，它不问哪个 solver 更强，而问 solver 被喂进去的 instance 是否还是同一个 optimization problem。HGS 和 OR-Tools 在这里不是被改进对象，而是用于暴露 preprocessing sensitivity 的仪器。

看似新的三类 rounding，其实从 robust/relaxed approximation 角度并不新：inner/outer approximation 是优化里很传统的思想。实质创新在于把它严肃应用到 VRPTW benchmark scaling，并把 feasibility transfer、cost distortion、convergence ranking 放到同一个实验框架中。尤其是 nearest bias + optimizer’s curse 的拆解，比单纯说 rounding matters 更有信息量。

技术谱系上，这篇更像 optimization benchmarking methodology / numerical reproducibility paper，而不是 algorithmic VRPTW paper。它新增的信息是：预处理 convention 可以强到改变 metaheuristic ranking。

Dataset / Evaluation

评估覆盖经典 Solomon 100 客户和 Homberger 600/1000 客户实例，包含 R/C/RC topology，基本能代表 VRPTW 文献中最常用的欧氏 benchmark 场景。选择 HGS 和 OR-Tools 也合理：一个是高性能 VRP metaheuristic 体系，一个是广泛工业/工程使用的 CP/local-search 工具链；二者差异足以说明现象不是单一实现偶然。

实验最支持的 claim 是：scaling/rounding 会显著影响 feasibility transfer、cost estimation 和评价排序。尤其是同时报告 integer-internal AUC 与 float-grounded AUC，使 ranking inversion 很难被解释为普通噪声。

但 evaluation 仍是离线 benchmark 语境。它没有覆盖真实 road-network travel time、非欧氏 asymmetric metric、动态时间、stochastic travel time 或工业软约束。对这些场景，fractional-part bias 和 feasibility transfer 的具体方向可能不同。论文也没有充分隔离 solver 内部机制：例如 OR-Tools 的 guided local search、HGS 的 fleet-size stage、不同 neighborhood 对 rounding perturbation 的敏感性可能不同。换言之，claim 对“经典欧氏 VRPTW benchmark”很强，对“VRPTW deployment”则不能直接外推。

另外，使用实验中找到的 IP BKS 作为 integer gap reference 是可接受的 benchmarking 做法，但它让 integer-internal metric 更像相对内部效率指标，而非绝对 optimality 证明。这个限制不伤害主结论，但要避免过度解读。

Limitation

这篇论文成立依赖几个前提。

第一，实例是欧氏坐标生成 travel time，且坐标/距离分布具有特定小数部分结构。nearest 的系统性低估在这里被证明得很好，但在真实路网、非整数坐标、预估交通时间矩阵中未必同方向成立。

第二，结论强依赖 time-window feasibility 的硬约束语义。如果实际应用允许软时间窗、惩罚迟到或实时修复，那么 optimistic rounding 的不可转移性可能会表现为 penalty increase 而不是 infeasibility collapse。

第三，solver-specific attribution 不够彻底。文中显示 HGS 和 OR-Tools 都有 ranking inversion，但没有深入解释哪些 neighborhood、repair、penalty adaptation 或 construction heuristic 对 rounding 更敏感。增益来源不清的部分主要在 convergence acceleration：它可能来自更粗成本导致更多 ties、更大可行域、约束传播更松、route count 更容易下降，或 solver 内部整数运算更稳定；论文没有完全拆开。

第四，pessimistic scheme 的安全性也有代价：它可能删除原问题中真实最优附近的 tight feasible routes，因此在低 P 下不只是 conservative evaluation，而是在解一个可能过紧的 robustified problem。它保证 IP feasible ⇒ I feasible，但不保证 IP optimal 接近 I optimal。

第五，scaling 上限没有从计算复杂度和工程实现角度充分讨论。P 越大 fidelity 越好，但整数值范围、solver 内部 cost scaling、penalty λP、local-search delta 计算和缓存行为都可能受影响。文中趋势显示 P≥1000 足够好，但这更像经验建议，不是理论界限。

最后，这篇论文没有解决 benchmark convention 的最终标准化问题，只是明确指出现有 convention 不可混用。它把问题从“如何取整”推进到“必须声明评价空间”，但还没有给出一个社区层面的统一协议。

Takeaway

• 1. VRPTW 中 scaling/rounding 应被视为 instance definition，而不是 preprocessing。
• 任何不报告 P、rounding scheme、evaluation space 的结果都不完全可复现，也不应直接与 float BKS 比较。
• 2. optimistic low-precision rounding 的优势主要是 surrogate problem 更容易，不是 solver 更强。
• 它适合比较整数空间内部收敛，但不适合声称原始 float benchmark 上更优。

一句话总结

这篇论文是 VRPTW benchmark 方法论中的一次必要纠偏：它证明 scaling 和 rounding 会把同一实例变成不同优化问题，并能直接反转 metaheuristic 的性能排序。