Будни автоматизации или «мне нужна программка для 3D упаковки»

    Автоматизация отечественных предприятий, которой приходиться заниматься, это нужная и высокооплачиваемая, но довольно нервная работа. Выручает юмор. Например, при общении с требовательным клиентом можно вспомнить анекдот: «Держась руками за стену, на ногах еле стоит мужик. К нему пристает ребенок: „Ну, папа, пожалуйста, сделай мне кораблик!“, папа отвечает: „Ага! — Сейчас все брошу и пойду делать тебе кораблик!“. Про один такой сделанный для клиента „кораблик“ и хочется рассказать. Надеюсь, совместное погружение в теплое ламповое (то есть клиентоориентированное) программирование доставит Вам положительные эмоции, да и задача попалась интересная. Поплыли?

    image

    Началось все с письма клиента, в котором говорилось что крупный сетевой ритейлер Х (все его знают) потребовал, чтобы отгрузки в его адрес осуществлялись не на паллетах, а в коробах заданного размера. Поэтому менеджеру, курирующему данного клиента, требуется „программка“, которая по составу разноразмерных упаковок в заказе определит  необходимое количество коробов и распечатает упаковочные листы. Письмо сопровождалось просьбой не затягивать решение вопроса, поскольку момент перехода на новую систему отгрузок вот-вот наступит, а штрафные санкции могут стоить больше, чем новый автомобиль генерального. Стоимость автомобиля была известна, так как «Феррари» числилась в списке основных средств. Поэтому задача нехотя (всего одно рабочее место из почти пары сотен) была взята в работу и поставлена на контроль. Хотя более массовых задач в тот момент было море: только-только запущено свежеразработанное ПО для терминалов сбора данных на складе сырья, в режиме ошпаренной кошки велась разработка приложения для перевода торговых представителей с КПК на планшеты, отлаживалась система регистрации и контроля перемещений паллет с готовой продукцией и тому подобное.

    Беглый анализ показал, что задача “container loading” является NP-полной. Объяснить это клиенту, который регулярно капризным голосом названивал с вопросом „когда же будет моя программка“, мы не могли и не пытались. А Вы попробуйте сказать симпатичной девушке-менеджеру по работе с клиентами, что ее задача какая-то там полная. О чем она в первую очередь подумает? И какие у вас после этого шансы? В общем, наивная вера наших клиентов в безграничные возможности компьютеров и всемогущество программистов сыграла в тот раз с нами очередную шутку. Но нужно было выкручиваться и мы это сделали.

    Чтобы объяснить приведенное далее решение требуется иметь в виду еще одно обстоятельство. Фреймворк, с которым мы работаем, основан на скриптовом языке. Хотя язык достаточно гибок и обвешен по принципу рождественской елки всякими хлопушками и погремушками, включая даже методы математической статистики, он не очень хорошо приспособлен для задач с объемными вычислениями. Обычный цикл у нас выполняется гораздо дольше, чем в компилируемом языке. Поэтому простые, но массовые вычисления бывает удобнее делать на стороне сервера непосредственно на уровне СУБД. Для работы с базой данных у нас используется язык, очень похожий на T-SQL. Поэтому не сомневаюсь, что приведенный далее код будет всем понятен.

    Идея решения заключается в том, чтобы расчертить дно короба на маленькие клеточки, получить в таблице все возможные варианты расположения каждой упаковки в узлах сетки с учетом возможных вращений этой упаковки, зафиксировать выбор лучшего конкретного расположения одной из упаковок, а затем скорректировать таблицу решений, „подняв“ возможные расположения других оставшихся упаковок на высоту зафиксированной упаковки, если их размещения пересекаются.

    В общем, вы поняли, что мы использовали „жадный“ алгоритм. Кстати, видимо, увидев это неосторожно написанное слово в листе учета рабочего времени, главный бухгалтер потом долго ворчала и не хотела подписывать счет за переработанные часы.

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

    Итак, сначала получаем таблицу чисел от 0 до 255 каскадным возведением в степень таблицы из 0 и 1.

    SELECT 0 AS x
    	INTO R1                                 
    UNION
    SELECT 1;
    
    SELECT L.x + 2 * H.x AS x
    	INTO R2
    	FROM R1 AS L, R1 AS H;
    
    SELECT L.x + 2 * H.x AS x
    	INTO R4
    	FROM R2 AS L, R2 AS H;
    
    SELECT L.x + 2 * H.x AS x
    	INTO R8
    	FROM R4 AS L, R4 AS H;
    


    Затем получаем таблицу всех возможных вращений упаковок. Кстати, интересная задача, чтобы проверить свое знание TSQL. Возможно, это новый паззл SQL для Joe Celko

    SELECT id, CASE x WHEN 0 THEN d0 WHEN 1 THEN d1 WHEN 2 THEN d2 END AS dx, x
    	INTO Scan
    	FROM Items, R2
    	WHERE x < 3;
     
    SELECT DISTINCT B0.id, B0.dx AS d0, B1.dx AS d1, B2.dx AS d2
    	INTO Spin
    	FROM Scan AS B0
    		JOIN Scan AS B1 ON B0.id = B1.id
    		JOIN Scan AS B2 ON B0.id = B2.id
    	WHERE NOT(B0.x = B1.x OR B0.x = B2.x OR B1.x = B2.x);
    

    Наконец, инициализируем таблицу решений, умножая координаты сетки на таблицу вращений.

    SELECT FromLeft.x AS d0l, FromBack.x AS d1l, FromLeft.x + d0 AS d0h, FromBack.x + d1 AS d1h, 0 AS d2l, d2 AS d2h, 0 AS v, d0 * d1 AS s, id
    	INTO Vista
    	FROM R8 AS FromLeft, R8 AS FromBack, Spin
    	WHERE FromLeft.x + d0 < = &Width AND FromBack.x + d1 < = &Depth AND d2 < = &Height;
    


    Теперь выполняем цикл:

    Для выбора лучшего варианта используется следующий запрос.

    SELECT TOP 1 id, d0l, d1l, d2l, d0h, d1h, d2 
    	FROM Vista 
    	WHERE d2l + d2 < = &Height 
    	ORDER BY s * d2l - v, s * d2 DESC, d2l + d2, d0l, d1l, d0h;
    


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

    Изменение таблицы решений с учетом того, что некоторое место в коробе становится занятым, делается так:

    SELECT Vi.d0l, Vi.d1l
    , ISNULL(CASE WHEN It.d2l + It.d2 > Vi.d2l THEN It.d2l + It.d2 END, Vi.d2l) AS d2l
    , Vi.d0h, Vi.d1h, Vi.d2
    , Vi.v + ISNULL((CASE WHEN It.d1l < Vi.d1l THEN It.d1l ELSE Vi.d1l END - CASE	WHEN It.d0l > Vi.d0l THEN It.d0l ELSE Vi.d0l END) 
    * (CASE	WHEN It.d1h < Vi.d1h THEN It.d1h ELSE Vi.d1h END - CASE	WHEN It.d1l > Vi.d1l THEN It.d1l ELSE Vi.d1l END) * It.d2, 0) AS v
    , Vi.s,	Vi.id
    	FROM Vista AS Vi
    		LEFT JOIN Items AS It
    		ON (Vi.d1l < = It.d1l AND It.d1l < Vi.d1h OR It.d1l < = Vi.d1l AND Vi.d1l < It.d1h)
    			AND (Vi.d0l < = It.d0l AND It.d0l < Vi.d0h OR It.d0l < = Vi.d0l AND Vi.d0l < It.d0h)
    	WHERE Vi.id <> &id AND It.id = &id;
    


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

    Вот, в общем-то, и все.

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

    Ниже приведен скриншот упаковочного листа, использованного при отладке.

    Скриншот упаковочного листа

    Настоящий упаковочный лист выглядит довольно скучно: графика 2,5Д упаковщикам оказалась не нужной. Собственно результат работы представляет собой просто еще одну печатную форму, подключаемую к заказу. Работает на типичных заказах данного конкретного клиента достаточно быстро.

    В общем, клиент в лице девушки-менеджера остался доволен. Правда, не так, чтобы очень. А вот почему? Вряд ли ее могла расстроить инструкция к программке, в которой говорилось, что она работает только с толстым клиентом в обычных формах (это была десятая редакция). Мы ведь все знаем, что большинство наших клиентов никогда не открывают инструкций. В общем, разгадка мыслей отдельных пользователей это вам не «container loading», а действительно неразрешимая проблема.

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

    P.S.: Здесь все правда и ничего не выдумано — коллеги не дадут соврать. Причем наиболее глубокое впечатление почему-то осталось у тех, кого я подвозил тогда на своей синей импрезе. Все запомнили число 200, но это были отнюдь не достигнутые проценты утилизации объема короба.
    Вот такой парадокс психологии!

    (С) ildarovich
    INFOSTART.RU
    Company
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 9

      +1
      Вы — герой. Но мне интересно — а какой там объем входных данных, что NP-полнота имеет значение? Поставили бы какой-нибудь Blue Gene (условно говоря) для этой задачи.
        0
        когда-то решалось что-то подобное для автоматизации ячеистого склада… 20000 мест, 5000 номенклатуры… В итоге ограничились «типоразмерами» номенклатуры и «псевдовместимости» мест, ибо на минитестах подобное допущение давало погрешность менее 3%
          0
          Одна коммерческая библиотека, стоимостью $1K, которую припрягли для аналогичной задачи мы, имеет ограничения порядка 30 объектов и 10 типов коробок.
          По словам автора библиотеки, при превышении этих параметров результаты выходят либо до непрактичности неточные, либо до непрактичности времязатратные.

          В частности, я представляю себе случаи, когда жадный алгоритм скосячит: например, когда длинный узкий объект нужно поставить «торчком» в оставленные под его размеры «дырки» в предыдущих слоях.
            0
            «Программка» совершенно нормально работает и с 20 типами коробок и со 100 объектами. Но все же это переборный метод, его время работы прямо пропорционально площади дна коробки, числу типов коробок и числу объектов. Еще одним ограничением является «дискретизация» положения упаковок на дне коробки. Например, если дискретизация — 1 см, а размеры коробок заданы в миллиметрах, то между упаковками будет оставаться расстояние.
            Жадный алгоритм может делать неудачные ходы, согласен. Например, на рисунке в статье можно увидеть, что Classic Jenga была положена сначала на 6-м шаге выше, а на 7-м ниже и не плоско, а ребром. Это произошло из-за минимизации закрываемой пустоты. На шестом шаге была возможность положить Jenga без пустоты под ней, а на седьмом шаге она длиннее Фермера на 2 см и пустота под Jenga образовалась. Чтобы она оказалась меньше, программа положила 7-ю коробку на ребро.
            Интересно, что буквально сегодня провели «натурный» эксперимент. Так вот, программка уложила упаковки лучше, чем два стажера, которым дали эту задачу, что было совершенно неожиданно для меня. Будем еще перепроверять этот результат.
            0
            Наверное, нет смысла в получении точной статистики по заказам данного клиента (хотя такая возможность имеется) — число строк в заказе (это будет число типов коробок) и число мест. Ориентировочно в заказе было 10 -15 строк и порядка 100 упаковок.
            Когда я говорил, что эта задача NP-полная, я имел ввиду задачу получения глобально-оптимального решения, минимизирующего неиспользуемое пространство в коробе. Применяя «жадный» алгоритм, мы получаем субоптимальное решение. То есть мы не делаем «возвратов», если обнаружили неудачно расположенную на предыдущем шаге коробку, как, например, в методе ветвей и границ. Трудоемкость использованного алгоритма легко оценить. Она пропорциональна произведению ширины, глубины коробки, числу типов коробок и общему числу коробок.
            Не вполне сейчас уверен, но вроде бы, в просмотренных мною работах на тему «container loading», давалась оценка эффективности жадного алгоритма как 77%. Есть стандартный набор тестов, на которых проверяются разные алгоритмы. Интересно, что гораздо более сложные алгоритмы могут давать 84, 86%. То есть их эффективность не настолько выше. Возможно, при загрузке морских контейнеров и вагонов и стоит бороться за эти 7-13%. В нашем случае в этом не было смысла.
            0
            Кто-нибудь, объясните анекдот…
              0
              Знаете что такое NP-полная задача? Условно говоря, это задача, которую нельзя точно решить быстрее чем полным перебором. Т. е. неразрешимая за приемлемое время задача. Вот такую задачу потребовалось решить автору.
              0
              «Фреймворк, с которым мы работаем, основан на скриптовом языке» — Тот-Который-Нельзя-Называть
                0
                1С вообще не упомянут в статье? Даже жаль. Кажется, что было бы интересно отметить, что реализовано в 1С.

              Only users with full accounts can post comments. Log in, please.