Three-dimensional bin packing problem with variable bin height

File Size Format
64978_1.pdf 231Kb Adobe PDF View
Title Three-dimensional bin packing problem with variable bin height
Author Wu, Yong; Li, Wenkai; Goh, Mark; Souza, Robert de
Journal Name European Journal of Operational Research
Year Published 2010
Place of publication Netherlands
Publisher Elsevier
Abstract This paper studies a variant of the three-dimensional bin packing problem (3D-BPP), where the bin height can be adjusted to the cartons it packs. The bins and cartons to be packed are assumed rectangular in shape. The cartons are allowed to be rotated into any one of the six positions that keep the carton edges parallel to the bin edges. This greatly increases the difficulty of finding a good solution since the search space expands significantly comparing to the 3D-BPP where the cartons have fixed orientations. A mathematical (mixed integer programming) approach is modified based on [Chen, C. S., Lee, S. M., Shen, Q. S., 1995. An analytical model for the container loading problem. European Journal of Operational Research 80 (1), 68–76] and numerical experiments indicate that the mathematical approach is not suitable for the variable bin height 3D-BPP. A special bin packing algorithm based on packing index is designed to utilize the special problem feature and is used as a building block for a genetic algorithm designed for the 3D-BPP. The paper also investigates the situation where more than one type of bin are used and provides a heuristic for packing a batch of cartons using the genetic algorithm. Numerical experiments show that our proposed method yields quick and satisfactory results when benchmarked against the actual packing practice and the MIP model with the latest version of CPLEX.
Peer Reviewed Yes
Published Yes
Alternative URI http://dx.doi.org/10.1016/j.ejor.2009.05.040
Copyright Statement Copyright 2010 Elsevier. This is the author-manuscript version of this paper. Reproduced in accordance with the copyright policy of the publisher. Please refer to the journal's website for access to the definitive, published version.
Volume 202
Issue Number 2
Page from 347
Page to 355
ISSN 0377-2217
Date Accessioned 2010-10-20
Date Available 2011-05-11T07:21:37Z
Language en_AU
Research Centre Institute for Integrated and Intelligent Systems
Faculty Griffith Business School
Subject Combinatorics and Discrete Mathematics (excl Physical Combinatorics); Optimisation
URI http://hdl.handle.net/10072/34843
Publication Type Journal Articles (Refereed Article)
Publication Type Code c1x

Show simple item record

Griffith University copyright notice