A reference length approach for the 3D strip packing problem

A reference length approach for the 3D strip packing problem

0.00 Avg rating0 Votes
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: , , ,
Keywords: heuristics
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.

Reviews

Required fields are marked *. Your email address will not be published.