Automating the Packing Heuristic Design Process with Genetic Programming

Created by W.Langdon from gp-bibliography.bib Revision:1.4496

  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 =          "",
  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

                 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).",

Genetic Programming entries for Edmund Burke Matthew R Hyde Graham Kendall John R Woodward