在全国范围内，每天都有数十万司机向客户和公司运送包裹和包裹，其中许多送货上门时间平均只有几天。以可预测且及时的方式协调如此大规模的供应链壮举是运筹学的一个长期存在的问题，研究人员一直致力于优化最后一段运输路线。

这是因为，由于电子商务需求增加、天气延误、交通堵塞、缺乏停车位、客户送货偏好或卡车部分满载而导致停靠点之间的距离过长等效率低下，该过程的最后阶段通常成本最高。疫情期间变得更加夸张和明显。

借助更新的技术和更加个性化和细致的数据，研究人员能够开发具有更好路由选项的模型，但同时需要平衡运行它们的计算成本。麻省理工学院首席研究科学家、麻省理工学院运输与物流中心(CTL)研究主任、麻省理工学院-IBMWatsonAI实验室研究员MatthiasWinkenbach讨论了人工智能如何为组合问题提供更好、计算效率更高的解决方案像这样的优化问题。

什么是车辆路径问题?传统运筹学(OR)方法如何解决该问题?

几乎所有物流和配送公司(例如USPS、亚马逊、UPS、FedEx和DHL)每天都面临着车辆路线问题。简而言之，它正在寻找一条有效的路线来连接一组需要送货或需要从他们那里取东西的客户。它正在决定您在路上看到的每辆车在特定的一天应该拜访哪些客户以及按什么顺序拜访。

通常，这里的目标是找到最短、最快或最便宜的路线。但很多时候，它们也受到特定于客户的约束的驱动。例如，如果您的客户指定了交货时间窗口，或者客户位于高层建筑的15层而不是底层。这使得这些客户更难融入高效的交付路线。

为了解决车辆路径问题，如果没有适当的需求信息以及理想情况下的客户相关特征，我们显然无法进行建模。例如，我们需要知道给定客户订购的包裹的尺寸或重量，或者需要将多少单位的特定产品运送到特定地点。

所有这些都决定了您需要为该特定站点提供服务的时间。对于现实问题，您还想知道驾驶员可以在哪里安全地停放车辆。传统上，路线规划者必须对这些参数做出良好的估计，因此经常会发现模型和规划工具做出全面假设，因为没有可用的特定站点数据。

机器学习对此非常有趣，因为现在大多数司机都有智能手机或GPS跟踪器，因此有大量关于递送包裹需要多长时间的信息。现在，您可以以某种程度自动化的方式大规模提取该信息并校准每个停靠点，以便以现实的方式进行建模。

使用传统的OR方法意味着您需要编写一个优化模型，首先定义目标函数。在大多数情况下，这是某种成本函数。然后，还有一堆其他方程定义了路由问题的内部工作原理。例如，您必须告诉模型，如果车辆拜访了客户，它也需要再次离开客户。用学术术语来说，这通常称为流量守恒。

同样，您需要确保每个客户在给定路线上都被恰好访问一次。这些和许多其他现实世界的约束一起定义了可行路线的构成。这对我们来说似乎是显而易见的，但这需要显式编码。

一旦优化问题被表述出来，就有一些算法可以帮助我们找到最好的解决方案;我们将它们称为求解器。随着时间的推移，他们找到了符合所有限制的解决方案。然后，它会尝试找到越来越好的路线，越来越便宜的路线，直到你说，“好吧，这对我来说已经足够好了”，或者直到它可以从数学上证明它找到了最佳解决方案。

美国一个城市的送货车辆平均停靠120次左右。明确地解决这个问题可能需要一段时间，所以公司通常不会这样做，因为计算成本太高。因此，他们使用所谓的启发式算法，这种算法可以非常有效地找到相当好的解决方案，但通常无法量化这些解决方案与理论最优值的差距。

您目前正在将机器学习应用于车辆路径问题。您如何利用它来利用并可能超越传统的OR方法?

这就是我们目前正在与MIT-IBMWatsonAI实验室的人员合作的项目。在这里，总体思路是在大量现有路由解决方案上训练模型，这些解决方案要么是在公司的实际运营中观察到的，要么是使用这些有效启发式方法生成的。

在大多数机器学习模型中，您不再具有明确的目标函数。相反，您需要让模型了解它实际上正在考虑什么类型的问题以及该问题的良好解决方案是什么样的。例如，与根据给定语言的单词训练大型语言模型类似，您需要根据各种送货站点的概念及其需求特征来训练路线学习模型。

就像理解自然语言的固有语法一样，您的模型需要了解如何以产生良好解决方案的方式连接这些交付站点-在我们的例子中，是一个廉价或快速的解决方案。如果您随后向其提出一组全新的客户需求，它仍然能够以字面上的方式将各个点连接起来，如果您试图找到连接这些客户的良好途径，您也会这样做。

为此，我们使用大多数人从语言处理领域了解的模型架构。这似乎有点违反直觉，因为语言处理与路由有什么关系?但实际上，这些模型的属性，尤其是Transformer模型，擅长寻找语言结构——以形成句子的方式连接单词。例如，在一种语言中，你有一定的词汇量，而且这是固定的。

它是您可以使用的一组离散的可能单词，挑战是以有意义的方式将它们组合起来。在路由方面，也是类似的。在剑桥，您可以访问大约40,000个地址。通常，需要访问的是这些地址的子集，挑战是：我们如何以有意义的顺序组合这个子集(这些“单词”)?

这就是我们方法的新颖之处——利用已被证明在语言空间中极其有效的结构并将其引入组合优化。路由对我们来说只是一个很好的测试平台，因为它是物流行业最基本的问题。

当然，经过数十年的运筹学研究，已经出现了非常好的路由算法。我们在这个项目中试图做的是，通过一种完全不同的、纯粹基于机器学习的方法，我们能够预测与您所获得的路线几乎一样好或更好的路线运行最先进的路线优化启发式。

与其他最先进的手术室技术相比，像您这样的方法有什么优势?

目前，最好的方法在训练这些模型所需的计算资源方面仍然非常饥饿，但您可以预先加载其中的一些工作。然后，经过训练的模型在需要时可以相对有效地生成新的解决方案。

另一个需要考虑的方面是航线的运营环境，尤其是在城市中，不断变化。可用的道路基础设施、交通规则和速度限制可能会改变，理想的停车场可能被其他东西占用，或者建筑工地可能会堵塞道路。使用纯粹基于OR的方法，您实际上可能会遇到麻烦，因为一旦获得有关问题的新信息，您就必须立即基本上解决整个问题。

由于操作环境是动态变化的，因此您必须一遍又一遍地执行此操作。如果您有一个训练有素的模型，并且之前遇到过类似的问题，那么它可能会立即建议下一个最佳路线。它更像是一种工具，可以帮助公司适应日益不可预测的环境变化。

此外，优化算法通常是手动设计的，以解决给定公司的特定问题。从此类显式算法获得的解决方案的质量受到算法设计的详细程度和复杂程度的限制。另一方面，基于学习的模型不断地从数据中学习路由策略。

定义模型结构后，精心设计的路线学习模型将从正在训练的大量路线中提炼出对路线策略的潜在改进。简而言之，基于学习的路线工具将继续寻找路线的改进，而您无需投资在算法中明确设计这些改进。

最后，基于优化的方法通常仅限于针对非常明确定义的目标函数进行优化，该目标函数通常寻求最小化成本或最大化利润。事实上，公司和司机面临的目标比这复杂得多，而且往往还有些矛盾。例如，一家公司希望找到高效的路线，但它也希望拥有较低的排放足迹。

司机还希望安全并能以便捷的方式为这些顾客提供服务。最重要的是，公司还关心一致性。精心设计的路线学习模型最终可以自行捕获这些高维目标，这是传统优化方法永远无法实现的。

因此，这种机器学习应用实际上可以对工业、社会和环境产生切实的现实影响。物流行业面临的问题比这复杂得多。

例如，如果您想优化整个供应链，比如说，产品从中国制造商通过世界各地不同港口的网络，通过北美大型零售商的分销网络到达您的商店你实际在哪里购买它——这涉及到很多决策，这显然使得它比优化单个车辆路线更加困难。

我们希望，通过这项初步工作，我们可以为研究和私营部门开发工作奠定基础，以构建最终实现更好的端到端供应链优化的工具。