Рис. 1. Построение стеков сравнительно одинаковой высоты из разных коробок
Обычно по такому принципу получалось уложить один или два приличных по качеству слоя в основании палеты. Но дальше становилось хуже. Перекрывающихся поверхностей становилось все меньше, и палета превращалась в группу столбиков с зияющими между ними дырами. Алгоритму «ТОПС Инжиниринг» редко удавалось собрать соседние стеки одинаковой высоты из разнородных коробок. Обычно плоская поверхность создавалась просто из нескольких уложенных рядом упаковок одинаковой высоты. Но когда наборов коробок схожей высоты уже не оставалось, плоские поверхности исчезали совсем. Иногда получалось построить более-менее устойчивый угол или даже половину палеты, но рядом все равно оставалась пустота.
Было очевидно, что надо делать алгоритм кардинально лучше, чем «ТОПС». Но как? Идеи не сразу приходили в голову. В литературе и в интернете я находил много общих рассуждений о вычислительной сложности проблемы, о потенциальных подходах к ее решению, но практически ничего, что бы реально помогало начать делать алгоритм. В большинстве случаев задача описывалась с точки зрения максимального заполнения пространства (минимизации пустот между коробками). Но в практическом смысле не менее важна структурная устойчивость палеты, хорошие перекрытия между плоскими поверхностями из нескольких коробок, а материалов на эту тему в научной литературе практически не было. Кроме того, необходимо оптимизировать палету по весу и прочности (тяжелые и крепкие коробки должны стоять внизу), а также по категориям товаров, так, чтобы товары близких категорий, соседствующих на полках в супермаркете, были рядом и на палете. И на этот счет ни в отраслевой литературе, ни в интернете я не нашел подходов и решений, которые можно было бы начать реализовывать.
Проблема построения плоских поверхностей из коробок разного размера (в том числе совершенно разной высоты) не давала мне покоя. Я думал о ней за рулем, во время велосипедных прогулок недалеко от дома и даже по ночам. Как сделать, чтобы этих поверхностей было больше, как дотянуть их до самого верха палеты?
Вскоре мне пришла в голову идея: что, если существенно изменить подход к решению проблемы? Что, если структурной единицей упаковки будет не целая палета, а слой, с плоскими нижними и верхними поверхностями, покрывающими всю палету? Если не пытаться увеличить площадь кусочных плоских поверхностей и продлевать их построение все выше, а на каждом шаге работать исключительно с плоскими поверхностями, занимающими все основание палеты?
Это будет вовсе не просто. Я предположил, что плоский слой можно построить, даже если все коробки в нем разного размера, в том числе по высоте. Общая идея состояла в следующем. Мы стараемся подобрать как можно больше стеков примерно одинаковой высоты из одной, двух, трех или четырех коробок. Если мы собрали достаточное число таких стеков и их общая площадь близка к площади основания палеты или превышает ее, эти стеки можно попробовать упаковать с небольшими зазорами уже на двумерном пространстве. В этом случае сверху мы получим плоскую поверхность, куда можно уложить еще один подобный слой из стеков, и т. д.
Рис. 2. Построение стеков из двадцати коробок неповторяющихся размеров. Можно, например, подобрать коллекцию из шести стеков примерно одинаковой высоты (стоящих рядом на нижней картинке), включающую в себя тринадцать коробок. Семь коробок из двадцати останутся неиспользованными
Если бы это удалось сделать, такой метод замечательно структурировал бы задачу палетизации, сводя ее к формированию последовательности слоев из стеков (или, в некоторых случаях, из одиночных коробок). На каждом слое задача повторяется и сводится к одной и той же процедуре. Но как построить такой слой?
Было далеко не очевидно, что это вообще осуществимо при огромном количестве разных комбинаций коробок. В середине декабря к нам в офис приехал программист из «ТОПС Инжиниринг», работающий над их алгоритмом палетизации, – обсудить с нами развитие проекта. Я спросил, не пытались ли они построить целые слои с плоским верхом из коробок разной высоты. «Это, пожалуй, невозможно», – ответил он.
Но я решил попробовать – я не сталкивался с подобной задачей раньше, и это придало мне смелости: ведь я не знал, что это, «пожалуй, невозможно». Для построения слоя надо подобрать стеки практически одинаковой высоты (с разницей в пределах нескольких миллиметров) из имеющихся упаковок. И для этого все равно придется перепробовать огромное количество комбинаций, хоть и намного меньшее, чем в задаче построения всей палеты.