An extended model formulation for the two-dimensional irregular strip packing problem considering general industry-relevant aspects

Alf Kimms and Hédi Király

European Journal of Operational Research, 2023, vol. 306, issue 3, 1202-1218

Abstract: Two-dimensional cutting and packing problems including irregular items (nesting problems) are common, e.g., in the clothing, paper, glass and leather industries. In the irregular strip packing problem considered in this work a finite number of rotations of convex as well as non-convex polygons with and without holes are permitted. To deal with the geometry of irregular items, direct trigonometry is applied. The focus is on aspects and characteristics that are typical for many affected industries and have been neglected so far. In the mentioned sectors, it is conceivable that items can be created from smaller parts by assembling them using various techniques. There might be several possible combinations of parts to be joined together to result in the desired item, i.e., there might be several cutting patterns to choose from. Also, whether the large material, i.e., large object is single-colored or has a particular structure or design is of great importance. In the latter case, special attention must be paid to the rotation of certain items or parts in order to achieve the desired (uniform or non-uniform) appearance of the final product. The utilized data structure is introduced, to address the mentioned aspects in the presented mixed-integer linear model which is an extension of a formulation published by previous authors. Furthermore, the method of calculating “critical vertices” is introduced, which requires only a reduced number of comparisons between edges and vertices of two items to ensure overlap-free positioning. Industry-relevant examples are highlighted in the computational study to illuminate the versatility of the model.

Keywords: Packing; Cutting; Nesting problem; Irregular strip packing problem; Direct trigonometry (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722006403
Full text for ScienceDirect subscribers only

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:eee:ejores:v:306:y:2023:i:3:p:1202-1218

DOI: 10.1016/j.ejor.2022.07.050

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().