Page 20 - 《软件学报》2021年第12期

软件学报 ISSN 1000-9825,CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2021,32(12):3684−3697 [doi: 10.13328/j.cnki.jos.006161] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

∗
求解二维装箱问题的强化学习启发式算法

阳名钢, 陈梦烦, 杨双远, 张德富

(厦门大学 信息学院,福建 厦门 361005)
通讯作者: 张德富,E-mail: dfzhang@xmu.edu.cn

摘 要: 二维带形装箱问题是一个经典的 NP-hard 的组合优化问题,该问题在实际的生活和工业生产中有着广泛
的应用.研究该问题,对企业节约成本、节约资源以及提高生产效率有着重要的意义.提出了一个强化学习求解算
法.新颖地使用强化学习为启发式算法提供一个初始的装箱序列,有效地改善启发式冷启动的问题.该强化学习模型
能进行自我驱动学习,仅使用启发式计算的解决方案的目标值作为奖励信号来优化网络,使网络能学习到更好的装
箱序列.使用简化版的指针网络来解码输出装箱序列,该模型由嵌入层、解码器和注意力机制组成.使用 Actor-Critic
算法对模型进行训练,提高了模型的效率.在 714 个标准问题实例和随机生成的 400 个问题实例上测试提出的算法,
实验结果显示:提出的算法能有效地改善启发式冷启动的问题,性能超过当前最优秀的启发式求解算法.
关键词: 二维装箱问题; 强化学习; 指针网络; 启发式算法; 分层搜索
中图法分类号: TP301

中文引用格式: 阳名钢,陈梦烦,杨双远,张德富.求解二维装箱问题的强化学习启发式算法.软件学报,2021,32(12):3684
–3697.http://www.jos.org.cn/1000-9825/6161.htm
英文引用格式: Yang MG, Chen MF, Yang SY, Zhang DF. Reinforcement learning heuristic algorithm for solving the two-
dimensional strip packing problem. Ruan Jian Xue Bao/Journal of Software, 2021,32(12):3684−3697 (in Chinese). http://www.jos.
org.cn/1000-9825/6161.htm
Reinforcement Learning Heuristic Algorithm for Solving the Two-dimensional Strip Packing Problem

YANG Ming-Gang, CHEN Meng-Fan, YANG Shuang-Yuan, ZHANG De-Fu
(School of Informatics, Xiamen University, Xiamen 361005, China)

Abstract: The two-dimensional strip packing problem is a classic NP-hard combinatorial optimization problem, which has been widely
used in daily life and industrial production. This study proposes a reinforcement learning heuristic algorithm for it. The reinforcement
learning is used to provide an initial boxing sequence for the heuristic algorithm to effectively improve the heuristic cold start problem.
The reinforcement learning model can perform self-driven learning, using only the value of the heuristically calculated solution as a
reward signal to optimize the network, so that the network can learn a better packing sequence. A simplified version of the pointer
network is used to decode the output boxing sequence. The model consists of an embedding layer, a decoder, and an attention mechanism.
Actor-critic algorithm is used to train the model, which improves the efficiency of the model. The reinforcement learning heuristic
algorithm is tested on 714 standard problem instances and 400 generated problem instances. Experimental results show that the proposed
algorithm can effectively improve the heuristic cold start problem and outperform the state-of-the-art heuristics with much higher solution
quality.
Key words: two-dimensional strip packing problem; reinforcement learning; pointer network; heuristics; hierarchical search

二维带形装箱问题是指将一组矩形小物品装入一个具有给定宽度、但是高度无限的矩形箱子中,这些矩形
只能按照固定方向放置,不能相互重叠,且必须完全装入箱子中.问题的目标是使得使用的高度尽可能的低.
二维装箱问题是经典的组合优化问题,在各行各业中都有着非常广泛的应用.如在石材切割中,物品是小块

∗ 基金项目: 国家自然科学基金(61672439)
收稿时间: 2020-07-14; 修改时间: 2020-08-20; 采用时间: 2020-09-17; jos 在线出版时间: 2021-05-20