- author = "Edmund K. Burke and Matthew R. Hyde and Graham Kendall and John Woodward",
- title = "Automating the Packing Heuristic Design Process with Genetic Programming",
- journal = "Evolutionary Computation",
- year = "2012",
- volume = "20",
- number = "1",
- pages = "63--89",
- month = "Spring",
- keywords = "genetic algorithms, genetic programming, evolutionary design, cutting and packing, hyper-heuristicsn",
- ISSN = "1063-6560",
-
DOI = "
doi:10.1162/EVCO_a_00044",
-
URL = "
http://results.ref.ac.uk/Submissions/Output/944156",
- size = "25 pages",
-
abstract = "The literature shows that one, two and three
dimensional bin packing and knapsack packing are
difficult problems in Operational Research. Many
techniques, including exact, heuristic, and
metaheuristic approaches, have been investigated to
solve these problems and it is often not clear which
method to use when presented with a new instance. This
paper presents an approach which is motivated by the
goal of building computer systems which can design
heuristic methods. The overall aim is to explore the
possibilities for automating the heuristic design
process.
We present a genetic programming system to automatically generate a good quality heuristic for each instance. It is not necessary to change the methodology depending on the problem type (one, two or three dimensional knapsack and bin packing problems), and it therefore has a level of generality unmatched by other systems in the literature. We carry out an extensive suite of experiments and compare with the best human designed heuristics in the literature. Note that our heuristic design methodology uses the same parameters for all the experiments.
The contribution of this paper is to present a more general packing methodology than those currently available, and to show that, by using this methodology, it is possible for a computer system to design heuristics which are competitive with the human designed heuristics from the literature. This represents the first packing algorithm in the literature able to claim human competitive results in such a wide variety of packing domains.",
- uk_research_excellence_2014 = "This paper describes how to automatically develop 3D packing heuristics, which is relevant in many industrial areas where 3D physical objects need to be packed optimally into a confined space. This is the first attempt at automatically developing 3D packing heuristics. The results in this paper provided some of the foundation blocks and signposts for a new major EPSRC programme grant (EP/J017515/1) of pounds6.8M between UCL, Stirling, York and Birmingham, which started in 2012. This research has led to Woodward organising a workshop on the automated design of algorithms at the 2013 GECCO (Genetic and Evolutionary Computation Conference).",
