Solving the Pallet Loading Problem

Loading...
Thumbnail Image
Authors
Martins, Gustavo H.A.
Dell, Robert F.
Subjects
packing
pallet loading
combinatorial optizmiation
Advisors
Date of Issue
2008
Date
2008
Publisher
Language
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 degrees 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 in 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.
Type
Article
Description
European Journal of Operational Research, 184, 2008, pp. 429-440.
The article of record as published may be located at http://dx.doi.org/10.1016/j.ejor.2006.11.012
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Martins, G.H.A. and R.F. Dell, “Solving the Pallet Loading Problem,” European Journal of Operational Research, 184, 2008, pp. 429-440.
Distribution Statement
Rights
defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections