A new approach for bin packing problem using knowledge reuse and improved heuristic

The two-dimensional (2D) irregular packing problem is a combinatorial optimization problem with NP-complete characteristics, which is common in the production process of clothing, ships, and plate metals. The classic packing solution is a hybrid algorithm based on heuristic positioning and meta-heuristic sequencing, which has the problems of complex solving rules and high time cost. In this study, the similarity measurement method based on the twin neural network model is used to evaluate the similarity of pieces in the source task and the target task. The reusability evaluation of packing tasks is designed to select appropriate source task knowledge. The transfer operator is used to transfer the piece sequence knowledge from the source task to complete the reuse of packing knowledge in the target task. The bottom-left algorithm is improved to complete the placement of 2D irregular pieces. The computational experiments show that the proposed algorithm for the bin packing problem using knowledge reuse and improved heuristic (KRIH) has good robustness. The KRIH algorithm can obtain 8 equal or better results on 16 instances in a relatively short time compared with some classical heuristic algorithms, which has good application potential.