An effective recursive partitioning approach for the packing of identical rectangles in a rectangle

An effective recursive partitioning approach for the packing of identical rectangles in a rectangle

0.00 Avg rating0 Votes
Article ID: iaor201054
Volume: 61
Issue: 2
Start Page Number: 306
End Page Number: 320
Publication Date: Feb 2010
Journal: Journal of the Operational Research Society
Authors: , ,
Keywords: packing
Abstract:

In this work, we deal with the problem of packing (orthogonally and without overlapping) identical rectangles in a rectangle. This problem appears in different logistics settings, such as the loading of boxes on pallets, the arrangements of pallets in trucks and the stowing of cargo in ships. We present a recursive partitioning approach combining improved versions of a recursive five-block heuristic and an L-approach for packing rectangles into larger rectangles and L-shaped pieces. The combined approach is able to rapidly find the optimal solutions of all instances of the pallet loading problem sets Cover I and II (more than 50,000 instances). It is also effective for solving the instances of problem set Cover III (almost 100,000 instances) and practical examples of a woodpulp stowage problem, if compared to other methods from the literature. Some theoretical results are also discussed and, based on them, efficient computer implementations are introduced. The computer implementation and the data sets are available for benchmarking purposes.

Reviews

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