全国各地，每天都有数十万名司机向客户和公司交付包裹和货物，许多点击到门的时间平均只有几天。在可预测和及时的方式上协调这样一项规模庞大的供应链任务是运营研究的长期问题，研究人员一直在努力优化交付路线的最后一段。这是因为流程的最后阶段通常是成本最高的，由于诸如电子商务需求增加导致的停车点之间的距离增加、天气延误、交通、停车位不足、客户交付偏好或卡车部分满载等效率低下的问题，在疫情期间这些问题变得更加夸张和明显。
随着新技术和更个性化、细致的数据，研究人员能够开发具有更好路线选择的模型，但同时需要平衡运行这些模型的计算成本。麻省理工学院(MIT)交通与物流中心(CTL)的首席研究科学家、研究总监、麻省理工学院-IBM沃森人工智能实验室的研究员马蒂亚斯·温肯巴赫(Matthias Winkenbach)讨论了人工智能如何能够为这类组合优化问题提供更好、更高效的解决方案。
问：什么是车辆路径问题，传统的运营研究(OR)方法如何解决这个问题？
答：车辆路径问题几乎每天都会面临着物流和快递公司，如美国邮政服务(USPS)、亚马逊(Amazon)、UPS、联邦快递(UPS)和DHL。简单来说，它是找到一条连接一组需要交付或需要从中取货的客户的高效路径。它决定了每辆车（你在路上看到的那些车辆）在某一天内应该访问哪些客户以及以什么顺序访问。通常，目标是找到导致最短、最快或最便宜路径的路线。但往往也受到特定于客户的约束的影响。例如，如果你有一个指定交货时间窗口的客户，或者一个位于高层大楼的客户与位于底层的客户。这使得将这些客户整合到一个高效的交付路线中变得更加困难。
要解决车辆路径问题，我们显然不能在没有适当的需求信息和理想情况下进行建模。例如，我们需要知道由给定客户订购的包裹的大小或重量，或者需要向某个特定位置运送多少个特定产品单位。所有这些都决定了为服务该特定停车点所需的时间。对于现实问题，您还想知道司机可以在哪里安全地停放车辆。传统上，路径规划师必须为这些参数提供良好的估计，因此往往会发现模型和规划工具在没有可用的停车点特定数据的情况下进行了一些笼统的假设。
机器学习对此非常有趣，因为现在大多数司机都有智能手机或GPS跟踪器，因此有大量关于交付包裹所需时间的信息。现在，您可以以一种相对自动化的方式大规模提取这些信息，并以真实的方式对每个停车点进行建模。
使用传统的OR方法意味着您编写一个优化模型，其中首先定义目标函数。在大多数情况下，这是一种成本函数。然后有一堆其他方程式来定义路由问题的内部工作原理。例如，您必须告诉模型，如果车辆访问了一个客户，它也需要离开该客户。在学术术语中，这通常被称为流量守恒。同样，您需要确保每个客户在给定路线上只被访问一次。这些和许多其他现实约束条件共同定义了什么构成了可行路线。对我们来说，这似乎是显而易见的，但这需要明确编码。
一旦制定了优化问题，就有算法可以帮助我们找到最佳解决方案；我们称之为求解器。随着时间的推移，它们找到符合所有约束条件的解决方案。然后，它试图找到越来越好的路线，越来越便宜的路线，直到您要么说：“好了，这对我来说足够好了”，要么数学上证明它找到了最优解。美国城市的平均交付车辆约有120个停车点。解决这个问题可能需要一段时间，所以通常公司不会这样做，因为计算成本太高了。因此，他们使用所谓的启发式算法，这些算法在寻找相当好的解决方案方面非常高效，但通常无法量化这些解决方案与理论最优解之间的差距。
问：您目前正在将机器学习应用于车辆路径问题。您如何利用它来提升和可能超越传统的OR方法？
答：这正是我们目前与麻省理工学院-IBM沃森人工智能实验室的人合作的项目。在这里，总体思路是在大量现有的路由解决方案上训练模型，这些解决方案要么是在公司的实际运营中观察到的，要么是使用其中一种高效的启发式算法生成的。在大多数机器学习模型中，您不再有一个明确的目标函数。相反，您需要让模型理解它实际上正在研究的问题类型以及问题的良好解决方案是什么样的。例如，类似于在给定语言中训练大型语言模型的单词，您需要在路线学习模型中训练各种交付停车点及其需求特征的概念。就像理解自然语言的固有语法一样，您的模型需要理解如何以一种能够产生良好解决方案的方式连接这些交付停车点 – 在我们的情况下，是一种便宜或快速的解决方案。如果您将一组全新的客户需求投入其中，它仍然能够以一种您自己寻找良好路线的方式将这些点连接起来。
为此，我们使用的是大多数人从语言处理领域了解的模型架构。这似乎有点违反直觉，因为语言处理与路径规划有什么关系呢？但实际上，这些模型，特别是变压器模型的属性，擅长在语言中找到结构 – 连接单词以形成句子。例如，在一种语言中，您有一定的词汇量，这是固定的。它是一组可能的单词，您可以使用的，挑战是如何以有意义的方式将它们组合起来。在路径规划中，情况类似。在剑桥，您可以访问大约40,000个地址。通常，需要访问的是这些地址的一个子集，挑战是：我们如何将这个子集 – 这些“单词” – 以有意义的顺序组合起来？
这是我们方法的新颖之处 – 利用已经在语言领域证明非常有效的结构，并将其引入组合优化。路径规划对我们来说只是一个很好的测试平台，因为它是物流行业中最基本的问题。
当然，已经有非常好的路径规划算法出现，这些算法经过几十年的运营研究。我们在这个项目中试图做的是展示，通过一种完全不同的、纯粹基于机器学习的方法论，我们能够预测出与运行最先进的路线优化启发式算法得到的路线几乎一样好甚至更好的路线。
问：您的方法与其他最先进的OR技术相比有什么优势？
答：目前，最好的方法在所需的计算资源方面仍然非常庞大，但您可以将其中一些工作前置。然后，一旦需要，训练好的模型在生成新解决方案时相对高效。
另一个要考虑的方面是，路线的操作环境，特别是在城市中，是不断变化的。可用的道路基础设施，或者交通规则和限速可能会发生变化，理想的停车场可能被其他东西占用，或者施工现场可能会阻塞道路。使用纯OR方法，您可能会遇到麻烦，因为一旦有关问题的新信息可用，您就必须基本上立即解决整个问题。由于操作环境是动态变化的，您必须一次又一次地这样做。而如果您有一个经过良好训练的模型，它以前见过类似的问题，它可能会几乎即时地建议下一个最佳路线。它更像是一种帮助公司适应环境中越来越不可预测变化的工具。
此外，优化算法通常是手工制作的，用于解决给定公司特定问题的特定问题。从这些显式算法获得的解决方案的质量受到算法设计中投入的细节和复杂性的限制。另一方面，基于学习的模型会不断从数据中学习路由策略。一旦定义了模型结构，一个设计良好的路由学习模型将从它正在训练的大量路线中提炼出对您的路由策略的潜在改进。简而言之，基于学习的路由工具将继续找到改进您的路线的方法，而无需您投资于显式设计这些改进到算法中。
最后，基于优化的方法通常仅限于优化非常明确定义的目标函数，该函数通常旨在最小化成本或最大化利润。而在现实中，公司和司机面临的目标要复杂得多，而且往往也有些相互矛盾。例如，公司希望找到高效的路线，但也希望减少排放。司机还希望安全，并且希望以方便的方式为这些客户提供服务。除此之外，公司还关心一致性。一个设计良好的路由学习模型最终可以自己捕捉到这些高维目标，而这是您无法通过传统的优化方法以同样方式实现的。
因此，这是一种可以在工业界、社会和环境中产生实际影响的机器学习应用。物流行业的问题比这个复杂得多。例如，如果您想优化整个供应链 – 比如说，从中国制造商通过世界各地不同港口的网络，通过北美大型零售商的分销网络到您实际购买的商店的产品流动 – 在其中涉及到很多决策，这显然比优化单个车辆路线更困难。我们希望通过这项初步工作，为研究和私营部门的开发工作奠定基础，以构建最终能够实现更好端到端供应链优化的工具。
