A best-first branch and bound algorithm for the pallet-loading problem

S. Ahn, K. Yoon and J. Park

International Journal of Production Research, 2015, vol. 53, issue 3, 835-849

Abstract: In this study, we proposed an optimal algorithm for the pallet-loading problem (PLP). The PLP involves determining a loading pattern that can load the most identical boxes with rectangular shapes onto a large rectangular pallet. A new branch and bound algorithm, including a sub-algorithm that cheques the feasibility of the solutions, was proposed to solve a relaxed mathematical model, which did not consider the exact position of the boxes. Because the algorithm constructed the layout row-by-row and used effective branching strategies and improved bounds, it found a solution very quickly. Whenever a solution was obtained for the relaxed problem, another branch and bound algorithm (as a sub-algorithm) was used to check whether the solution obtained was feasible and to determine the resulting layout. The branching strategies in the sub-algorithm used the solution from the relaxation problem to quickly find the layout of the solution. The computational results demonstrated the superiority of the proposed algorithm. The algorithm proposed in this study solved all three million problems presented with an area ratio bound of less than 101 boxes in a minute, except for one. Solutions to all of the problems were obtained within 90 s, while other existing exact algorithms required more than an hour for some problems.

Date: 2015
References: Add references at CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2014.935824 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tprsxx:v:53:y:2015:i:3:p:835-849

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2014.935824

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().