等待假期包裹送达?在送货卡车上门之前需要解决一个棘手的数学问题，麻省理工学院的研究人员有一个可以加速解决方案的策略。该方法适用于车辆路线问题，例如最后一英里交付，其目标是将货物从一个中央仓库运送到多个城市，同时降低旅行成本。虽然有设计用于解决数百个城市的这个问题的算法，但当应用于更大的城市集时，这些解决方案变得太慢。

为了解决这个问题，土木与环境工程和数据、系统和社会研究所的吉尔伯特 W.温斯洛职业发展助理教授 Cathy Wu 和她的学生提出了一种机器学习策略，可以加速一些最强大的算法求解器增加 10 到 100 次。

求解器算法的工作原理是将交付问题分解为更小的子问题来解决——例如，在 2,000 个城市之间路由车辆的 200 个子问题。Wu 和她的同事使用一种新的机器学习算法来增强这个过程，该算法识别最有用的子问题来解决，而不是解决所有的子问题，以提高解决方案的质量，同时使用更少的计算量。

研究人员说，他们称之为“学习委托”的方法可用于各种求解器和各种类似问题，包括仓库机器人的调度和寻路。

优化交付路线的智能物流平台 Routific 的创始人兼首席执行官 Marc Kuo 表示，这项工作突破了快速解决大规模车辆路线问题的界限。他指出，Routific 最近的一些算法进步受到了 Wu 工作的启发。

“大多数学术研究机构倾向于专注于针对小问题的专门算法，试图以处理时间为代价寻找更好的解决方案。但在现实世界中，企业并不关心寻找更好的解决方案，尤其是当他们计算时间太长，”郭解释说。“在最后一英里物流的世界中，时间就是金钱，你不能让整个仓库操作等待一个缓慢的算法来返回路线。算法需要超快才能实用。”

吴、社会与工程系统博士生李思瑞和电气工程与计算机科学博士生闫中夏本周在 2021 NeurIPS 会议上展示了他们的研究成果。

选择好的问题

车辆路径问题是一类组合问题，涉及使用启发式算法来找到问题的“足够好的解决方案”。通常不可能对这些问题提出一个“最佳”答案，因为可能的解决方案数量太多了。

“这些类型问题的游戏名称是设计高效的算法……在某些因素内是最优的，”吴解释说。“但我们的目标不是找到最佳解决方案。这太难了。相反，我们希望找到尽可能好的解决方案。即使解决方案的 0.5% 改进也可以转化为公司的巨大收入增长。”

在过去的几十年里，研究人员开发了各种启发式方法来快速解决组合问题。他们通常通过从一个糟糕但有效的初始解决方案开始，然后逐渐改进解决方案来实现这一点——例如，通过尝试小的调整来改善附近城市之间的路由。然而，对于像 2,000 多个城市路由挑战这样的大问题，这种方法需要太多时间。

最近，已经开发出机器学习方法来解决这个问题，虽然速度更快，但它们往往更不准确，即使在几十个城市的规模上也是如此。吴和她的同事决定看看是否有一种有益的方式将这两种方法结合起来，以找到快速但高质量的解决方案。

“对我们来说，这就是机器学习的用武之地，”吴说。“我们能否预测这些子问题中的哪些，如果我们要解决它们，会导致解决方案的更多改进，节省计算时间和费用?”

传统上，大规模车辆路径问题启发式可能会随机或通过应用另一个精心设计的启发式方法来选择要解决的子问题的顺序。在这种情况下，麻省理工学院的研究人员通过他们创建的神经网络运行子问题集，以自动找到子问题，这些子问题在解决后将导致解决方案质量的最大提高。Wu 及其同事发现，这个过程将子问题选择过程加快了 1.5 到 2 倍。

“我们不知道为什么这些子问题比其他子问题更好，”吴指出。“这实际上是未来工作的一个有趣方向。如果我们确实在这里有一些见解，这些可能会导致设计出更好的算法。”

惊人的加速

吴和同事对这种方法的效果感到惊讶。在机器学习中，垃圾输入、垃圾输出的概念适用——也就是说，机器学习方法的质量在很大程度上依赖于数据的质量。组合问题是如此困难，以至于它的子问题也无法得到最优解。Wu 说，对作为输入数据可用的“中等质量”子问题解决方案进行训练的神经网络“通常会给出中等质量的结果”。然而，在这种情况下，研究人员能够利用中等质量的解决方案来获得高质量的结果，明显快于最先进的方法。

对于车辆路线和类似问题，用户通常必须设计非常专业的算法来解决他们的特定问题。其中一些启发式方法已经开发了几十年。

学习委托方法提供了一种自动方法来加速这些针对大型问题的启发式方法，无论启发式方法是什么，或者——可能——问题是什么。

Wu 说，由于该方法可以与各种求解器一起使用，因此它可能对各种资源分配问题有用。“我们可能会解锁现在可能实现的新应用程序，因为解决问题的成本要低 10 到 100 倍。”