An adaptative multi-objective scatter search for solving the dynamic bin packing problem

• Published in: Journal of heuristics 2025-03, Vol.31 (1), p.1-69
• Main Authors: Aïder, Méziane, Boulebene, Sabrin, Hifi, Mhand
• Format: Article
• Language: English
• Subjects: Artificial Intelligence; Boxes; Calculus of Variations and Optimal Control; Optimization; Combinatorial analysis; Management Science; Mathematics; Mathematics and Statistics; Multiple objective analysis; Operations Research; Operations Research/Decision Theory; Optimization; Packing problem; Performance evaluation; Performance measurement; Qualitative analysis; Racks; Rank tests; Scattering; Statistical tests; Storefronts
• ISSN: 1381-1231; 1572-9397
• DOI: 10.1007/s10732-024-09537-y

This paper deals with the dynamic multi-objective bin packing problem, a combinatorial optimization problem within the cutting/packing problems family. A solution to this problem involves packing cooling cookies into boxes while following a specific production process. In such a case, items, each with its own capacity, arrive in batches at racks. The objective is to optimize (i) the number of boxes used, (ii) the average initial heat associated with each box, and (iii) the maximum time taken to move all boxes to the storefront. This problem is addressed through an adaptive multi-objective scatter search applied to a special dynamic bin packing problem. The method begins by constructing an initial Pareto front set, specifically, the initial reference set containing diversified solutions based on the three objective functions related to the studied problem. The subsequent stages of the method operate in three collaborative phases: (i) improving the reference set by optimizing a highlighted objective function, (ii) refining the final reference set by prioritizing the optimization of average initial heat, and (iii) addressing the objective related to the maximum time to establish the final solution. Hence, to facilitate the transition between the aforementioned three phases, a hybridization between the solution combination method and the reference update method is introduced. Finally, the proposed method’s performance is evaluated using benchmark and newly generated instances and compared with recent methods. The study includes both qualitative and quantitative analyses. To identify the best-performing method among those tested, three statistical tests are conducted: the Student’s t-test, the Sign test, and the Wilcoxon signed-rank test. Additionally, performance metrics such as the ε -test, the binary coverage measure, and the net front contribution indicator are used for evaluation. The results achieved by the proposed method surpass those published in the literature, highlighting the method’s strength and effectiveness, and establishing it as a competitive solution for the dynamic multi-objective bin-packing problem.