How to Pack Trapezoids: Exact and Evolutionary Algorithms

Rhydian Lewis, Penny Holborn

Research output: Contribution to journalArticlepeer-review

91 Downloads (Pure)

Abstract

The purposes of this paper are twofold. In the first, we describe an exact polynomial-time algorithm for the pair sequencing problem and show how this method can be used to pack fixed-height trapezoids into a single bin such that interitem wastage is minimised. We then go on to examine how this algorithm can be combined with bespoke evolutionary and local search methods for tackling the multiple-bin version of this problem—one that is closely related to one-dimensional bin packing. In the course of doing this, a number of ideas surrounding recombination, diversity, and genetic repair are also introduced and analysed.
Original languageEnglish
Pages (from-to)463-476
Number of pages15
JournalIEEE Transactions on Evolutionary Computation
Volume21
Issue number3
DOIs
Publication statusPublished - 13 Sep 2016

Keywords

  • Diversity
  • Trapezoid Packing
  • Bin Packing
  • Pair Sequencing Problem
  • Recombination
  • Sequential Analysis

Fingerprint

Dive into the research topics of 'How to Pack Trapezoids: Exact and Evolutionary Algorithms'. Together they form a unique fingerprint.

Cite this