A deep reinforcement learning algorithm for the rectangular strip packing problem

doi:10.1371/journal.pone.0282598

A deep reinforcement learning algorithm for the rectangular strip packing problem

2023-03-16

0

OA

AI

DOI：10.1371/journal.pone.0282598

原文链接

原文求助

摘要

En 中文

作为二维（2D）最优剪裁问题的分支，矩形条带装箱问题是一个典型的非确定性多项式（NP-hard）问题。传统的装箱解决方案方法依赖于启发式和元启发式算法。通常需要通过人工决策来指导解决方案，导致解决方案规模小、泛化能力弱且求解效率低。受深度学习和强化学习的启发，结合矩形件装箱的特点，本研究提出了一种基于深度强化学习的算法来解决矩形条带装箱问题。采用具有编码器-解码器结构的指针网络作为深度强化学习算法的基本网络。设计了一种无模型强化学习算法来训练网络参数以优化装箱顺序。该设计不仅可以避免为不同问题单独设计启发式规则，还能利用具有自学习特性的深度网络更广泛地解决不同实例。同时，设计了一种基于最大矩形底左（Maxrects-BL）的件定位算法来确定件在板材上的放置位置，并计算模型奖励和装箱参数。最后，使用实例来分析算法的优化效果。实验结果表明，所提出的算法与某些经典启发式算法相比，能产生三个更优和五个相当的结果。此外，在所有测试实例中，该算法的计算时间均少于1秒，显示出良好的泛化能力、求解效率及实际应用潜力。

A deep reinforcement learning algorithm for the rectangular strip packing problem

摘要

期刊

机构

引用论文