Solving the Pallet Loading Problem

Abstract

This paper presents new bounds, heuristics, and an exact algorithm for the Pallet Loading Problem (PLP). PLP maximizes the number of boxes placed on a rectangular pallet. All boxes have identical rectangular dimensions and, when placed, must be located completely within the pallet. Boxes may be rotated 90 so long as they are placed with edges parallel to the pallet's edges. The set of all PLP instances with an area ratio (pallet area divided by box area) less than 101 boxes can be represented by 3,080,730 equivalent classes. Our G5-heuristic finds optimal solutions to 3,073,724 of these 3,080,730 classes and in the remaining 7006 classes only differs from the best known bound by one box. We develop three other heuristics that solve another 54 instances. Finally, we solve the 6952 remaining classes with our exact HVZ algorithm. Only a subset of these classes has been solved previously.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2008
Accession Number
ADA517366

Entities

People

  • Gustavo H. Martins
  • Robert F. Dell

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computations
  • Computer Programming
  • Computers
  • Coordinate Systems
  • Databases
  • Electronic Mail
  • Information Operations
  • Information Systems
  • Linear Programming
  • Mathematics
  • Operations Research
  • Orientation (Direction)
  • Personal Computers
  • Systems Analysis
  • Trees (Data Structures)
  • Two Dimensional

Fields of Study

  • Computer science

Readers

  • Graph Algorithms and Convex Optimization.
  • Logistics and Supply Chain Management.
  • Operations Research