KAIST开发出强化学习技术 无需外部求解器即可生成可行的交付、生产和劳动力调度计划的人工智能

盖世汽车讯 从包裹递送路线、工厂生产计划到医院值班表，许多现实世界的规划任务都需要满足众多运营约束的解决方案。据外媒报道，由韩国科学技术院（KAIST）计算机学院Min-Soo Kim教授领导的研究团队开发了一种名为RL-SPH（基于强化学习的起始原始启发式算法）的强化学习技术，该技术训练人工智能独立生成可行的方案，而无需依赖外部求解器。该研究成果已发表在arXiv预印本服务器上。

这项技术的关键特性在于它能够学习如何生成满足优化问题中多个约束条件的解决方案。研究团队期望该方法能够为物流、制造、半导体生产和劳动力管理等领域的AI决策奠定重要基础。

包裹递送路线规划、车辆路线规划、工厂生产调度和医院员工排班都是典型的规划问题，都可以使用整数线性规划（ILP）进行建模。ILP是一种数学优化技术，用于在满足一组线性约束条件且部分或全部决策变量取整数值的前提下，寻找最优解。

当快速答案无法使用时

例如，包裹递送计划不仅要尽可能缩短递送时间，还必须满足车辆容量限制和司机工作时间要求，同时确保每个目的地都能被访问。即使路线看起来多么短或便宜，只要违反了其中任何一项条件，在实践中都无法使用。

现有的基于学习的方法可以快速生成近似解或部分解，但这些预测结果经常违反约束条件。因此，许多方法会将输出传递给专门的整数线性规划（ILP）求解器，例如Gurobi或SCIP，由这些求解器负责获得可行解。该轮文指出，现有的端到端基于学习的原始启发式算法通常难以独立生成可行解。

优化前的可行性分析

在近期涌现的人工智能技术中，例如PAS、DDIM和DiffILO，RL-SPH是唯一在所比较的三个基准测试（SC、CA 和 IS）中均达到100%可行性率的方法。其训练平均耗时仅为30分钟，比现有技术快14.7倍，比最新的基于无监督学习的技术快约34倍。无监督学习是一种人工智能训练方法，它无需预先提供正确答案即可在数据中发现模式。

该技术在MIPLIB上进一步展现了其泛化能力。MIPLIB是一个国际混合整数规划基准测试库，广泛应用于学术界和工业界。它不仅能够可靠地找到比训练集规模大67倍的问题的可行方案，还能找到训练过程中从未遇到过的全新问题类型的可行方案。

Kim表示：“在实际应用中，一个真正可执行的方案往往比一个理论上最优但违反实际约束的方案更为重要。这项研究表明，人工智能无需依赖专门的优化求解器来强制执行可行性，就能学习生成可行的解决方案。我们期望这项技术能够为物流、制造、半导体生产、劳动力管理和其他工业领域的人工智能决策提供重要的基础。”