Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows

该论文提出了一种针对带时间窗旅行商问题（TSPTW）的高效精确算法，证明了经典基准实例因结构可被利用而不再具备代表性，无法有效评估算法性能或作为机器学习训练集。

要点

这篇文章就像是一个**“作弊码”的发现者**，他在告诉整个计算机科学界：

“嘿，大家别再拿那些老掉牙的‘经典考题’来测试你们的新算法了！这些题目其实有个巨大的漏洞，只要用一种极其简单的方法就能秒杀。如果你们只在这些题目上表现好，那可能只是因为你们‘猜’对了出题人的套路，而不是真的变聪明了。”

下面我用几个生活中的比喻来拆解这篇论文的核心内容：

1. 背景：什么是“带时间窗的旅行商问题”？

想象你是一个外卖骑手（或者快递员）。

• 你有n 个客户要送。
• 每个客户都有一个**“收货时间窗”**：比如张三只能在 9:00-9:30 之间收货，李四只能在 10:00-10:15 之间收货。
• 你不能迟到（否则客户投诉），但可以早到（在门口等）。
• 你的目标是规划一条路线，要么最早送完所有货回家（这叫“完工时间”目标），要么在路上花的总时间最短（这叫“时长”目标）。

过去几十年，科学家们为了测试谁的外卖路线规划得最好，一直用一套**“经典题库”**（Benchmark Instances）。大家觉得，只要在这些题上跑得快，你的算法就是最强的。

2. 核心发现：这套“经典题库”其实是个“纸老虎”

作者 Francisco Soulignac 发现，这套经典题库里，凡是客户数量超过 50 个的题目，其实非常容易解。

他写了一个超级简单的算法（就像是一个只会“倒着走”的笨办法）：

• 普通算法：像是一个勤奋的探险家，从起点出发，尝试所有可能的路，遇到死胡同就回头，非常耗时。
• 作者的算法：像是一个**“倒着走的侦探”。他从终点（家）开始，倒着往回找路。他有一个绝招：“只要前面能早点到家，我就优先选那条路；如果前面太堵了，我就直接放弃那条路。”**

结果令人震惊：

• 这个“笨办法”在10 秒钟内就能解开所有 50 个以上客户的经典难题。
• 而以前那些号称“世界顶尖”的复杂算法，跑这些题可能需要几分钟甚至几小时。

3. 为什么会出现这种情况？（比喻：出题人的“套路”）

这就好比出题人（生成这些题目的科学家）在出题时，无意中给题目加了“作弊提示”。

• 出题逻辑：这些经典题目在生成时，时间窗（比如 9:00-9:30）通常是很紧的，而且是根据一条“大概的路线”生成的。
• 作者的发现：这种“紧时间窗”加上“特定生成方式”，导致这些题目在数学结构上非常规整。就像是一个迷宫，虽然看起来墙很多，但其实只有一条路是通的，其他路都是死胡同。
• 作者的算法：正好擅长识别这种“死胡同”，它像一把万能钥匙，专门能打开这种特定结构的锁。
• 其他算法：很多复杂的算法（包括机器学习算法）是在这些题目上训练出来的。它们可能**过度拟合（Overfitting）**了，就像学生死记硬背了这几道经典题的答案，一旦换个稍微难一点的题目（比如时间窗很宽、很乱的题目），它们就傻眼了。

4. 实验对比：谁才是真英雄？

作者拿他的“笨办法”和其他几种“顶尖算法”在两类题目上 PK：

• 第一类：经典题库（老题目）

  • 结果：作者的“笨办法”大杀四方，秒杀对手。
  • 原因：对手被这些题目的“特殊结构”骗了，以为题目很难，其实很简单。

• 第二类：新题库（Rifki & Solnon 生成的题目，时间窗很宽、很乱）

  • 结果：作者的“笨办法”直接崩溃，解不开；而对手们虽然慢，但还能解出来。
  • 原因：新题目没有那种“死胡同”结构，时间窗很宽，允许你在路上随便晃悠。这时候，那种“倒着走”的简单逻辑就失效了，需要真正强大的搜索能力。

5. 结论与建议：别再自欺欺人了

这篇论文给学术界泼了一盆冷水，但也指明了方向：

1. 停止迷信老题库：如果只用那些 50 个以上客户的经典题目来评估算法，毫无意义。因为任何稍微带点“倒推”逻辑的简单算法都能拿满分。这会让人们误以为现在的算法已经无敌了。
2. 警惕机器学习：很多 AI 算法是用这些老题目训练的。如果只在这些题目上表现好，那它们可能只是学会了“走捷径”，并没有真正学会解决复杂的现实问题。
3. 未来的方向：我们需要更难的题目。比如让时间窗变得更宽、更随机（就像现实生活中的交通状况，有时候很堵，有时候很空，没有固定套路）。只有在这种“乱拳打死老师傅”的环境下，才能看出谁才是真正的外卖规划大师。

总结

这就好比考试。
以前的考题（经典题库）虽然看起来很难，但其实都有固定的解题套路。作者发现了一个**“秒杀套路”，只要用这个套路，所有老题都能秒过。
他提醒大家：“别因为大家都能秒杀老题，就以为现在的学生（算法）都变聪明了。我们要出一些没有套路的‘新题’，看看谁是真的有实力，谁只是会背答案。”**

一句话总结： 经典基准测试已经“烂”了，它们太容易被简单的技巧攻破，我们需要更真实、更混乱的难题来真正检验算法的成色。

技术摘要

论文技术总结：警惕旅行商问题时间窗（TSPTW）的经典基准实例

1. 研究背景与问题定义

问题定义：
本文研究的是带有时间窗的旅行商问题（TSPTW）。在该问题中，一辆车必须访问一组客户，且每个客户必须在预定义的时间窗口 $[a(v), b(v)]$ 内被访问。车辆可以提前到达并等待，但不能迟到。车辆从 depot（起点/终点）出发，访问所有客户后返回 depot。

目标函数变体：
文章主要关注以下三种变体：

1. TSPTW-M (Makespan)：最小化路线完成时间（即车辆返回 depot 的时间）。
2. TSPTW-D (Duration)：最小化路线总时长（即从出发到返回 depot 的总时间，包含等待时间）。
3. TSPTW-TT (Travel Time)：最小化纯行驶时间（不包含等待时间）。

核心问题：
目前，大多数 TSPTW 算法（包括精确算法和机器学习方法）的性能评估主要依赖于由 López-Ibáñez 和 Blum (2023) 编译的经典基准实例集（包含 50 个或更多客户的实例）。作者指出，这些实例集的结构存在特定偏差，导致它们不再能代表真实的挑战，甚至可能误导对算法效率的评估。

2. 方法论：简单精确求解器

作者提出了一种简单但高效的**后向最佳优先搜索（Backward Best-First Search）**算法，专门用于解决 TSPTW-M，并作为预处理步骤辅助解决 TSPTW-D。

2.1 核心算法 (Algorithm 1 & 2)

• 搜索方向：算法采用后向搜索策略。从终点 depot ($n+1$) 开始，逆向构建路径（即 $\langle w \rangle + R$），优先处理那些能更早到达终点 depot 的部分路径。
• 启发式策略：
  • 在每一步，算法选择能够最大化“可节省时间”（$ub - \delta_m(R)$）的部分路径进行扩展。
  • 在平局时，优先选择能最大化最早出发时间（$\delta^{-1}(R, \delta_m(R))$）的路径，以便在之前的客户处有更大的等待灵活性。
• 剪枝策略：
  • 不可达性剪枝 (Unreachable Function)：预先计算不可达顶点集合 $U(w, t)$。如果某个顶点 $w$ 在时间 $t$ 之前无法被访问，则包含该顶点的路径被剪枝。
  • 支配剪枝 (Dominance)：如果存在另一条部分路径 $Q$，其访问的顶点集与 $R$ 相同，且 $Q$ 能比 $R$ 更早到达终点或更晚出发，则 $R$ 被 $Q$ 支配，从而被丢弃。
• 求解流程：
  • 对于 TSPTW-M：通过不断降低上界 $ub$ 并运行决策算法（Algorithm 1），直到找到最优解。
  • 对于 TSPTW-D：利用滑动窗口策略（Algorithm 3），在整数时间范围内多次调用 TSPTW-M 求解器，寻找最小化 $\delta(R, t) - t$ 的解。

2.2 实现细节

• 使用标签（Label）存储路径信息（访问顶点集、最早到达时间、最晚出发时间等）。
• 使用优先队列管理待处理的路径。
• 使用哈希表存储支配关系，避免重复扩展被支配的路径。

3. 关键贡献

1. 揭示了经典基准的局限性：

   • 作者提出的简单算法能在10 秒内解决所有包含 50 个或更多客户的经典基准实例（TSPTW-M）。
   • 作为“即插即用”方法，该算法也能在 30 分钟内解决除一个实例外的所有经典基准实例（TSPTW-D）。
   • 结论：这些经典实例（如 Lan, Dum, Gen, Ohl, DaS 等）由于时间窗生成方式的特定结构（通常基于某条初始路径的邻域生成，导致时间窗较紧且结构单一），对现代精确算法而言过于简单，已不再适合作为唯一的评估标准。

2. 指出了机器学习训练数据的偏差：

   • 许多机器学习方法（如强化学习）使用与经典基准相似的生成过程来创建“困难”训练集。
   • 由于这些生成过程倾向于产生结构化的、时间窗较紧的实例，导致训练出的模型可能过拟合，无法处理时间窗更宽松（Loose）或结构更复杂的真实场景。

3. 算法的局限性分析：

   • 该简单算法在时间窗宽松（Loose time windows）的实例上表现极差，甚至无法解决 30-40 个客户的实例（如 Fontaine (2024) 提出的基准集 Rif）。
   • 这反证了经典基准之所以“容易”，是因为它们的时间窗相对较紧，限制了搜索空间，而非因为算法本身有多强大。

4. 实验结果

作者将提出的算法（Algorithm 2 和 3）与当前最先进的方法（Ler22, Rud23, Fon24）在多个基准集上进行了对比：

• 经典基准集 (Asc, Dum, Gen, Lan, Ohl, DaS)：

  • 提出的算法在 50+ 客户的实例上表现极其出色，平均耗时仅几秒，且解决了之前未解决的 4 个实例（TSPTW-M）和 14 个实例（TSPTW-D）。
  • 相比之下，其他先进算法在这些实例上耗时更长，甚至无法在 1 小时内解决部分实例。
  • 异常现象：该算法在客户数较少（<50）的某些实例上反而表现不佳（内存溢出或超时），这进一步证明了其优势依赖于特定实例结构（大 N 且时间窗紧）。

• 困难基准集 (Rif, Fontaine 2024)：

  • 在时间窗较宽松（$\beta$ 值较小）的 Rif 基准集上，该算法表现最差，甚至无法解决 30-40 个客户的实例。
  • 相比之下，Ler22（专为困难时间窗设计）在这些实例上表现稳健。

• 结论：

  • 经典基准集（Lan, Dum, Gen 等）由于生成机制（基于第二近邻路径生成时间窗），导致时间窗相对较紧，搜索空间小，结构单一。
  • 这种结构被作者的简单后向搜索算法充分利用，从而产生了“看似卓越”的结果。

5. 意义与建议

1. 基准测试的革新：

   • 不再应单独使用包含 50+ 客户的经典基准集来评估 TSPTW 算法。
   • 未来的基准测试应包含时间窗更宽松的实例（如 Fontaine (2024) 和 Rifki et al. (2020) 提出的变体），以真正测试算法的鲁棒性。

2. 对机器学习研究的警示：

   • 设计用于训练机器学习算法的“困难”数据集时，必须谨慎。如果数据集生成过程沿用了经典基准的偏差（如基于固定路径生成时间窗），训练出的模型可能无法泛化到真实世界中时间窗更宽松或更复杂的场景。
   • 建议引入时间窗紧密度参数（如 $\beta$）来生成不同难度的数据集，以覆盖从“易”到“难”的完整谱系。

3. 对真实世界的反思：

   • 虽然宽松时间窗的实例更难求解，但作者也指出，现实世界（如在线堆垛机调度）中往往需要紧密的时间窗以保证任务及时完成。因此，经典基准是否完全“过时”仍有待商榷，但它们确实不足以代表所有挑战。
   • 作者建议将此类简单算法作为预处理步骤，用于过滤掉容易的实例，从而让更复杂的算法专注于处理真正的难点。

总结：这篇论文通过展示一个简单算法在经典基准上的“统治级”表现，有力地证明了这些基准实例已失去区分度，呼吁社区转向更具挑战性（特别是时间窗更宽松）的基准集，以避免算法评估和机器学习训练中的偏差。