Я не присутствовал на официальном открытии склада в Ньюбурге, но слышал, как это событие описывал спустя несколько лет один из моих коллег, менеджер команды программистов, на выступлении перед новыми сотрудниками. Как и полагается в таких случаях, были перерезанные ленточки, лозунги на плакатах, начальство в дорогих костюмах и коллективные фотки с зубастыми улыбками. Присутствовало несколько вице-президентов и других топ-менеджеров головной компании, «Си-энд-Эс», и они теснили друг друга для официального снимка у конца цепного конвейера. Это хоть и далеко не гламурное место было очень важным: оттуда должна была выйти первая палета с разносортными коробками, собранная роботом-палетизатором.
Но когда она вышла, позитивный настрой собрания рухнул, как мешок риса с полки продуктового склада. Это была очень маленькая и жалкая палета – дюжина коробок, хаотично наваленных одна на другую. Упомянутый менеджер назвал ее «the most miserable pallet ever» – самой ущербной палетой в истории. Он саркастически хмыкал, рассказывая, как вице-президенты стали неловко оттаптываться в разные стороны, инстинктивно не желая быть ближе всех в кадре к этому уродцу.
Я не видел самую первую палету, но насмотрелся фоток некоторых других, собранных на складе в последующие дни. Ими едва ли можно было похвастаться. Стало ясно, что качество палет – в первую очередь качество их геометрических моделей (планов палет), а не результата их механической сборки роботами – будет одной из острейших проблем для нашего экспериментального производства.
Мы затронули эту тему с Ларри Свитом еще во время моего собеседования. Он сказал, что формирование планов палет будет одной из ключевых задач для ньюбургского проекта и для нашей лаборатории. Софтверным алгоритмом по упаковке палет на тот момент занималась по контракту техасская компания «ТОПС Инжиниринг» с большим опытом решения разных оптимизационных задач в логистике, и мы полагались на их экспертность. Создать реально работающее решение самостоятельно Ларри не надеялся. По его мнению, это потребовало бы нескольких лет труда с крайне сомнительными шансами на успех.
Задача тем не менее привлекала меня с самого начала. Занимаясь видеоизмерением упаковок, я вполглаза следил за тем, как продвигался проект софта по упаковке палет (см. цв. вкл., рис. 5). Взаимодействие с «ТОПС» курировал мой китайский коллега Ке Фу. Когда Ке, почти всегда флегматичный и не склонный к проявлению эмоций, рассказывал о развитии проекта, тревога все явственнее проявлялась на его лице. Он был очевидно озабочен качеством полученных к тому времени результатов.
Беспокоиться было о чем. Задача упаковки прямоугольных коробок в замкнутый объем палет (3D bin packing problem) – одна из самых трудных в прикладной математике. Даже если нужно упаковать всего десять коробок разного размера, существует огромное число возможных вариантов такой укладки. Только крошечный процент этих комбинаций даст хорошее решение, остальные же будут похожи на хаотично накиданную кучу с неустойчивыми пирамидами и зияющими между ними дырами.
Обычная палета, используемая в американской логистике, имеет основание размером 40 на 48 дюймов, или около 101 на 122 см; при этом коробки могут на пару сантиметров вылезать за периметр этого основания. Проемы дверей погрузочных доков склада способны пропускать объекты высотой примерно два с половиной метра, но работникам трудно укладывать коробки выше двух метров, а также разгружать их по приезде в магазин. При типичном размере складских упаковок в полученный объем должно помещаться 100–150 коробок, а для некоторых категорий товаров – до 300. Это дает астрономическое число возможных комбинаций и мизерный, исчезающе малый процент приемлемых вариантов, образующих плотную и крепкую палету.
Проблема состояла не просто в том, чтобы впихнуть как можно больше коробок в ограниченный объем, а в том, чтобы создать по-настоящему устойчивую конструкцию. Достичь этого можно, сформировав некоторым набором коробок относительно плоскую поверхность, куда хорошо ляжет следующий слой. И затем еще одну плоскую поверхность. И еще одну. При наличии произвольного набора разных коробок это очень трудная задача. Относительно прямолинейный (но даже в этом случае крайне сложный) алгоритм может выглядеть так. Допустим, у нас 100 коробок разного размера и их надо уложить в палету. Из них мы выбираем подмножество, скажем, из 12 коробок примерно одинаковой высоты – с разницей в пределах одного сантиметра – и стараемся уложить их в один слой максимально плотно друг к другу, с минимальными зазорами на основание палеты. Верх этого слоя получается относительно ровным, и на него можно уложить следующий слой, где могут оказаться коробки тоже близкой друг к другу, но уже отличающейся от первого слоя высоты.