The Three-Dimensional Bin Packing Problem

Silvano Martello (), David Pisinger and Daniele Vigo
Additional contact information
Silvano Martello: DEIS, University of Bologna, Viale Risorgimento 2, Bologna, Italy
David Pisinger: DIKU, University of Copenhagen, University Parken 1, Copenhagen, Denmark
Daniele Vigo: DEIS, University of Bologna, Viale Risorgimento 2, Bologna, Italy

Operations Research, 2000, vol. 48, issue 2, 256-267

Abstract: The problem addressed in this paper is that of orthogonally packing a given set of rectangular-shaped items into the minimum number of three-dimensional rectangular bins. The problem is strongly NP-hard and extremely difficult to solve in practice. Lower bounds are discussed, and it is proved that the asymptotic worst-case performance ratio of the continuous lower bound is 1/8. An exact algorithm for filling a single bin is developed, leading to the definition of an exact branch-and-bound algorithm for the three-dimensional bin packing problem, which also incorporates original approximation algorithms. Extensive computational results, involving instances with up to 90 items, are presented: It is shown that many instances can be solved to optimality within a reasonable time limit.

Keywords: Production/scheduling: cutting stock/trim; Transportation: freight/material handling; Programming: integer; branch-and-bound (search for similar items in EconPapers)
Date: 2000
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (80)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.48.2.256.12386 (application/pdf)

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:inm:oropre:v:48:y:2000:i:2:p:256-267

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().