Random‐key optimization for 2D irregular packing with reusable area evaluation

Abstract

Abstract The diverse constraints of industrial applications lead to variants of two‐dimensional (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, to measure and maximize the contiguous unused area in a layout, thereby facilitating the reuse of remnant material. This study proposes an approach focused on optimizing placement policies. 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. Among the 15 benchmark 2D Irregular Knapsack Problem instances evaluated, RKO matched the best‐performing existing algorithm on 11 and achieved better solutions on the remaining 4. These results suggest that RKO is competitive with, and potentially superior to, this algorithm. RKO's results indicate that current benchmarks no longer adequately represent the problem, motivating the introduction of extended benchmark instances. RKO also outperforms leading 2D irregular strip packing problem (SPP) methods relying on constructive sequence search. Finally, comparing our method against the top SPP algorithm, which minimizes layout overlap, on real‐world MRCAP instances shows that RKO yields superior remnant quality in almost all problem cases. This demonstrates that minimizing layout width in SPP does not ensure effective remnant valorization, highlighting the distinction between these two optimization objectives.