Study of Methods for One-dimensional Bin Packing Problem

Resumen

The Bin Packing Problem (BPP) is a classic optimization problem that is known for its applicability andcomplexity, which belongs to a particular class of problems called NP-hard, in which, given a set of items ofvariable size, we search to accommodate them inside fixed size containers, seeking to optimize the numberof containers to be used, that is, using the least number of containers to place the largest number of itemspossible. For this problem, there are different variants with respect to the dimensions of objects (1D-BPP,2D-BPP and 3D-BPP), number of objectives to satisfied (Multiobjective) and changes on time (Dynamic).In this study we will focus only on the One-dimensional Bin Packing Problem (1D-BPP), because it isthe base problem for the multidimensional, multiobjective and dynamic variants and has been preservedas a current study problem due to the various applications that it offers. In the current state of the artfor 1D-BPP, there are different algorithms, mainly heuristics for solving the problem, however, there is noheuristic or metaheuristic algorithm capable of finding the optimal solution for all possible instances of aproblem of this type despite the scientific community’s efforts.This work presents a study of methods and strategies that have been used to address 1D-BPP in thelast two decades, in order to identify the most promising ones regarding algorithmic performance. Themain objective is that this study can help both researchers and professionals interested in using specificcomponents or techniques that help improve the behavior of an algorithm to solve this problem.Among the strategies implemented in recent years we find the hybridization of metaheuristic algorithmswith machine learning, with reinforcement learning (RL) being the most used, which is an excellent alternative to dynamically adapt the search for these heuristics by training an agent in a supervised orself-supervised manner [1]. A reinforcement learning agent tries to learn the behavior through trial-anderror interactions in a dynamic and uncertain environment. The agent does not know what actions totake, and it must automatically discover which actions produce the maximum benefit. In addition, it mustbe able to adapt to changes that occur in the environment. On each interaction, the agent receives anindication of its current state and selects an action. The action changes state and the agent receives areinforcement or reward signal. The agent’s goal is to find a policy that associates states with actions,maximizing the long-term accumulated reward.Currently, we see the field of RL for combinatorial optimization (CO) problems as a promising direction forthis research line because of the effectiveness in terms of the solution quality, the capacity to outperformthe existing algorithms, and huge running time gains compared to the classical heuristic approaches. We present a grouping genetic algorithm as case of study. In the proposed version, a new strategy was implemented incorporating reinforcement learning to one of the genetic operators. Preliminary results of our version showed an increase in its performance compared to the original genetic algorithm [2]. According to the results obtained in the experimentation, the proposed version improves the performance of theoriginal algorithm by 6.23%, solving 80 more instances and reducing the execution time. With this work,it was possible to identify some promising strategies that could be addressed in the future for 1D-BPPand obtain a greater impact on performance if are combined or implemented in conjunction with other methods.