Calcular una estimación aproximada para el tamaño de la caja de envío

Question

Estoy tratando de encontrar la mejor manera de calcular el tamaño de la caja necesaria para el envío.

Tengo 3 contenedores de transporte con diferentes tamaños. Tengo del producto anchura, longitud, profundidad, y la masa se define en la base de datos.

Me gustaría saber cómo encontrar la menor cantidad de cajas necesarias para barco, y también las dimensiones más pequeñas de esas cajas, dado el número de artículos en el carro.

Mi 'idea' actual es encontrar el máximo ancho de toda la gama de productos, seleccione la caja de acuerdo con ella, y luego dividir el orden que necesita ... esto no parece como si fuera a trabajar.

Mi tamaños de caja son:  - 8 x 6 x 6 = 228 pulgadas cúbicas  - 10 x 8 x 8 = 640 pulgadas cúbicas  - 12,5 x 12,5 x 12,5 = 1953.125 pulgadas cúbicas

Un producto se define como tal:

 [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
                )

He mirado en problema de la mochila, el problema de embalaje, etc y no puede encontrar una manera de hacer esto. Cualquier ayuda sería grande.

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

En cuanto a obtener una respuesta óptima, que es NP-duro ... http: //en.wikipedia .org / wiki / Bin_packing_problem

El algoritmo voraz se muestra en la Wikipedia, aunque puede ser bastante lejos, podría hacer por su caso.

Sin embargo, como una estimación que sólo podría resumir los volúmenes de los artículos y luego aplicar un factor de ineficiencia y luego usar la caja más pequeña (s) se puede.

Alternativamente, usted podría ordenar los elementos en la disminución de volumen y luego ver cuánto se puede conseguir en el actual conjunto de cajas, la creación de una nueva caja cuando no se puede instalar el artículo en. No estoy seguro de cómo le gustaría manejar diferentes tamaños de cajas aunque. También podría haber un caso en el que cambia el tamaño de la caja en lugar de crear una nueva caja.

Para la reflexión.

Answer 2

Esta es una tecnología baja, pero posible solución:

Sólo se encontró con el mismo problema. Decidí tomar nuestros tamaños de cajas y luego dar a cada producto de un porcentaje de la cantidad de espacio que tomó en cada tamaño de la caja. Nuestros productos son de forma libre y pueden ser aplastado un poco por lo que si el suyo son absolutos en el tamaño puede que tenga que reducir los porcentajes para dar cuenta de los productos que se ponga en la caja en diferentes ángulos etc ... También para nosotros que somos capaces de poner siempre cosas en las cajas como el mismo ángulo entre sí por lo que también ayuda a hacer el siguiente método funcione mejor.

Esto supone que hay 3 tamaños de la caja:

• Un Producto
  • Box A = 48% (2 ajuste en una caja)
  • Box B = 30% (3 ajuste en una caja)
  • Box C = 12% (8 ajuste en una caja)
• Producto B
  • Box A = 24%
  • Box B = 15%
  • Box C = 7%

A continuación, sólo tienen su código de sumar los porcentajes de su cesta productos para el cuadro A, B y C ... obviamente si están por debajo del 100% todo debe encajar y si se parte de arriba a abajo el primero en llegar a menos de 100% se ajuste a sus productos y ser la caja más pequeña. Y si surge algún escenarios cuando el embalaje que suele ajuste simplemente reducir ligeramente el porcentaje que ha introducido para ese producto.

Para envíos múltiples caja sólo tiene que decidir lo que quiere hacer en cuanto a como combinaciones. Lo anterior funciona mejor para los envíos de caja única, pero con un poco de lógica adicional fácilmente podrían funcionar bien para múltiples envíos de cajas.