KAIST宣布，计算机系教授Minsoo Kim研究团队开发出一项名为“RL-SPH”的强化学习方法，使AI无需借助外部专业优化程序，也能在现实约束条件下生成可执行的计划方案。

这类问题广泛存在于物流配送、车辆路径规划、工厂生产调度和医院排班等场景，本质上属于需要在多重约束下寻找高效方案的整数线性规划（ILP）问题。以快递配送为例，如果方案无法满足车辆载重、配送人员工时等约束，就很难直接用于实际作业。

研究团队指出，现有AI方法即便能够给出降低成本或缩短时间的方案，也可能违反车辆载重、工时等现实条件，因此往往还需要借助专业优化程序对AI生成的结果进行修正。

与直接预测答案的方式不同，RL-SPH采取的是逐步修正当前计划的思路。该方法并不一开始就追求最优解，而是优先让AI找到能够在现实中落地的可行方案。

具体来看，RL-SPH采用两阶段搜索策略：第一阶段先找到满足全部约束条件的“可行解”；第二阶段在保持可行性的前提下，进一步优化成本与时间。团队同时引入了用于建模变量与约束关系的AI模型“ILP-GT”，并采用优先调整关键变量的搜索策略。

在5类基准测试中，RL-SPH在所有问题上都成功找到了可行方案。在包含一般整数变量的复杂问题中，其可行解搜索成功率达到100%。

与现有方法相比，RL-SPH在多项指标上均有明显提升。其中，用于衡量与最优解差距的“Primal gap”平均改善28.6倍；用于评估搜索质量与速度的“Primal integral”改善2.6倍；首次找到可行方案的时间平均缩短2.5倍。

与PAS、DDIM、DiffILO等最新AI方法相比，只有RL-SPH在全部基准测试中均实现了100%的可行解搜索成功率。其平均训练时间仅为30分钟，较现有技术快14.7倍，较基于无监督学习的方法快约34倍。

在国际优化基准MIPLIB评测中，RL-SPH还能够在规模较以往最高扩大67倍的问题上找到可行方案，并在训练过程中未接触过的新类型问题上展现出泛化能力。

Minsoo Kim表示，在现实场景中，相比“最优答案”，“能够实际执行的计划”往往更为重要。他预计，这项技术将成为推动AI决策在物流、制造、半导体生产和人力运营等产业现场落地的关键能力。

本项研究由计算机系博士生Taehun Lee担任第一作者，Minsoo Kim担任通讯作者。相关成果已于今年7月举行的国际机器学习大会（ICML）上发表。