更快更高更强！优化车辆路线的机器学习新策略

图源：Unsplash/CC0公共域

将货物从一个中心仓库运送到多个城市，同时降低运输成本的车辆路径问题一直是配送的一大难题，现有的算法可以用于解决几百个城市的这个问题，但当城市的数量和规模扩大后，这些算法就太慢了。

麻省理工学院的Cathy Wu等研究人员针对此问题开发了一个机器学习策略，将目前最强算法的运行速度提升至原来的10到100倍。

这种新的算法是将配送问题分解成更小的子问题来解决。比如，将2000个城市之间的车辆路径问题分解成200个子问题，从中识别出最有用的子问题去解决，而不是去解决所有的子问题。这样做可以用数量级更小的计算，得到质量更优的解决方案。

这种新的算法被称为“学习委托”，可用于仓库机器人的调度和寻路等各种类似的问题。

优化配送路线的智能物流平台Routific的创始人兼首席执行官Marc Kuo表示：“这项工作推动了大规模车辆路径问题的快速解决。大多数学术机构倾向于专注解决小问题的算法，试图以处理时间为代价找到更好的解决方案。但在现实世界中，企业并不关心更好的解决方案，尤其是在计算时间更长的情况下。在最后一英里配送行业，时间就是金钱，你不能让整个仓库操作等待一个缓慢的算法反馈路线，一个超快的算法才能实际应用。”

选择好的问题

车辆路径问题是一类组合问题，它涉及到使用启发式算法来寻找问题的“更优解”，然而我们通常不可能想出一个“最佳”答案，因为解决方案实在是太多了。

Wu解释道：“解决这类问题的关键在于设计有效的算法，但我们的目标不是找到最优解决方案，那太困难了。相反，我们只是去寻找尽可能好的解决方案，因为即使是解决方案0.5%的改进，也可以转化为公司收入的巨大增长。”

在过去的几十年里，研究人员开发了各种启发式算法来解决组合问题。他们通常从一个糟糕但有效的初始解决方案开始，再逐步改进。但是对于像2000多个城市这样庞大的车辆路径问题，这种方法会花费太多时间。

最近，人们开发了机器学习策略来解决这个问题，虽然更快，但往往更不准确，即使是几十个城市的规模也是如此。

Wu和她的同事们决定看看是否有一种方法可以将这两种方法结合起来，找到快速且优质的解决方案。

传统的启发式算法可能是随机选择要解决的子问题，也可能是花费很多时间选择子问题。麻省理工学院的研究团队通过他们创建的神经网络运行了一组子问题，他们发现这个过程将子问题的选择过程加快了1.5到2倍。

“我们不知道为什么这些子问题比其他子问题更好，”Wu指出，“这将是我们未来工作的一个有趣的方向，研究清楚这个问题可以帮助我们设计出更好的算法。”

惊人的加速

机器学习方法的质量在很大程度上依赖于数据的质量。Wu解释说，一个训练有素的“中等质量”的子问题解决方案作为输入数据，通常会得到“中等质量”的输出结果。然而，研究人员却能够利用“中等质量”的解决方案得到“高质量”的结果，且比最先进的方法要快得多。

“学习委托”算法为车辆路径问题提供了一种自动加速的启发式算法，并且适用于各种各样的求解者，也就是说它可以应用在各种资源分配问题上。Wu说：“未来我们可能会解锁新的应用程序，因为现在解决这类问题的成本已经减少了10到100倍。”

本文由升哲科技编译，转载请注明。