A reinforcement learning approach to the stochastic cutting stock problem

作     者：Pitombeira-Neto, Anselmo R. Murta, Arthur H. F. 

作者机构：Univ Fed Ceara Dept Ind Engn Campus Pici Fortaleza Brazil Univ Fed Ceara Grad Program Modeling & Quantitat Methods Fortaleza Brazil Univ Fed Ceara OPL Lab Operat Res Prod & Logist Fortaleza Brazil 

出 版 物：《EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION》 (EURO J. Comput. Optim.)

年 卷 期：2022年第10卷

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Coordenacao de Aperfeicoamento de Pessoal de Nivel Superior - Brazil (CAPES) Conselho Nacional de Desenvolvimento Cientifico e Tecnologico (CNPq) [422464/2016-3] 

主　　题：Cutting stock problem Reinforcement learning Approximate dynamic programming 

摘      要：We propose a formulation of the stochastic cutting stock problem as a discounted infinite-horizon Markov decision process. At each decision epoch, given current inventory of items, an agent chooses in which patterns to cut objects in stock in anticipation of the unknown demand. An optimal solution corresponds to a policy that associates each state with a decision and minimizes the expected total cost. Since exact algorithms scale exponentially with the state-space dimension, we develop a heuristic solution approach based on reinforcement learning. We propose an approximate policy iteration algorithm in which we apply a linear model to approximate the action-value function of a policy. Policy evaluation is performed by solving the projected Bellman equation from a sample of state transitions, decisions and costs obtained by simulation. Due to the large decision space, policy improvement is performed via the cross-entropy method. Computational experiments are carried out with the use of realistic data to illustrate the application of the algorithm. Heuristic policies obtained with polynomial and Fourier basis functions are compared with myopic and random policies. Results indicate the possibility of obtaining policies capable of adequately controlling inventories with an average cost up to 80% lower than the cost obtained by a myopic policy.(c) 2022 The Author(s). Published by Elsevier Ltd on behalf of Association of European Operational Research Societies (EURO).