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

• 成果类型: Article
• 署名作者: Lamas-Fernandez, Carlos; Bennell, Julia A.; Martinez-Sykora, Antonio
• 署名单位: University of Southampton; Solent University; University of Leeds
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2260
• 发表日期: 2023
• 页码: 1298-1317
• 关键词: 3D irregular packing; open dimension problem; voxel; metaheuristics

摘要

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 meta-heuristic techniques achieve the best known solutions for a wide variety of problems in practical computation times.