Efficient Approaches for the Single Cylindrical Packing Problem with Cylindrical Items

Packing problems are a type of fundamental global optimization problem with many real-world applications. In this paper, we propose a new variant of three-dimensional (3D) packing problem, called the Single Cylindrical Packing Problem with Cylindrical Items (SCPP-CI), which involves packing as many cylindrical items as possible into a cylindrical container so as to maximize volume utilization. We design a Corner Occupying Action (COA) operator for SCPP-CI to obtain dense placement solutions, and design a Compact Level Degree (CLD) metric to evaluate the quality of feasible COAs. Two deterministic heuristic algorithms based on the COA operator and CLD metric are proposed to solve this problem, a CLD Construction algorithm (CLDC) and a top-$N$ CLD Local Search algorithm (CLDLS). To utilize existing resources to evaluate the performance of our proposed algorithms, we first degrade the 3D SCPP-CI problem to a two-dimensional (2D) circle packing problem and compare CLDC and CLDLS with the general CPLEX exact solver and the state-of-the-art unequal circle packing heuristic, FSS, on existing 2D benchmarks. We then generate 10 groups of SCPP-CI instances (100 instances in each group) with increasing heterogeneity, and compare CLDC and CLDLS with CPLEX. Experimental results show that both CLDC and CLDLS significantly outperform CPLEX for both 2D and 3D problems, and also significantly outperform the FSS baseline when solving the 2D unequal circle packing problem, indicating the excellent performance of our proposed methods