A fast algorithm for two-dimensional pallet loading problems of large size

This paper concerns the two-dimensional pallet loading problem (PLP), which requires the determination of the orthogonal layout that loads the maximum number of identical small rectangles (i.e., boxes or products) onto a large rectangle (i.e., pallet or container) without overlapping. Although many...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2001-10, Vol.134 (1), p.193-202
Main Authors: G, Young-Gun, Kang, Maing-Kyu
Format: Article
Language:English
Subjects:
Algorithms
Heuristic
Heuristics
Packaging
Packing
Pallet loading
Pallets
Studies
Two-dimensional
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper concerns the two-dimensional pallet loading problem (PLP), which requires the determination of the orthogonal layout that loads the maximum number of identical small rectangles (i.e., boxes or products) onto a large rectangle (i.e., pallet or container) without overlapping. Although many algorithms have been developed for this problem, the large amount of time required to find efficient layouts for a large PLP presents great practical difficulties. In this paper, we develop a heuristic that finds efficient layouts with low complexity. We also propose a new algorithm, using the heuristic as a sub-algorithm, which rapidly finds complicated solutions having a 5-block structure. Finally, computational results show that the new algorithm can be successfully applied to large PLPs with sizes exceeding 6800 boxes.
ISSN:0377-2217
1872-6860
DOI:10.1016/S0377-2217(00)00249-6