Smart nesting: estimating geometrical compatibility in the nesting problem using graph neural networks

Kirolos Abdou (), Osama Mohammed (), George Eskandar (), Amgad Ibrahim (), Paul-Amaury Matt () and Marco F. Huber ()
Additional contact information
Kirolos Abdou: TRUMPF Werkzeugmaschinen SE + Co. KG
Osama Mohammed: University of Stuttgart
George Eskandar: University of Stuttgart
Amgad Ibrahim: TRUMPF Werkzeugmaschinen SE + Co. KG
Paul-Amaury Matt: Fraunhofer Institute for Manufacturing Engineering and Automation IPA
Marco F. Huber: Fraunhofer Institute for Manufacturing Engineering and Automation IPA

Journal of Intelligent Manufacturing, 2024, vol. 35, issue 6, No 19, 2827 pages

Abstract: Abstract Reducing material waste and computation time are primary objectives in cutting and packing problems (C &P). A solution to the C &P problem consists of many steps, including the grouping of items to be nested and the arrangement of the grouped items on a large object. Current algorithms use meta-heuristics to solve the arrangement problem directly without explicitly addressing the grouping problem. In this paper, we propose a new pipeline for the nesting problem that starts with grouping the items to be nested and then arranging them on large objects. To this end, we introduce and motivate a new concept, namely the Geometrical Compatibility Index (GCI). Items with higher GCI should be clustered together. Since no labels exist for GCIs, we propose to model GCIs as bidirectional weighted edges of a graph that we call geometrical relationship graph (GRG). We propose a novel reinforcement-learning-based framework, which consists of two graph neural networks trained in an actor-critic-like fashion to learn GCIs. Then, to group the items into clusters, we model the GRG as a capacitated vehicle routing problem graph and solve it using meta-heuristics. Experiments conducted on a private dataset with regularly and irregularly shaped items show that the proposed algorithm can achieve a significant reduction in computation time (30% to 48%) compared to an open-source nesting software while attaining similar trim loss on regular items and a threefold improvement in trim loss on irregular items.

Keywords: Reinforcement learning; Graph neural networks; Cutting and packing; Nesting; Geometrical compatibility; Geometrical relationship graph; Grouping for nesting (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10845-023-02179-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joinma:v:35:y:2024:i:6:d:10.1007_s10845-023-02179-0

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10845

DOI: 10.1007/s10845-023-02179-0

Access Statistics for this article

Journal of Intelligent Manufacturing is currently edited by Andrew Kusiak

More articles in Journal of Intelligent Manufacturing from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().