GeoNest improves packing efficiency for irregular shapes in circular containers
GeoNest: Learning to Select Failure-Aware Neighborhoods for the Irregular Knapsack Problem in a Circular Container
Machine LearningArtificial Intelligence
Summary
Packing oddly shaped objects into a round container is a tricky problem because leftover spaces often become too small for remaining pieces. The authors propose GeoNest, a new method that learns to focus on tricky problem areas by pairing leftover shapes with leftover spaces that caused prior packing failures. GeoNest then figures out which placed pieces block new placements and chooses the best areas to fix with a geometric solver. Their tests show that GeoNest packs shapes more efficiently than existing methods, including on real industrial designs.
What this means in practice
- •For manufacturing planners: Improve material usage by better arranging cutting layouts for irregular parts in circular sheets or blanks.
- •For industrial design engineers: Enhance automated placement tools to reduce waste when fitting complex shapes into constrained round areas.
Authors
Zhongman Du, Huiming Zhang, Linlin Yang, Sheng Xu, Baochang Zhang
Abstract
The two-dimensional irregular knapsack problem in a fixed circular container is an important combinatorial optimization problem for maximizing material utilization in manufacturing. Conventional geometric packing solvers can produce tightly packed layouts, yet they often partition the residual space into isolated small pockets that cannot fit valuable unplaced polygons. To overcome this late-stage packing bottleneck, we propose a failure-aware large neighborhood search framework named GeoNest, driven by a graph policy trained via reinforcement learning. Specifically, we first construct neighborhoods by pairing failed target polygons with residual pockets. We then use explanatory poses to identify the placed polygons that block candidate insertions. These diagnosed blocking relations define bounded, fixed-item repair subproblems for the underlying geometric solver. Finally, the graph policy selects the most promising subproblem for execution. For evaluation, we introduce CircleNest-Bench, a benchmark comprising 2,391 load-controlled instances from four contour sources, including a held-out industrial CAD source. Experimental results demonstrate that, under the same total time budget, GeoNest improves mean utilization over a state-of-the-art standalone packing solver by about 0.9% on average across the three main test sets and by about 0.6% on the held-out industrial set.