Solving One-Dimensional Cutting Stock Problems with the Deep Reinforcement Learning
Jie Fang, Yunqing Rao, Qiang Luo, Jiatai Xu
Abstract
It is well known that the one-dimensional cutting stock problem (1DCSP) is a combinatorial optimization problem with nondeterministic polynomial (NP-hard) characteristics. Heuristic and genetic algorithms are the two main algorithms used to solve the cutting stock problem (CSP), which has problems of small scale and low-efficiency solutions. To better improve the stability and versatility of the solution, a mathematical model is established, with the optimization objective of the minimum raw material consumption and the maximum remaining material length. Meanwhile, a novel algorithm based on deep reinforcement learning (DRL) is proposed in this paper. The algorithm consists of two modules, each designed for different functions. Firstly, the pointer network with encoder and decoder structure is used as the policy network to utilize the underlying mode shared by the 1DCSP. Secondly, the model-free reinforcement learning algorithm is used to train network parameters and optimize the cutting sequence. The experimental data show that the one-dimensional cutting stock algorithm model based on deep reinforcement learning (DRL-CSP) can obtain the approximate satisfactory solution on 82 instances of 3 data sets in a very short time, and shows good generalization performance and practical application potential.