The dynamic bin packing optimization problem: open challenges

Resumen

The Bin Packing Problem (BPP) is a classic optimization problem that is known for its applicability and complexity, which belongs to a special class of problems called NP-hard, in which, given a set of items of variable size, we search to accommodate them inside fixed size containers, seeking to optimize the number of containers to be used, that is, using the least number of containers to place the largest number of items possible. For this problem, there are different variants such as one-dimensional (1D-BPP), 2-dimensional (2D-BPP), or 3-dimensional (3D-BPP) bin packing, multiobjective bin packing (MBP), dynamic bin packing (DBP), among others. The BPP has been preserved as a current study problem due to the various applications that it offers; therefore, in the recent state of the art, there are different algorithms, mainly heuristics, for solving the problem, however, currently, there are still open aspects of this problem that have not been studied in-depth, such as changes in the environment (dynamism). To date, there is no heuristic or metaheuristic algorithm capable of finding the optimal solution for all possible instances of a problem of this type despite the efforts of the scientific community. This work presents a review of DBP optimization model and methods to solve it; we identify those methods that provide a better impact on performance and highlight future lines of research on this problem. We also present the GGA-CGT-II algorithm as a case study extended from the Grouping Genetic Algorithm with Controlled Gene Transmission (GGA-CGT) [1] algorithm. In the proposed version, two differentstrategies were implemented: a) Method to calculate various theoretical lower limits of the optimal solution andselect the best one for each instance and b) Instance reduction method to simplify the problem. We conduct extensiveexperimentation to observe their impact on performance in isolation and then together. The new version of GGACGT showed an increment in its performance with benchmark instances for the 1D-BPP.With this work, it was possible to identify some promising lines of research for the dynamic bin packing [2,3].