Back to search

University of Southampton

From archaeology to 3D printing: packing problems in the three dimensions

Abstract

dc:description.abstract

This thesis is a study on three cutting and packing problems involving irregular items. These problems are highly relevant in areas such as transportation, additive manufacturing or the garment industry. We investigate a special type of one-dimensional bin packing problem appearing in the industry; a novel problem in two dimensions entailing irregular shapes and free rotations; and an open dimension problem in three dimensions. Our aims are to find strategies to deal with irregular shapes, particularly geometric tools, and solution methods for problems with unusual constraints.<br/><br/>In the first part we look at an industrial problem related to the management of helicopter fleets. We model and test with realistic data a bin packing problem where the objective is to find the minimum aircraft needed to lift a collection of items. The characteristics of this problem allow us to relax the geometrical constraints and consider it as a variant of the one-dimensional bin packing problem, but its many problem specific constraints make this a multi-objective that, to the best of our knowledge, is new in the literature.<br/><br/>In the second part, we deal with a novel problem in two dimensions, motivated by the deciphering of an ancient Aztec codex. The problem itself is a novel packing problem with irregular shapes, an irregular container, free rotation and with the overlap and containment constraints relaxed. We provide a constructive algorithm and a metaheuristic procedure that are able to find satisfying solutions for an open question in the deciphering of the codex.<br/><br/>Finally, in the last part we treat three-dimensional irregular shapes. We adopt a discretised approach that allows us to generate quick intersection tests and we develop the no-fit voxel. This is an extension of the no-t polygon, a mainstream tool for two dimensional packing problems that had not been extended to three dimensions in the literature. Using this tool, we investigate local search neighbourhoods and metaheuristic algorithms to find efficient packings and are able to provide an ILP model based on the no-fit voxel to locally improve the packing layouts.

Degree

thesis:*
Name dc:type.qualificationname
Ph.D.
Level dc:type.qualificationlevel
doctoral
Grantor dc:publisher.institution
University of Southampton
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Lamas Fernandez, Carlos
Advisor dc:contributor.advisor
  • Bennell, Julia A.

Rights

Language dc:language
English, eng

Chain of custody

source
Harvested from
University of Southampton
Base URL
eprints.soton.ac.uk/cgi/oai2
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Lamas Fernandez, Carlos. From archaeology to 3D printing: packing problems in the three dimensions. doctoral thesis, University of Southampton, 2018.