Using helical polyhedron for online irregular strip packing problem with free rotations

Yulin Liu and Li Zheng

European Journal of Operational Research, 2025, vol. 327, issue 2, 407-419

Abstract: The packing of irregular pieces is widely applied across various industries including metalworking, woodworking, clothing manufacturing, and leather goods production. Allowing rotation during packing, particularly in scenarios where materials are homogeneous, can yield superior outcomes by reducing material wastage, thus contributing to cost-saving and environmental preservation. This study investigates the online irregular strip packing problem allowing free rotation, inspired by a leather handicraft workshop, where orders arrive infrequently and vary widely in content. The objective is to minimize the sheet length utilized. Most existing literature models irregular strip packing problem with rotation as a nonlinear programming problem, making it challenging to obtain the optimal position and orientation of every single input piece despite advancements in optimization solvers. In this paper, a novel approach is proposed to solve online irregular strip packing problem with rotation. We rotate the input polygon while simultaneously translating it along the z-axis, forming a helix. Thus, the problem of selecting the rotation angle is transformed into determining the z-coordinate of the helix’s cross-section. Subsequently, meshing the helix into a polyhedron allows us to propose a mixed integer linear formulation based on its Minkowski sum with other polygons. To ensure guaranteed optimality, we introduce a branch-and-bound algorithm tailored to the problem. Extensive numerical experiments indicate the effectiveness and competitiveness of our algorithm over state-of-the-art nonlinear formulations for irregular strip packing problem with rotation.

Keywords: Irregular strip packing; Rotation; Helical polyhedron; Bottom-left strategy; Branch-and-bound (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S037722172500387X
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:327:y:2025:i:2:p:407-419

DOI: 10.1016/j.ejor.2025.05.019

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 ().