Dynamic feedback algorithm based on spatial corner fitness for solving the three-dimensional multiple bin-size bin packing problem

Yi Liu

doi:10.1007/s40747-024-01368-5

2024-03-01

Yi Liu

Xiaoyun Jiang *

DOI：10.1007/s40747-024-01368-5

原文链接

原文求助

摘要

En 中文

To improve cargo loading efficiency and achieve diverse needs of companies for the loading process, this paper innovatively establishes a multiple objective mixed integer programming model for the three-dimensional multiple bin-size bin packing problem (3D-MBSBPP). The model is designed to maximize container space utilization rate and cargo load balance, minimize container usage costs, and incorporates some practical constraints. On this basis, we propose a novel dynamic feedback algorithm based on spatial corner fitness (SCF_DFA) to solve this model, which consists of three stages. Specifically, Stage 1 employs a heuristic algorithm based on spatial corner fitness to optimize the search of the remaining spaces. Stage 2 employs a container type selection algorithm to dynamically adjust and optimize container types. Stage 3 uses an improved genetic algorithm to improve the quality of the solutions of the first two stages. We demonstrate the effectiveness of the proposed algorithm through comparative experiments on benchmark instances, and apply it to solve the real-life instances for the 3D-MBSBPP. The results show that the proposed algorithm can make the average container space utilization rate reach 85.38%, which is 1.48% higher than that of baseline method, while the loading results obtained are more balanced, indicating the advantages of the SCF_DFA in solving 3D-MBSBPP. Furthermore, we conduct ablation experiments to confirm the effectiveness of each component within the algorithm.

Keyword:

Three-dimensional multiple bin-size bin packing problem

Multiple objective mixed integer programming model

Spatial corner fitness assessment strategy

Dynamic feedback algorithm

Improved genetic algorithm