Voxel-Based Solution Approaches to the Three-Dimensional Irregular Packing Problem

Carlos Lamas-Fernandez (), Julia A. Bennell () and Antonio Martinez-Sykora ()
Additional contact information
Carlos Lamas-Fernandez: Centre for Operational Research, Management Science and Information Systems (CORMSIS), Southampton Business School, University of Southampton, Southampton, SO17 1BJ, United Kingdom
Julia A. Bennell: Centre for Decision Research, Leeds University Business School, University of Leeds, Leeds, LS2 9JT, United Kingdom
Antonio Martinez-Sykora: Centre for Operational Research, Management Science and Information Systems (CORMSIS), Southampton Business School, University of Southampton, Southampton, SO17 1BJ, United Kingdom

Operations Research, 2023, vol. 71, issue 4, 1298-1317

Abstract: Research on the three-dimensional (3D) packing problem has largely focused on packing boxes for the transportation of goods. As a result, there has been little focus on packing irregular shapes in the operational research literature. New technologies have raised the practical importance of 3D irregular packing problems and the need for efficient solutions. In this work, we address the variant of the problem where the aim is to place a set of 3D irregular items in a container, while minimizing the container height, analogous to the strip packing problem. In order to solve this problem, we need to address two critical components; efficient computation of the geometry and finding high-quality solutions. In this work, we explore the potential of voxels, the 3D equivalent of pixels, as the geometric representation of the irregular items. In this discretised space, we develop a geometric tool that extends the concept of the nofit polygon to the 3D case. This enables us to provide an integer linear programming formulation for this problem that can solve some small instances. For practical size problems, we design metaheuristic optimisation approaches. Because the literature is limited, we introduce new benchmark instances. Some are randomly generated and some represent realistic models from the additive manufacturing area. Our results on the literature benchmark data and on our new instances show that our metaheuristic techniques achieve the best known solutions for a wide variety of problems in practical computation times.

Keywords: Optimization; 3D irregular packing; open dimension problem; voxel; metaheuristics (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2260 (application/pdf)

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:inm:oropre:v:71:y:2023:i:4:p:1298-1317

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().