Algorithms and data structures for three-dimensional packing

Allen, Sam D. (2011) Algorithms and data structures for three-dimensional packing. PhD thesis, University of Nottingham.

[img]
Preview
PDF
1471Kb

Abstract

Cutting and packing problems are increasingly prevalent in industry. A well utilised freight vehicle will save a business money when delivering goods, as well as reducing the environmental impact, when compared to sending out two lesser-utilised freight vehicles. A cutting machine that generates less wasted material will have a similar effect. Industry reliance on automating these processes and improving productivity is increasing year-on-year.

This thesis presents a number of methods for generating high quality solutions for these cutting and packing challenges. It does so in a number of ways. A fast, efficient framework for heuristically generating solutions to large problems is presented, and a method of incrementally improving these solutions over time is implemented and shown to produce even higher packing utilisations. The results from these findings provide the best known results for 28 out of 35 problems from the literature. This framework is analysed and its effectiveness shown over a number of datasets, along with a discussion of its theoretical suitability for higher-dimensional packing problems. A way of automatically generating new heuristics for this framework that can be problem specific, and therefore highly tuned to a given dataset, is then demonstrated and shown to perform well when compared to the expert-designed packing heuristics. Finally some mathematical models which can guarantee the optimality of packings for small datasets are given, and the (in)effectiveness of these techniques discussed. The models are then strengthened and a novel model presented which can handle much larger problems under certain conditions. The thesis finishes with a discussion about the applicability of the different approaches taken to the real-world problems that motivate them.

Item Type:Thesis (PhD)
Supervisors:Burke, E.K.
Kendall, G.
Uncontrolled Keywords:packing, shipment, business, operations research
Faculties/Schools:UK Campuses > Faculty of Science > School of Computer Science
ID Code:2779
Deposited By:Dr Sam D. Allen
Deposited On:05 Sep 2012 15:27
Last Modified:05 Sep 2012 15:27

Archive Staff Only: item control page