Random-Key Optimizer with reinforcement learning for the Capacitated Multi-period Cutting Stock Problem with setup cost

Autor(es)

Silva, Eduardo M. ; Chaves, Antonio A. ; de Araujo, Silvio A. ; Jans, Raf

• Tipo de documento: Artigo Científico
• Fonte: Computers & Operations Research; v. 183, p. 18-pg., 2025-11-01.

Resumo

This paper introduces a Random-Key Optimizer (RKO) procedure incorporating reinforcement learning to solve the One-Dimensional Multi-Period Cutting Stock Problem (MPCSP) with setup costs and capacity constraints. The MPCSP involves determining cutting plans for each period to meet customer demands, where inventory variables link consecutive periods. The RKO represents solutions as random-key vectors, which are decoded into feasible solutions for the MPCSP through a decoder process. During the optimization process, the RKO dynamically adapts its parameters using reinforcement learning. This framework integrates Biased Random-Key Genetic Algorithm (BRKGA), Particle Swarm Optimization (PSO), and Simulated Annealing (SA), all utilizing a unified decoder function. A novel penalization mechanism is also introduced within the decoder to handle infeasibilities effectively. The proposed RKO is evaluated on benchmark instances from the literature and compared against state-of-the-art methods, including a hybrid column generation heuristic and a dynamic programming-based heuristic. In addition, a new set of large-scale instances is introduced for further evaluation. Computational experiments reveal that the RKO employed by BRKGA consistently outperforms other solution methods in benchmark instances, delivering superior average solution quality. A sensitivity analysis is also conducted, examining the impact of setup costs and production capacity. Moreover, the study includes a comparative analysis of the RKO framework with and without reinforcement learning. (AU)

• Processo FAPESP: 13/07375-0 - CeMEAI - Centro de Ciências Matemáticas Aplicadas à Indústria
• Beneficiário: Francisco Louzada Neto
• Modalidade de apoio: Auxílio à Pesquisa - Centros de Pesquisa, Inovação e Difusão - CEPIDs
• Processo FAPESP: 22/05803-3 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento e localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 22/05803-3 - Problemas de corte, empacotamento, dimensionamento de lotes, programação da produção, roteamento e localização e suas integrações em contextos industriais e logísticos
• Beneficiário: Reinaldo Morabito Neto
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 23/04588-4 - Modelos e métodos adaptativos para o problema de corte de estoque multi-período com restrições de setups e capacidade
• Beneficiário: Eduardo Machado Silva
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 24/08848-3 - Problema de roteamento de veículos com coleta e entrega de cargas completas: métodos de otimização e restrições práticas da milha intermediária da cadeia de suprimentos
• Beneficiário: Antônio Augusto Chaves
• Modalidade de apoio: Auxílio à Pesquisa - Regular
• Processo FAPESP: 24/01409-4 - Problemas de dimensionamento de lotes e de roteamento: aplicações industriais e logísticas
• Beneficiário: Silvio Alexandre de Araujo
• Modalidade de apoio: Bolsas no Exterior - Pesquisa
• Processo FAPESP: 18/15417-8 - Desenvolvimento de uma meta-heurística híbrida com fluxo de controle e parâmetros adaptativos
• Beneficiário: Antônio Augusto Chaves
• Modalidade de apoio: Auxílio à Pesquisa - Jovens Pesquisadores - Fase 2