A reference length approach for the 3D strip packing 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) | 37-47 |
Journal / Publication | European Journal of Operational Research |
Volume | 220 |
Issue number | 1 |
Publication status | Published - 1 Jul 2012 |
Link(s)
Abstract
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. © 2012 Elsevier B.V. All rights reserved.
Research Area(s)
- Best-fit heuristic, Combinatorial optimization, Greedy algorithm, Look-ahead, Packing, Tree search
Citation Format(s)
A reference length approach for the 3D strip packing problem. / Wei, Lijun; Oon, Wee-Chong; Zhu, Wenbin et al.
In: European Journal of Operational Research, Vol. 220, No. 1, 01.07.2012, p. 37-47.
In: European Journal of Operational Research, Vol. 220, No. 1, 01.07.2012, p. 37-47.
Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review