This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Crainic, T. G. Articles by Tadei, R. Search for Related Content

Extreme Point-Based Heuristics for Three-Dimensional Bin Packing

Département de management et technologie and Centre Interuniversitaire de Recherche sur les Réseaux d'Entreprise, la Logistique et le Transport, ESG, U.Q.A.M., Montréal, Québec, Canada H3C 3P8
Department of Control and Computer Engineering, Politecnico di Torino, 10129, Torino, Italy
Department of Control and Computer Engineering, Politecnico di Torino, 10129, Torino, Italy
theo{at}crt.umontreal.ca
guido.perboli{at}polito.it
roberto.tadei{at}polito.it

One of the main issues in addressing three-dimensional packing problems is finding an efficient and accurate definition of the points at which to place the items inside the bins, because the performance of exact and heuristic solution methods is actually strongly influenced by the choice of a placement rule. We introduce the extreme point concept and present a new extreme point-based rule for packing items inside a three-dimensional container. The extreme point rule is independent from the particular packing problem addressed and can handle additional constraints, such as fixing the position of the items. The new extreme point rule is also used to derive new constructive heuristics for the three-dimensional bin-packing problem. Extensive computational results show the effectiveness of the new heuristics compared to state-of-the-art results. Moreover, the same heuristics, when applied to the two-dimensional bin-packing problem, outperform those specifically designed for the problem.

Key words: programming; integer; algorithms; heuristic; three-dimensional packing; bin packing
History: received June 2006; revised March 2007; accepted September 2007.