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

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.