Article ID: | iaor20122440 |
Volume: | 220 |
Issue: | 1 |
Start Page Number: | 37 |
End Page Number: | 47 |
Publication Date: | Jul 2012 |
Journal: | European Journal of Operational Research |
Authors: | Lim Andrew, Zhu Wenbin, Oon Wee-Chong, Wei Lijun |
Keywords: | heuristics |
In the three‐dimensional strip packing problem (3DSP), we are given a container with an open dimension and a set of rectangular cuboids (boxes) and the task is to orthogonally pack all the boxes into the container such that the magnitude of the open dimension is minimized. We propose a block building heuristic based on extreme points for this problem that uses a reference length to guide its solution. Our 3DSP approach employs this heuristic in a one‐step lookahead tree search algorithm using an iterative construction strategy. We tested our approach on standard 3DSP benchmark test data; the results show that our approach produces better solutions on average than all other approaches in literature for the majority of these data sets using comparable computation time.