Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/312489 
Year of Publication: 
2023
Citation: 
[Journal:] Journal of Intelligent Manufacturing [ISSN:] 1572-8145 [Volume:] 35 [Issue:] 6 [Publisher:] Springer US [Place:] New York, NY [Year:] 2023 [Pages:] 2811-2827
Publisher: 
Springer US, New York, NY
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.
Subjects: 
Reinforcement learning
Graph neural networks
Cutting and packing
Nesting
Geometrical compatibility
Geometrical relationship graph
Grouping for nesting
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.