Credit: Unsplash/CC0公共域等待假日套餐送达？在送货车开到你家门口之前，有一个棘手的数学问题需要解决，麻省理工学院的研究人员有一个策略可以加快解决速度。这种方法适用于车辆路线问题，如最后一英里(last-mile d elivery ),其目标是将货物从一个中央仓库运送到多个城市，同时降低出行成本。虽然有一些算法被设计来为几百个城市解决这个问题，但是当这些解决方案被应用于更大范围的城市时会变得太慢。
为了弥补这一点，吉尔伯特·温斯洛(Gilbert W. Winslow)土木与环境工程职业发展助理教授、数据、系统与社会研究所(Institute for Data、system and Society)的吴茜(Cathy Wu)和她的学生们提出了一种机器学习策略，可以将一些最强的算法求解器加速10到100倍。
求解算法的工作原理是将配送问题分解成更小的子问题来解决——比如，200个子问题用于在2000个城市之间安排车辆路线。吴和她的同事用一种新的机器学习算法来增强这个过程，该算法识别最有用的子问题来解决，而不是解决所有的子问题，以提高解决方案的质量，同时使用数量级更少的计算。
研究人员说，他们的方法被称为“学习委派”，可以用于各种求解器和各种类似的问题，包括仓库机器人的调度和寻路。
Routific的创始人兼首席执行官Marc Kuo表示，这项工作突破了快速解决大规模车辆路线问题的界限，Routific是一个优化送货路线的智能物流平台。他指出，Routific最近在算法方面的一些进展受到了吴工作的启发。
“大多数学术研究倾向于专注于针对小问题的专门算法，试图以处理时间为代价找到更好的解决方案。但在现实世界中，企业并不关心找到更好的解决方案，尤其是在计算时间过长的情况下。“在最后一英里物流的世界里，时间就是金钱，你不能让你的整个仓库运营等待一个缓慢的算法来返回路线。一个算法需要超快才能实用。”
社会与工程系统博士生吴和电气工程与计算机科学博士生严忠霞本周在2021神经科学大会上介绍了他们的研究。
选择好的问题
车辆路径问题是一类组合问题，它涉及使用启发式算法来寻找问题的“足够好的解”。对于这些问题，通常不可能给出一个“最好”的答案，因为可能的解决方案数量太多了。
“这类问题的游戏名称是设计高效的算法……在某些因素下是最优的，”吴解释说。“但目标不是找到最优解。那太难了。相反，我们希望找到尽可能好的解决方案。即使解决方案改进了0.5%，也能为公司带来巨大的收入增长。”
在过去的几十年里，研究人员开发了各种启发式方法来快速解决组合问题。他们通常这样做，从一个糟糕但有效的初始解决方案开始，然后逐渐改进解决方案——例如，通过尝试小的调整来改进附近城市之间的路由。然而，对于像2000多个城市的路由挑战这样的大问题，这种方法花费的时间太多了。
最近，机器学习方法已经被开发出来解决这个问题，但是虽然速度更快，但往往更不准确，即使是在几十个城市的规模上。吴和她的同事们决定看看是否有一种有益的方法，将这两种方法结合起来，找到快速但高质量的解决方案。
“对我们来说，这就是机器学习的用武之地，”吴说。“如果我们解决了这些子问题，我们能预测哪些子问题会导致解决方案的更多改进，从而节省计算时间和费用吗？”
传统上，大规模车辆路径问题启发式算法可以随机或通过应用另一种精心设计的启发式算法来选择子问题的求解顺序。在这种情况下，麻省理工学院的研究人员通过他们创建的神经网络运行一组子问题，以自动找到子问题，当这些子问题被解决时，将导致解决方案质量的最大提高。吴和同事发现，这个过程将子问题选择过程加快了1.5到2倍。
“我们不知道为什么这些子问题比其他子问题更好，”吴指出。“这实际上是未来工作的一个有趣方向。如果我们在这方面确实有一些见解，这些可能会导致设计更好的算法。”
惊人的加速
吴和他的同事对这种方法的效果感到惊讶。在机器学习中，垃圾进入、垃圾排出的思想适用——也就是说，机器学习方法的质量在很大程度上取决于数据的质量。一个组合问题是如此的困难，以至于它的子问题都不能被最优地解决。吴说，一个神经网络训练“中等质量”的子问题解决方案作为输入数据，“通常会给我中等质量的结果”。然而，在这种情况下，研究人员能够利用中等质量的解决方案来获得高质量的结果，比最先进的方法快得多。
对于车辆路径和类似的问题，用户通常必须设计非常专业的算法来解决他们的特定问题。其中一些试探法已经发展了几十年。
“学习委派”方法提供了一种自动的方法来加速这些大型问题的启发式方法，无论启发式方法是什么，或者潜在地是什么问题。
吴说，由于这种方法可以与多种解算器一起工作，因此它可能对多种资源分配问题有用。“我们可能会解锁新的应用程序，因为现在解决这个问题的成本要低10到100倍。”
来源：由phyica.com整理转载自PH，转载请保留出处和链接！
