A new iterative-doubling Greedy-Lookahead algorithm for the single container loading problem
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
Original language | English |
---|---|
Pages (from-to) | 408-417 |
Journal / Publication | European Journal of Operational Research |
Volume | 222 |
Issue number | 3 |
Publication status | Published - 1 Nov 2012 |
Link(s)
Abstract
The aim of the Single Container Loading Problem (SCLP) is to pack three-dimensional boxes into a three-dimensional container so as to maximize the volume utilization of the container. We propose a new block building approach that constructs packings by placing one block (of boxes) at a time until no more boxes can be loaded. The key to obtaining high quality solutions is to select the right block to place into the right free space cuboid (or residual space) in the container. We propose a new heuristic for evaluating the fitness of residual spaces, and use a tree search to decide the best residual space-block pair at each step. The resultant algorithm outperforms the best known algorithms based on the 1600 commonly used benchmark instances even when given fewer computational resources. We also adapted our approach to address the full support constraint. The computational results for the full support support variant on the 1600 instances similarly show a significant improvement over existing techniques even when given substantially fewer computational resources. © 2012 Elsevier B.V. All rights reserved.
Research Area(s)
- 3D packing, Block building, Packing, Tree search
Citation Format(s)
A new iterative-doubling Greedy-Lookahead algorithm for the single container loading problem. / Zhu, Wenbin; Lim, Andrew.
In: European Journal of Operational Research, Vol. 222, No. 3, 01.11.2012, p. 408-417.
In: European Journal of Operational Research, Vol. 222, No. 3, 01.11.2012, p. 408-417.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review