Random-Key Optimization for 2D Irregular Packing with Reusable Area Evaluation

The diverse constraints of industrial applications lead to variants of 2D irregular packing problems that require tailored solution methods. This paper addresses a real-world industrial challenge by proposing a new problem definition, the Maximum Reusable Contiguous Area Problem (MRCAP), and a novel metric, the Maximum Contiguous Area, developed to measure and maximize the contiguous unused area of a layout, facilitating the reuse of remnant material. This study proposes an approach focused on placement policy optimization. We develop a decoder, implemented within a new version of the Random-Key Optimizer (RKO) framework, that dynamically assigns the best placement rule from an 11-heuristic portfolio. We validate our methodology on established literature benchmarks. On the 15 benchmark 2D Irregular Knapsack Problem instances considered, RKO matched the best-performing existing algorithm on 11 instances and obtained better solutions on the remaining 4 instances. These results suggest that RKO is at least competitive with, and potentially superior to, this algorithm on this test set. RKO’s results indicate that current benchmarks no longer adequately represent the 2D Irregular Knapsack Problem, motivating the introduction of extended benchmark instances. RKO’s results outperform the best-performing SPP methods that rely on constructive sequence search. Then, we compare our method against the leading SPP algorithm, which optimizes layouts (overlap minimization), using real-world MRCAP instances. The results show that the new RKO yields superior remnant quality in almost all problem cases. These results indicate that minimizing layout width in SPP does not ensure effective remnant valorization, highlighting the distinction between these two optimization objectives.

Article

Download

View PDF