基于启发式引导强化学习的钢板分配方法

《ADVANCED ENGINEERING INFORMATICS》：Steel plate allocation via heuristic-guided reinforcement learning

　　

- 高效求解一维切割下料问题。
- 在最小化母板用量的同时最大化余料集中度。
- 利用启发式基元构建动作空间以应用于强化学习。
- 采用价值网络与策略网络耦合训练范式。

**引言**

厚钢板构成了大型工程系统的结构基础，广泛应用于建筑、造船和重型机械制造等领域[1]。产品多样化趋势和小批量订单的兴起已显著增加了现代钢企的生产计划复杂度。订单分配因此成为一项关键的运营决策问题。给定一组客户订单，需将轧制母板分割为满足尺寸约束的子板，同时最小化材料浪费。鉴于产能过剩和利润空间收窄的现状，改进切割策略以减少材料浪费已成为迫在眉睫的运营优先级[2]。在实际生产中，订单长度差异悬殊，可用母板尺寸受上游轧制条件波动影响而不断变化，残余材料需集中管理以支持再利用。这些因素在分配决策与余料分布之间引入了强耦合，构成了一个高度约束的一维切割下料问题（1D-CSP）。

1D-CSP是运筹学中的经典NP难问题[3]。其主要目标是将子板分配到最少数量的母板上，以减少原材料消耗。除钢板切割外，该问题还出现在造纸[4]、木材加工[5]和玻璃制造[6]等领域，是常见的技术挑战。由于解空间随问题规模呈指数级增长，在可接受的时间内获取全局最优解极为困难。图1(a)展示了一个典型构建示例，其中子板需重新组合以恢复原始母板数量和长度集合。此过程要求在海量的组合空间内识别隐含的最优装填结构[7]。在工程规模上一致近似此类结构最优解将显著提升材料利用率、减少库存积压并缩短生产排程周期。然而，迄今为止尚无任何研究提出了能在不完全枚举的情况下精确求解此类问题的方法。

如图1(b)所示，板材分组需要将客户订单映射为可供轧制的母板可行组合。如表1所总结，针对复杂切割问题及其变体已开发了多种优化策略，厚板分组是其代表性案例之一。整数线性规划提供了经典形式化方法，通过将问题抽象为数学模型来求解，原则上可获得精确最优解[11]、[18]。然而，该问题的NP难特性导致大规模问题求解时间不可接受。基于列生成的密切相关方法在材料利用率方面取得了改进[9]、[10]。然而，其性能仍滞后于现代生产系统对秒级响应和实时调度中细粒度优化的需求。

为提高计算效率，研究人员开发了一系列面向工程应用的近似策略。启发式方法因其简单性、低推理成本和易于纳入运营约束等优势，在板材分组问题中被广泛应用[14]、[15]。Barragán-Vite提出了一种基于Petri网的1D-CSP方法，仅需调节两个参数：束宽和过滤宽度[16]。该方法表现出具有竞争力的性能，尤其在中等规模问题上。然而，启发式方法本质上依赖确定性规则执行局部搜索，通常缺乏有效逃离局部最优的机制[25]。

与传统启发式相比，元启发式方法引入了种群进化等机制以实现解空间的全局探索，能提供更优的解决方案。Liang等人的早期研究表明，在设计良好的算子条件下，相对简单的进化编程即使不使用交叉操作也能达到与经典遗传算法相当的解质量[19]。这一发现表明算法性能更取决于其与问题表示的兼容性而非算子复杂度。后续研究聚焦于编码方案和算子设计的创新。Jin等人提出了一种混合多染色体遗传算法，将切割模式与其使用频率在编码中分离[20]。

然而，元启发式面临的核心挑战在于探索与利用之间的平衡。为解决此问题，Quiroz-Castellanos等人开发了一种具有受控基因传递的分组遗传算法，其中交叉算子保留优势基因，并结合自适应基于变异的局部改进启发式。该设计使该方法在广泛认可的Hard28基准测试集上超越了主流算法。并行化进一步推动了分组遗传算法的性能提升。Dokeroglu提出了一种基于岛屿模型的并行混合分组遗传算法，多个子种群并行演化，并应用混合启发式重新插入残余项目，在1,318个实例中达到了88.54%的最优率[26]。在此基础上，Kucukyilmaz研究了岛屿模型中的通信拓扑和迁移策略，首次提出并评估了一种动态通信拓扑。该方法为遗传算法设定了新基准，在Hard28测试集的28个实例中求解了23个[27]。更近期的研究引入了生物启发方法，如非洲水牛优化算法和差分信息素分组蚁群优化，通过模拟群体学习和协作行为改进搜索引导[22]、[23]。尽管取得这些进展，元启发式的计算成本仍然很高，且对参数调节极为敏感，参数调节本身也成为复杂子问题。更重要的是，大多数现有方法假设固定有限数量的母板尺寸，隐含牺牲了对预定义模式的泛化能力。在真实钢铁生产中，新型尺寸规格频繁出现，现有模型需要反复预处理和参数调节[28]。随着子板类型多样性增加，编码长度随之增长，模式库的膨胀可能使计算不可行。

近年来，深度强化学习在组合优化中展现出强大潜力，通过学习决策策略替代人工设计规则，从而平衡决策效率与泛化能力。一项代表性研究采用指针网络建模切割序列，使强化学习智能体能够自动学习有效的切割策略[24]。然而，这些方法生成的解决方案往往无法平衡最小化原材料使用数量与最大化余料集中度的目标。这一局限性表明奖励函数设计和训练策略仍需进一步改进。

尽管如此，Fang等人的工作提供了重要见解[24]。大多数先前研究聚焦于最小化母板数量，而忽略了余料的利用价值。从生产经济学的角度来看，在实际操作中往往存在多个可行方案能达到相同的最小母板数。在这种情况下，需要在等效解之间进一步筛选。这一观察呼唤对优化目标进行层次化重构。不应仅将最优率作为主要评估标准，而应将目标扩展为：在达到最小母板数后，进一步优化余料的空间分布。特别是，提高余料集中度可以增强其未来再利用潜力。Scheithauer等人的早期工作将残余长度建模为人工物品并显式纳入切割模式[29]。利用线性规划和列生成方法，将余料价值整合到目标函数中。然而，该方法仅限于管理单一类型余料。在此基础上，Cui引入了序贯启发式方法补充残余需求，并结合整数取整策略，通过余料价值系数平衡余料价值收益与短件消耗[13]。更近期地，Nascimento引入惩罚机制以促进余料集中，但此类多约束形式化将负担转移到了计算成本上[14]。研究人员提出了一种名为OptimizationTREE的启发式算法，通过树形结构探索切割组合，将损失集中到少数板材上，从而将废料转化为可再利用的余料[15]。在真实生产场景中，分散在多块母板上的短余料通常难以再利用。相比之下，如图1(b)所示，集中在少数母板上的长余料具有显著更高的再利用价值。因此，在维持最小化母板数量目标的同时，将余料分布结构纳入优化目标，对于将板材分组决策从基础材料节约推进到精细化价值管理至关重要。

针对上述需求，本研究提出了一种耦合价值-策略优化框架（CVPO），将启发式基元与深度强化学习相结合，在序贯决策范式下求解1D-CSP。该框架从计算高效的初始分组开始，通过启发式基元定义结构化的有限动作空间，这些基元编码了可行的局部子板重分配操作。候选动作由价值评估器评估，提供长期结果的稳定离线估计，而策略学习者则学习多步决策策略，逐步超越价值网络提供的基准。优化目标以层次化方式形式化：（i）最小化激活的母板数量；（ii）最大化余料在有限目标板材子集上的集中度。通过消除对固定切割模式和预设板材尺寸的依赖，CVPO生成高质量、可扩展的解决方案，实现母板近全利用并系统组织余料以供潜在再利用，为复杂工业装填问题建立了实用且理论基础扎实的方法。

**问题建模与模型构建**

本研究受厚板生产中的板材分组决策问题启发。如图1(c)所示，客户订单被转化为母板上的具体切割方案。在实际场景中，母板可行长度范围受设备能力的严格约束。例如，轧辊台的承载能力决定了允许的最大板材长度，而轧辊之间的间隙则设定了下限。在轧制过程中，板材展宽

**方法**

所有后续算法组件均集成于CVPO框架中，该框架通过耦合的价值网络和策略网络模块编排基元引导的子板交换，其中启发式基元定义动作空间，价值网络提供稳定评估，策略网络学习长期策略。

**学习目标与监督标签定义**

价值网络被设计为学习从动作到其关联风险值的映射，从而为给定的板材分组配置和选定的基元提供价值评估。设离散决策步骤$t$处的板材分组配置记为$b_t \in B$。对于任何候选基元$a \in \mathcal{A}$，执行单步重分配后得到下一状态$b_{t+1} = f(b_t, a)$。监督标签通过从$b_{t+1}$开始的蒙特卡洛未来重分配估计来构建。

**训练过程分析**

图4(a)展示了价值网络训练过程中的损失演化。训练损失在早期阶段急剧下降，在约100个epoch后逐渐稳定，表明模型已收敛。这表明初始训练后，价值网络足够稳定，可为决策提供可靠指导。图4(b)至4(d)展示了策略网络训练过程中的收敛行为。图4(b)展示了单条轨迹下的回合奖励变化。

**结论**

1D-CSP由于NP难计算复杂度、解空间组合爆炸以及多样化的现实资源约束，始终是工业优化中的长期挑战。针对厚板分组场景，本研究提出了CVPO框架，将启发式设计 与深度强化学习相结合，旨在同时最小化母板数量并促进余料集中。

本工作的核心贡献在于…

**CRediT作者贡献声明**

Yuduo Zhao：撰写-审阅与编辑，概念化设计。Siwei Wu：资源支持，调查研究。Yuda Chen：可视化，软件开发。Tianlong Su：软件开发。Guodong Wang：资源支持，项目管理。

**利益冲突声明**

作者声明不存在已知的竞争经济利益或个人关系可能影响本文所报告的工作。

**致谢**

本研究得到中国国家重点研发计划（项目编号：2022YFB3304800）的资助。

Yuduo Zhao | Siwei Wu | Yuda Chen | Tianlong Su | Guodong Wang