Looking for help developing an algorithm to solve a 2D rectangle packing/bin problem.

Question

I need to develop an algorith to determine the optimum packing arrangement of dimensionally identical rectangles in a large rectangle of fixed size. 90 degree rotations are permitted.

I've researched in to packing problems and tried to digest the contents of a few papers, but many seem to not be directly related to my problem. They seem to be concerned with finding the minimum number of larger rectangles required to pack a fixed number of random smaller rectangles.

My problem is, how many smaller rectangles can I pack in a single large rectangle?

I'm not a mathematition - I am engineer so this problem is not so much a theoretical one - this is a pallet packing arrangement of real items and so the "theoretical optimum" packing arrangement may not be the best for me.

I need to find a compromise between optimum and simplicity as the pallets will be packed by people. I appreciate that this might be difficult to quantify so I am also looking for advice on this. I was thinking a long the lines of setting an upper bound on the number of total 90degree rotations allowed in any one arrangement, as to maintain a good amount of order in the total arrangement.

Would very much appreciate the help.

Answer 1

Given your requirement for simplicity I would suggest dividing the pallet into two rectangular regions and packing the objects in the first region with the longer dimension in the direction of the longer dimension of the pallet and in the remaining rectangular region of the pallet packing them rotated by 90 degrees.

Then try the same thing but starting with packing the objects in the first region with the longer dimension in the smaller dimension of the pallet (obviously not necessary for a square pallet).

With such a simple arrangement, for any real world situations I can imagine, a simple brute-force search should be fast enough here.

The following python script can be a start for you (multiply licensed under any license approved by the Open Source Initiative, with addition of WTFPL):

#! /usr/bin/python

import math

pallet_width = 80.
pallet_length = 100. # assumed > width

object_width = 4.1
object_length = 7.3 # assumed > width

def simple_pack(target_width, target_length, object_dim1, object_dim2):
    return math.floor(target_width / object_dim1) * math.floor(target_length / object_dim2)

max_length_to_length = int(math.floor(pallet_length / object_length))
max_length_to_width = int(math.floor(pallet_width / object_length))

best_L2L_packing = 0
for i in range(max_length_to_length, 0, -1):
    # i is the number of objects packed in length-to-length direction
    packed_L2L = i * int(math.floor(pallet_width / object_width))
    remaining_length = pallet_length - i * object_length
    total_packing = packed_L2L + int(simple_pack(remaining_length, pallet_width, object_width, object_length))
    if total_packing > best_L2L_packing:
        best_L2L_packing = total_packing
        best_L2L = i
        print "L2L=", i, "packing=", best_L2L_packing

print "% L2L efficiency =", best_L2L_packing * object_width * object_length / float(pallet_width * pallet_length)

best_L2W_packing = 0
for i in range(max_length_to_width, 0, -1):
    # i is the number of objects packed in length-to-width direction
    packed_L2W = i * int(math.floor(pallet_length / object_width))
    remaining_width = pallet_width - i * object_length
    total_packing = packed_L2W + int(simple_pack(remaining_width, pallet_length, object_width, object_length))
    if total_packing > best_L2W_packing:
        best_L2W_packing = total_packing
        best_L2W = i
        print "L2W=", i, "packing=", best_L2W_packing

print "% L2W efficiency =", best_L2W_packing * object_width * object_length / float(pallet_width * pallet_length)