A new iterative-doubling Greedy–Lookahead algorithm for the single container loading problem

Wenbin Zhu and Andrew Lim

European Journal of Operational Research, 2012, vol. 222, issue 3, 408-417

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.

Keywords: Packing; 3D packing; Block building; Tree search (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (13)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221712003529
Full text for ScienceDirect subscribers only

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:eee:ejores:v:222:y:2012:i:3:p:408-417

DOI: 10.1016/j.ejor.2012.04.036

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().