Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints

想象一下你是一名物流车队的队长，任务是将数百个包裹送到繁华的城市中。你有一张地图、一份客户名单，以及一套严格的规则：你的卡车载重有限，而且有些客户只要求在上午 9:00 到 11:00 之间送达。你的目标很简单：拜访所有人，遵守规则，并尽可能减少时间和燃料的消耗。这就是“车辆路径问题”（Vehicle Routing Problem），一个让物流公司和数学家们忙碌了几十年的经典谜题。

多年来，科学家们一直尝试用两种主要工具来解决这个问题。第一种是“完美计算器”，这种方法试图检查每一个可能的路径，以找到绝对最优的一条。这就像是在一个巨大的自助餐厅里品尝每一道菜，只为找到那一口完美的滋味。如果餐点很小，它效果很好；但如果自助餐变得规模宏大，你可能在吃完之前就会饿死。第二种工具是“聪明猜测”，即启发式算法（heuristic）。这就像是一位对厨房了如指掌的老练厨师；他们不会检查每一道菜，而是利用经验和快速技巧来找到一顿美味的饭菜。最近，一个新的竞争者加入了赛场：“深度学习”。把它想象成一个观察了成千上万个烹饪视频的机器人厨师，它通过观察学习模式，然后尝试瞬间猜出最佳路线，并且随着练习的增加变得越来越好。

这篇名为《智能路线》（Smart Routes）的论文，是这三位厨师之间的一场巅峰对决。作者构建了一个全新的数字游乐场——“智能路线”，来公平地测试他们。他们不仅仅研究了小型、简单的谜题；他们还在 50 个和 100 个停靠点的规模上测试了这些算法，这相当于从一个小社区扩展到了整个城市。他们想看看谁能在不违反游戏规则的前提下，最快地找到一条好的路线。

大赛：完美 vs. 快速 vs. 智能

研究人员使用他们全新的“智能路线”平台组织了一场比赛。这个平台就像一个通用的测试场，你可以接入任何算法——无论是经典的数学技巧、强大的计算机求解器，还是学习型机器人——并观察它们的运行情况。他们测试了三种主要的竞争者：

1. 精确求解器 (SCIP)： 这个“完美计算器”承诺提供最好的答案，但需要很长时间。
2. 经典启发式算法 (LKH, 2-OPT, 3-OPT, OR-Tools)： 这些是“聪明猜测者”，它们利用巧妙的捷径来快速找到优秀的答案。
3. 深度学习模型 (JAMPR)： 这是经过训练、能够学习模式并做出快速、高质量猜测的“机器人厨师”。

他们在两种类型的挑战中运行了这些竞争者：一个拥有 50 个配送点的较小城市，以及一个拥有 100 个配送点的大型城市。他们给了“完美计算器”巨大的时间优势（在小城市中为 1,000 秒，在大城市中为 2,000 秒），因为它需要进行深度思考。其他选手得到的时间要少得多（分别仅为 100 秒和 200 秒）。

结果：速度获胜，但规模决定一切

50 站挑战赛（小城市）
在较小的城市中，比赛进行得非常激烈。“完美计算器”（SCIP）最终找到了绝对最佳的路线，但它花了很长时间才达到。与此同时，“聪明猜测者”和“机器人厨师”找到的路线几乎一样好——仅比完美路线差约 5%——但它们完成的速度要快得多。

• 启示： 对于较小规模的问题，你不需要等待完美答案。快速方法得到的结果已经足够接近完美，因为它们能为你节省数小时的等待时间。

100 站挑战赛（大城市）
当城市规模翻倍至 100 个站点时，游戏规则发生了剧变。“完美计算器”开始陷入困境。它寻找其第一个有效路径所需的时间，是其他方法之 13 倍。更糟糕的是，当它终于找到一条路径时，这条路径的成本（更长、更慢）比“机器人厨师”和“聪明猜测者”（如 OR-Tools）瞬间找到的路径高出约 50%。

• 启示： 随着城市规模扩大，“完美计算器”变得过于缓慢而无法投入实际使用。它花费了太多时间进行搜索，以至于无法在规定时间内找到一个好的方案。而“机器人厨师”（JAMPR）和先进的“聪明猜测者”（如 OR-Tools）依然保持着高效，并找到了高质量的路线，证明了对于大型问题，速度和聪明的猜测胜过对完美的追求。

结论

论文得出结论：虽然“完美计算器”非常适合处理小型谜题，但当问题变得太大时，它会撞到天花板。 “智能路线”平台表明，对于现实世界的大规模配送问题（如 100 个站点），依赖精确、完美的解决方案往往不是一个好主意，因为它们耗时太长，甚至无法保证在合理时间内获得极佳的结果。

相反，作者建议，将经典启发式算法（经验丰富的捷径）与深度学习（受过训练的机器人）相结合才是制胜策略。这些方法可以找到几乎与完美方案不相上下的路线，而且速度极快，使其在现实世界的物流中具有实用价值。“智能路线”系统本身也被强调为一个宝贵的工具，因为它让任何人都能轻松测试这些不同的方法，在地图上可视化路径，甚至可以在无需重建整个系统的情况下加入自己的新想法。

简而言之，如果你正在努力为一个不断增长的城市配送包裹，不要等待完美的计划。使用那些能从经验中学习的智能、快速的工具，因为在现实世界中，现在就找到一条好的路线，比下周才找到一条完美的路线更有意义。