- author = "Sam D. Allen",
- title = "Algorithms and data structures for three-dimensional packing",
- school = "School of Computer Science, University of Nottingham",
- year = "2011",
- address = "UK",
- month = jul,
- keywords = "genetic algorithms, genetic programming, packing, shipment, business, operations research",
-
URL = "
http://etheses.nottingham.ac.uk/2779/1/thesis_nicer.pdf",
- size = "123 pages",
-
abstract = "Cutting and packing problems are increasingly
prevalent in industry. A well used freight vehicle will
save a business money when delivering goods, as well as
reducing the environmental impact, when compared to
sending out two lesser-used 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. 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.",
-
notes = "Supervisors: Edmund K. Burke and Graham Kendall
ID Code: 2779",
