A Cost Effective Two-Step Exploration for Constrained Two-Dimensional Packing Problems

A combinatorial optimization problem, particularly an NP-hard challenge, aims to find an optimal solution within a discrete search space and has been applied across diverse industries. However, practical use-cases often involve numerous constraints, making the optimization problem significantly more complex as the search space expands. To address this issue, this paper presents a new methodology that efficiently solves two-dimensional bin packing problems with multiple constraints. We propose a two-step exploration technique, consisting of combination and permutation, and apply it to the practical design of LNG vessels. The proposed methodology not only enhances efficiency in search time and space but also ensures the discovery of global optimal solutions without requiring additional exploration. Our results demonstrate remarkable improvements in both time and spatial efficiency compared to brute-force global searches. The methodology proposed in this paper is expected to contribute significantly to technological advancements in solving combinatorial optimization problems.