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