基于强化学习的装箱问题研究

Research on Packing Problem Based on Reinforcement Learning

论文提出了一种基于改进规则和强化学习的混合启发式算法来求解二维带装箱问题(2D Strip Packing Problem,2DSPP)。首先,对基于skyline算法的评分规则进行了改进。其次使用Deep Q-Network(DQN)来获得初始的矩形物品序列,它可以提高空间利用率,防止算法陷入局部最优。将改进的评分规则与DQN相结合,提出了基于简单随机算法(SRA)的启发式算法,称为基于强化学习的简单随机算法(RSRA)。用五种算法对8个数据集进行了实验比较。结果表明,RSRA在8个数据集(C,N,CX,NT,2sp,NP,ZDF,BWMV)上的性能最好,Ave.Gap%分别比GRASP、SRA、IA、ISH算法分别提高45.86%、45.16%、30.89%和20.56%。

This paper proposes a hybrid heuristic algorithm based on improved rules and reinforcement learning to solve 2D strip packing problem(2DSPP).Firstly,the scoring rules based on skyline algorithm are improved.Secondly,deep q-network(DQN)is used to obtain the initial rectangular item sequence,which can improve the space utilization and prevent the algorithm from falling into local optimum.Combining the improved scoring rules with DQN,a heuristic algorithm based on simple random algorithm(SRA)is proposed,which is called simple random algorithm based on reinforcement learning(RSRA).Five algorithms are used to compare 8 datasets.The results show that RSRA has the best performance on 8 datasets(C,N,CX,NT,2SP,NP,ZDF,BWMV).Compared with grasp,SRA,IA and ISH algorithms,Ave.Gap%are improved by 45.86%,45.16%,30.89%and 20.56%respectively.