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

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

56 Scopus Citations
View graph of relations

Author(s)

  • Wenbin Zhu
  • Andrew Lim

Related Research Unit(s)

Detail(s)

Original languageEnglish
Pages (from-to)408-417
Journal / PublicationEuropean Journal of Operational Research
Volume222
Issue number3
Publication statusPublished - 1 Nov 2012

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