研究人员开发了一种基于机器学习的技术，以比某些传统方法更有效地解决复杂的长期规划问题，同时达到更好地满足用户目标的最佳解决方案。
当一些通勤列车到达终点站时，它们必须前往一个切换平台进行调头，以便稍后从车站出发，通常是从与到达时不同的平台出发。
工程师使用称为算法求解器的软件程序来规划这些运作，但是在一个每周有数千次到达和出发的车站，这个问题变得过于复杂，以至于传统的求解器无法一次性地解决。
通过使用机器学习，麻省理工学院的研究人员开发了一个改进的规划系统，将求解时间减少了多达50％，并生成了一个更好地满足用户目标的解决方案，例如准时列车出发。这种新方法也可以用于有效解决其他复杂的物流问题，如医院工作人员排班、分配航空公司机组或分配任务给工厂机器。
工程师通常将这些类型的问题拆分成一系列重叠的子问题，这些子问题可以在合理的时间内各自解决。但是，这些重叠导致许多决策被不必要地重复计算，因此求解器达到最佳解决方案所需的时间更长。
这种新的增强人工智能的方法学习哪些部分的子问题应保持不变，将这些变量固定，以避免冗余计算。然后，传统的算法求解器处理剩余的变量。
“通常，一个专门的团队可能会花费数月甚至数年时间来设计一个算法，只为解决这些组合问题中的一个。现代深度学习为我们提供了一个机会，利用新的进展来帮助简化这些算法的设计。我们可以利用我们知道有效的东西，并用人工智能来加速它，”麻省理工学院土木与环境工程（CEE）和数据、系统与社会研究所（IDSS）的一名职业发展副教授凯西·吴（Cathy Wu）表示，她还是信息与决策系统实验室（LIDS）的一员。
论文的其他作者包括首席作者、IDSS研究生李思睿；CEE研究生欧阳文彬；以及LIDS博士后马一宁。这项研究将在国际学习表示会议上进行展示。
消除冗余
进行此研究的一个动机是麻省理工学院一名硕士生德文·卡米尔·威尔金斯（Devin Camille Wilkins）在吴教授的入门运输课程中提出的一个实际问题。这位学生想将强化学习应用于波士顿北站的一个真实列车调度问题。交通组织需要将许多列车分配到有限数量的平台上，以便在它们到达车站之前就做好调头准备。
这被发现是一个非常复杂的组合调度问题，正是吴实验室在过去几年中所研究的类型。
在面临一个长期问题时，涉及将有限的资源（如工厂任务）分配给一组机器，规划者通常将这个问题框架为灵活作业车间调度。
在灵活作业车间调度中，每个任务需要不同的时间来完成，但是任务可以分配给任何机器。与此同时，每个任务由必须按照正确顺序执行的操作组成。
此类问题迅速变得过于庞大和复杂，无法用传统求解器解决，因此用户可以采用滚动时间范围优化（RHO），将问题拆分成可更快解决的可管理块。
使用RHO，用户在固定的计划时间范围内分配最初的几个任务给机器，可能是一个四小时的时间段。然后，他们执行该序列中的第一个任务，并将四小时的计划时间范围向前移动，以增加下一个任务，重复该过程，直到整个问题得到解决，最终的任务-机器分配计划被创建。
计划时间范围应该比任何一个任务的持续时间更长，因为如果算法同时考虑即将到来的任务，解决方案会更好。
但是，当计划时间范围向前推进时，这会与之前计划时间范围中的操作产生一些重叠。算法已经为这些重叠的操作提出了初步解决方案。
“也许这些初步解决方案是好的，不需要重新计算，但也可能它们并不好。这就是机器学习的用武之处，”吴解释说。
对于他们称之为学习引导的滚动时间范围优化（L-RHO）的方法，研究人员教授机器学习模型预测在计划时间范围向前推进时应重新计算哪些操作或变量。
L-RHO需要数据来训练模型，因此研究人员使用经典算法求解器解决了一组子问题。他们取出最佳解决方案，即不需要重新计算的操作最多的那些作为训练数据。
一旦训练完成，机器学习模型获取一个它之前未见过的新子问题，并预测哪些操作不应该重新计算。剩余的操作被反馈到算法求解器中，算法求解器执行任务，重新计算这些操作，并向前移动计划时间范围。然后循环重新开始。
“如果从反思中看，我们不需要对其重新优化，那么我们可以将这些变量从问题中删除。由于这些问题以指数方式增长，如果我们可以删除一些变量，这可能是非常有利的，”她补充道。
一种可适应、可扩展的方法
为了测试他们的方法，研究人员将L-RHO与几种基础算法求解器、专业求解器和仅使用机器学习的方法进行了比较。它优于所有这些方法，求解时间减少了54％，解决方案质量提高了多达21％。
此外，当研究人员在更复杂的问题变体（如工厂机器故障或额外的列车拥堵）上测试时，他们的方法持续优于所有基准。它甚至优于研究人员为了挑战他们的求解器而创建的额外基准.
“我们的方法可以不作修改地应用于所有这些不同的变体，这正是我们进行这项研究的目的，”她表示。
L-RHO还可以适应目标的变化，自动生成新的算法来解决问题——它所需的只是一个新的训练数据集。
在未来，研究人员希望更好地理解模型决定冻结某些变量而不是其他变量的逻辑。他们还希望将他们的方法整合到其他类型的复杂优化问题中，如库存管理或车辆路径规划。
这项工作部分得到了国家科学基金会、麻省理工学院研究支持委员会、亚马逊机器人博士研究生奖学金和MathWorks的支持。
