Calculate a rough estimate for shipping box size

Question

I'm trying to find the best way to calculate the box size needed for shipping.

I have 3 shipping containers with different sizes. I have the product's width, length, depth, and mass defined in the database.

I would like to know how to find the smallest amount of boxes needed to ship, and also the smallest dimensions of those boxes given the number of items in the cart.

My current 'idea' is to find the maximum width of the entire products array, the select a box according to it, and then split the order as needed... this doesn't seem like it would work.

My Box sizes are: - 8 x 6 x 6 = 228 cubic inches - 10 x 8 x 8 = 640 cubic inches - 12.5 x 12.5 x 12.5 = 1953.125 cubic inches

A product is defined as such:

 [Product] => Array
                (
                    [STOCK_CODE] => 010003
                    [Product_Slug] => GABA_010003
                    [ItemName] => GABA
                    [WHOLESALE_PRICE] => 17.47
                    [RETAIL_PRICE] => 24.95
                    [Brand] => 
                    [ProductLine] => 
                    [image_name] => 705077000440
                    [MASS] => 0.313
                    [Height] => 4.625
                    [Width] => 2.375
                    [Depth] => 2.375
                    [cubic_inches] => 26.087890625
                )

I've looked into knapsack problem, packing problem, etc and can't find a way to do this. Any help would be GREAT.

function shipping(){

        $this->CartProduct->unbindModel(
            array('belongsTo' => array('User'))
        );

        //find all cart products by current logged in user
        $cartItems = $this->CartProduct->find('all', array('conditions' => array('CartProduct.user_id' => $this->Auth->user('id'))));

        $i = 0;

        //get the max width, height, depth
        $maxHeight = 0;
        $maxWidth = 0;
        $maxDepth = 0;
        foreach($cartItems as $c){
            $cartItems[$i]['Product']['cubic_inches'] = $c['Product']['Height'] * $c['Product']['Width'] * $c['Product']['Depth'];
            $cartItems[$i]['CartProduct']['total_cubic_inches'] = ($c['Product']['Height'] * $c['Product']['Width'] * $c['Product']['Depth']) * $c['CartProduct']['qty'];

            if($c['Product']['Height'] > $maxHeight)
            {
                $maxHeight = $c['Product']['Height'];
            }

            if($c['Product']['Width'] > $maxWidth)
            {
                $maxWidth = $c['Product']['Width'];
            }
            if($c['Product']['Depth'] > $maxDepth)
            {
                $maxDepth = $c['Product']['Depth'];
            }
            $i++;
        }

        //possible containers 
        //8 x 6 x 6 = 228 ci
        //10 x 8 x 8 = 640 ci
        //12.5 x 12.5 x 12.5 = 1953.125

        $possibleContainers = array(
            1 => array(
                'Height' => 8,
                'Width' => 6,
                'Depth' => 6,
                'Cubic' => 228),
            2 => array(
                'Height' => 10,
                'Width' => 8,
                'Depth' => 8,
                'Cubic' => 640),
            3 => array(
                'Height' => 12.5,
                'Width' => 12.5,
                'Depth' => 12.5,
                'Cubic' => 1953.125)
        );



        $max = array(
            'Height' => $maxHeight, 
            'Width' => $maxWidth, 
            'Depth' => $maxDepth, 
        );

        pr($cartItems);
        pr($possibleContainers);
        die();  
    }

Answer 1

Here is a low tech but possible solution:

We just ran into the same issue. I decided to take our box sizes and then give each product a percentage for how much space it took in each box size. Our products are free form and can be squished a bit so if yours are absolute in size you may need to reduce the percentages to account for products being put in the box at different angles ect... Also for us we are able to always put things in the boxes as the same angle to each other so this also helps make the below method work better.

This assumes there are 3 box sizes:

• Product A
  • Box A = 48% (2 fit in a box)
  • Box B = 30% (3 fit in a box)
  • Box C = 12% (8 fit in a box)
• Product B
  • Box A = 24%
  • Box B = 15%
  • Box C = 7%

Then just have your code add up those percentages for your cart items for box A, B and C ... obviously if any are below 100% everything should fit and if you start from top to bottom the first one to reach less than 100% will fit your products and be the smallest box. And if you run into any scenarios when packing that wont fit just slightly reduce the percentage you entered for that product.

For multiple box shipments you just need to decide what you want to do as for as combinations. The above works best for single box shipments but with some additional logic could easily work well for multiple box shipments.

Answer 2

As for getting a optimal answer, that's NP-Hard... http://en.wikipedia.org/wiki/Bin_packing_problem

The greedy algorithm shown on Wikipedia, while it can be quite far off, might actually do for your case.

However as an estimate you could just sum up the volumes of the items and then apply a inefficiency factor and then use the smallest box(s) you can.

Alternately you could sort the items into decreasing volume and then see how much you can get into the current set of boxes, creating a new box when you can't fit the item in. Not sure how you would handle different box sizes though. You could also have a case where it changes the box size rather than creating a new box.

Food for thought.