A three-dimensional bin-packing model: exact multicriteria solution and computational complexity

Gregory S. Taylor, Yupo Chan () and Ghulam Rasool ()
Additional contact information
Yupo Chan: University of Arkansas at Little Rock
Ghulam Rasool: Northwestern University

Annals of Operations Research, 2017, vol. 251, issue 1, No 23, 397-427

Abstract: Abstract The three-dimensional or vector bin-packing problem is reexamined, in which the least number of bins is determined to accommodate p items to be packed. An exact analytical mixed-integer-programming formulation is offered to pack items by layers, while considering the layer height at the same time. Relaxation of the model is shown to yield the linear-programming bound advanced by Federgruen and Van Ryzin for heuristic solution to the multi-dimensional bin-packing problem. When the items to be packed are arranged in non-increasing order by height or by volume, this lower bound is shown to be of computational complexity $${ O(p)}$$ O ( p ) , both theoretically and computationally. Since ours is an exact solution rather than a heuristic solution, the bound is perfectly tight, thus mitigating the worries about the magnitude of error bounds. The linear computational complexity suggests that our analytical model can be solved efficiently irrespective of the number of items to be packed. At the same time, extensive computation using a layer-by-layer dynamic-programming heuristic by Hodgson, the Interactive Pallet Loading System (IPLS), corroborated the Federgruen and Van Ryzin lower bound as well. Limited computational results from the analytical model also validated the IPLS heuristic solution. A novel feature of the analytical model is that it yields Pareto optima, rather than a single optimum. This allows decision-makers to choose among the non-dominated solutions in consideration of other soft factors in bin packing. When the multicriteria model is executed in an interactive manner, it is able to consider considerations such as center-of-gravity and ease of unloading.

Keywords: Pallet loading; Multi-dimensional packing; Bi-criteria knapsack problem; Computational bound; Air Force logistics (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-015-2048-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:annopr:v:251:y:2017:i:1:d:10.1007_s10479-015-2048-5

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-015-2048-5

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().