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

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

Беглый анализ показал, что задача “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 + 4 * H.x AS x
	INTO R4
	FROM R2 AS L, R2 AS H;

SELECT L.x + 16 * 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, но это были отнюдь не достигнутые проценты утилизации объема короба. - Вот такой парадокс психологии!