Для следующего слоя мы ищем еще одну комбинацию коробок, близких по высоте, из оставшегося набора. Но в нем может уже не оказаться достаточного числа подходящих коробок, и очередного плоского слоя, покрывающего всю палету, не получится. Мы можем сделать плоский слой примерно на половину палеты, а оставшуюся поверхность покрыть коробками другой высоты. Тогда мы получаем две плоских поверхности меньшей площади и разной высоты. Оставшиеся коробки придется укладывать по отдельности – на одну и на другую поверхность. Когда площадь основания уменьшается, а форма оказывается сложнее, чем простой прямоугольник, укладка следующих слоев будет в среднем хуже по качеству и с большими зазорами между коробками. Две разные плоские поверхности на следующем слое превратятся в три или четыре и далее будут расщепляться до тех пор, пока все плоские поверхности не будут состоять из одной коробки. Оставшиеся коробки можно только ставить друг на друга столбиком. В итоге такое построение превратится в набор рядом стоящих стопок, которые будут шататься и легко опрокидываться. Такая палета может просто рухнуть в процессе сборки или превратиться в кучу смятых коробок при транспортировке.
Таким образом, одной из ключевых задач алгоритма палетизации было создание больших плоских поверхностей до самого верха палеты – так, чтобы каждый новый слой мог укладываться на предыдущий с перекрытиями. Последние образуются тогда, когда щели между коробками текущего слоя закрываются коробками следующего, так что большинство верхних коробок опирается на две или более коробки в предыдущем слое. Это позволяет избежать формирования палеты, представляющей собой набор шатких отдельно стоящих стопок, разделенных глубокими щелями.
Процедура более-менее понятна и осуществима, если у нас в каждый момент времени достаточно коробок примерно одинаковой высоты, чтобы сформировать плоский слой во всю площадь палеты. Но как быть, если диапазон высот слишком широк и наборов схожих коробок мало? Можно попробовать собирать стопки (стеки) из разных коробок, близкие по высоте. При этом все коробки могут быть разной высоты, и в соседних стеках (в дальнейшем я буду называть их именно так – как в английском варианте stack) может быть разное число коробок. Например, один стек составлен из двух упаковок высотой 260 и 195 мм, в сумме – 455 мм. Другой стек – из трех упаковок высотой 115, 170 и 165 мм, в сумме – 450 мм. Установленные рядом, они образуют плоскую поверхность с незначительным перепадом высоты. На нее можно укладывать новый слой коробок, перекрывающий щель между этими стеками.
Подобрать комбинации коробок так, чтобы несколько соседних стеков оказались примерно одинаковой высоты, не очень сложно. Но площадь плоских поверхностей все равно будет уменьшаться к верхним слоям. Допустим, мы смогли подобрать и поставить рядом три стека, образовавших ровную поверхность. На нее мы будем укладывать новые коробки или стеки. Но они, скорее всего, не займут всю площадь. Поместится только два стека поверх трех, так, чтобы верхние перекрывали щели между нижними. Поверх этих двух, вероятно, получится уместить только один новый стек, перекрывающий щели между двумя нижними.
И вот мы опять приходим к пирамидам и высоким шатким столбикам из коробок.
Примерно так работал алгоритм «ТОПС», основанный на математическом методе рандомизированного направленного поиска «симулированного отжига»[12]. Этот алгоритм брал одну коробку, старался уложить ее в оптимальное место для текущего состояния палеты, пробовал несколько вариантов, выбирал из них относительно оптимальный по нескольким критериям и повторял процедуру со следующей коробкой.
12
Алгоритм симулированного отжига (