Research Repository

Three-dimensional bin packing problem with variable bin height

Wu, Yong and Li, Wenkai and Goh, Mark and de Souza, Robert (2009) Three-dimensional bin packing problem with variable bin height. European Journal of Operational Research, 202 (2). pp. 347-355. ISSN 0377-2217

Full text for this resource is not available from the Research Repository.

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 3DBPP. 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.

Item Type: Article
Uncontrolled Keywords: ResPubID17483, bin packing, mixed integer programming, optimization, genetic algorithms, batch bin packing, three-dimensional
Subjects: Faculty/School/Research Centre/Department > Institute for Logistics and Supply Chain Management (ILSCM)
FOR Classification > 0102 Applied Mathematics
SEO Classification > 8902 Computer Software and Services
Related URLs:
Depositing User: VUIR
Date Deposited: 26 Sep 2011 23:58
Last Modified: 26 Sep 2011 23:58
URI: http://vuir.vu.edu.au/id/eprint/4702
DOI: 10.1016/j.ejor.2009.05.040
ePrint Statistics: View download statistics for this item
Citations in Scopus: 27 - View on Scopus

Repository staff only

View Item View Item

Search Google Scholar