Рассчитать приблизительную оценку для размера коробки доставки

Question

Я пытаюсь найти лучший способ рассчитать размер коробки, необходимый для доставки.

У меня есть 3 контейнера для перевозки разных размеров.У меня есть ширина, длина, глубина и масса продукта, определенные в базе данных.

Я хотел бы знать, как найти наименьшее количество коробок, необходимых для доставки, а также наименьшие размеры этих коробок, учитываяколичество товаров в корзине.

Моя текущая «идея» - найти максимальную ширину всего массива товаров, выбрать поле в соответствии с ним, а затем разделить заказ по мере необходимости ... это неНе похоже, что это сработает.

Размеры My Box: - 8 x 6 x 6 = 228 кубических дюймов - 10 x 8 x 8 = 640 кубических дюймов - 12,5 x 12,5 x 12,5 = 1953,125 кубических дюймов

Продукт определен так:

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

Я изучил проблему с рюкзаком, упаковку и т. Д. И не могу найти способ сделать это.Любая помощь будет БОЛЬШОЙ.

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

Вот низкотехнологичное, но возможное решение:

Мы просто столкнулись с той же проблемой. Я решил взять размеры наших коробок, а затем дать каждому продукту процент от того, сколько места заняло в каждом размере коробки. Наши продукты имеют свободную форму и могут быть слегка сжаты, так что если ваши абсолютные размеры, вам может понадобиться уменьшить проценты для учета продуктов, помещаемых в коробку под разными углами и т. Д. Также для нас мы всегда можем поставить вещи в коробках расположены под одинаковым углом друг к другу, что также помогает улучшить работу описанного ниже метода.

Предполагается, что есть 3 размера коробки:

• Продукт А
  • Коробка A = 48% (по 2 в коробке)
  • Коробка B = 30% (по 3 в коробке)
  • Коробка C = 12% (8 вписывается в коробку)
• Продукт B
  • Коробка А = 24%
  • Коробка B = 15%
  • Коробка C = 7%

Тогда просто сделайте, чтобы ваш код суммировал эти проценты для товаров в корзине для полей A, B и C ... очевидно, если они ниже 100%, все должно соответствовать, и если вы начнете сверху вниз, то первый достигнет меньшего чем 100% подойдет вашей продукции и будет самой маленькой коробкой. И если вы столкнетесь с какими-либо сценариями при упаковке, которые не подходят, просто немного уменьшите процент, который вы ввели для этого продукта.

Для нескольких коробочных отправлений вам просто нужно решить, что вы хотите сделать в качестве комбинаций. Вышесказанное работает лучше всего для отгрузок в один ящик, но с некоторой дополнительной логикой может легко работать для отгрузок в несколько ящиков.

Answer 2

Что касается получения оптимального ответа, это NP-Hard ... http://en.wikipedia.org/wiki/Bin_packing_problem

Жадный алгоритм, показанный в Википедии, хотя он может быть довольно далеким, на самом деле может подойти для вашего случая.

Однако в качестве оценки вы можете просто суммировать объемы предметов, а затем применить коэффициент неэффективности , а затем использовать наименьшие поля, которые вы можете.

Поочередно выМожно отсортировать элементы по уменьшающемуся объему, а затем посмотреть, сколько вы можете получить в текущем наборе блоков, создавая новый блок, когда вы не можете уместить элемент. Хотя не уверен, как вы будете обрабатывать блоки разных размеров.Вы также можете иметь дело с изменением размера коробки вместо создания новой коробки.

Пища для размышлений.