Текст книги "Тугая упаковка, или Бизнес-роман о роботах, алгоритмах и о складе без людей"

Глава пятая
Проект KP

ЯНВАРЬ – ДЕКАБРЬ 2011

Эта глава станет, по-видимому, важнейшей во всей книге. В ней я расскажу о личном эпизоде «эврики» – о неожиданно придуманном мной алгоритме упаковки разных коробок в палеты и о том, как этот алгоритм был внедрен в рабочий код компании, сыграв ключевую роль в ее развитии. Это будет непростое повествование. Некоторые читатели предпочтут не вдаваться в сложные технические подробности описания алгоритма. Кого-то развитие проекта вокруг него заинтересует больше, чем математические выкладки. Прошу читателей выбирать самим, насколько они хотят погрузиться в эти детали.

* * *

В начале декабря 2010 г. был запущен наш первый проект – экспериментальный автоматизированный склад в Ньюбурге, штат Нью-Йорк. Сложные системы, подобные ему, никогда не включаются с места на полную катушку. Первые недели такой склад работает едва-едва, всего лишь на 10 % от запланированной мощности. Этот момент – включения системы в полном цикле, но на минимальных оборотах – в индустрии называют Go Live – «оживление». От него начинается отсчет ramp-up – постепенного увеличения мощности, способного растянуться на много месяцев. В реальности на некоторых наших складах этот процесс длился еще дольше – почти год. Но тогда, в 2010-м, до следующих наших систем было еще далеко.

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

Но когда она вышла, позитивный настрой собрания рухнул, как мешок риса с полки продуктового склада. Это была очень маленькая и жалкая палета – дюжина коробок, хаотично наваленных одна на другую. Упомянутый менеджер назвал ее «the most miserable pallet ever» – самой ущербной палетой в истории. Он саркастически хмыкал, рассказывая, как вице-президенты стали неловко оттаптываться в разные стороны, инстинктивно не желая быть ближе всех в кадре к этому уродцу.

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

Мы затронули эту тему с Ларри Свитом еще во время моего собеседования. Он сказал, что формирование планов палет будет одной из ключевых задач для ньюбургского проекта и для нашей лаборатории. Софтверным алгоритмом по упаковке палет на тот момент занималась по контракту техасская компания «ТОПС Инжиниринг» с большим опытом решения разных оптимизационных задач в логистике, и мы полагались на их экспертность. Создать реально работающее решение самостоятельно Ларри не надеялся. По его мнению, это потребовало бы нескольких лет труда с крайне сомнительными шансами на успех.

* * *

Задача тем не менее привлекала меня с самого начала. Занимаясь видеоизмерением упаковок, я вполглаза следил за тем, как продвигался проект софта по упаковке палет (см. цв. вкл., рис. 5). Взаимодействие с «ТОПС» курировал мой китайский коллега Ке Фу. Когда Ке, почти всегда флегматичный и не склонный к проявлению эмоций, рассказывал о развитии проекта, тревога все явственнее проявлялась на его лице. Он был очевидно озабочен качеством полученных к тому времени результатов.

Беспокоиться было о чем. Задача упаковки прямоугольных коробок в замкнутый объем палет (3D bin packing problem) – одна из самых трудных в прикладной математике. Даже если нужно упаковать всего десять коробок разного размера, существует огромное число возможных вариантов такой укладки. Только крошечный процент этих комбинаций даст хорошее решение, остальные же будут похожи на хаотично накиданную кучу с неустойчивыми пирамидами и зияющими между ними дырами.

Обычная палета, используемая в американской логистике, имеет основание размером 40 на 48 дюймов, или около 101 на 122 см; при этом коробки могут на пару сантиметров вылезать за периметр этого основания. Проемы дверей погрузочных доков склада способны пропускать объекты высотой примерно два с половиной метра, но работникам трудно укладывать коробки выше двух метров, а также разгружать их по приезде в магазин. При типичном размере складских упаковок в полученный объем должно помещаться 100–150 коробок, а для некоторых категорий товаров – до 300. Это дает астрономическое число возможных комбинаций и мизерный, исчезающе малый процент приемлемых вариантов, образующих плотную и крепкую палету.

Проблема состояла не просто в том, чтобы впихнуть как можно больше коробок в ограниченный объем, а в том, чтобы создать по-настоящему устойчивую конструкцию. Достичь этого можно, сформировав некоторым набором коробок относительно плоскую поверхность, куда хорошо ляжет следующий слой. И затем еще одну плоскую поверхность. И еще одну. При наличии произвольного набора разных коробок это очень трудная задача. Относительно прямолинейный (но даже в этом случае крайне сложный) алгоритм может выглядеть так. Допустим, у нас 100 коробок разного размера и их надо уложить в палету. Из них мы выбираем подмножество, скажем, из 12 коробок примерно одинаковой высоты – с разницей в пределах одного сантиметра – и стараемся уложить их в один слой максимально плотно друг к другу, с минимальными зазорами на основание палеты. Верх этого слоя получается относительно ровным, и на него можно уложить следующий слой, где могут оказаться коробки тоже близкой друг к другу, но уже отличающейся от первого слоя высоты.

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

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

Процедура более-менее понятна и осуществима, если у нас в каждый момент времени достаточно коробок примерно одинаковой высоты, чтобы сформировать плоский слой во всю площадь палеты. Но как быть, если диапазон высот слишком широк и наборов схожих коробок мало? Можно попробовать собирать стопки (стеки) из разных коробок, близкие по высоте. При этом все коробки могут быть разной высоты, и в соседних стеках (в дальнейшем я буду называть их именно так – как в английском варианте stack) может быть разное число коробок. Например, один стек составлен из двух упаковок высотой 260 и 195 мм, в сумме – 455 мм. Другой стек – из трех упаковок высотой 115, 170 и 165 мм, в сумме – 450 мм. Установленные рядом, они образуют плоскую поверхность с незначительным перепадом высоты. На нее можно укладывать новый слой коробок, перекрывающий щель между этими стеками.

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

И вот мы опять приходим к пирамидам и высоким шатким столбикам из коробок.

Примерно так работал алгоритм «ТОПС», основанный на математическом методе рандомизированного направленного поиска «симулированного отжига»[12]12
  Алгоритм симулированного отжига (англ. simulated annealing) – общий алгоритмический метод решения задачи глобальной оптимизации, особенно дискретной и комбинаторной оптимизации. Основывается на имитации физического процесса, происходящего при кристаллизации вещества, в том числе при отжиге металлов (постепенном понижении температуры).


[Закрыть]. Этот алгоритм брал одну коробку, старался уложить ее в оптимальное место для текущего состояния палеты, пробовал несколько вариантов, выбирал из них относительно оптимальный по нескольким критериям и повторял процедуру со следующей коробкой.

Рис. 1. Построение стеков сравнительно одинаковой высоты из разных коробок

Обычно по такому принципу получалось уложить один или два приличных по качеству слоя в основании палеты. Но дальше становилось хуже. Перекрывающихся поверхностей становилось все меньше, и палета превращалась в группу столбиков с зияющими между ними дырами. Алгоритму «ТОПС Инжиниринг» редко удавалось собрать соседние стеки одинаковой высоты из разнородных коробок. Обычно плоская поверхность создавалась просто из нескольких уложенных рядом упаковок одинаковой высоты. Но когда наборов коробок схожей высоты уже не оставалось, плоские поверхности исчезали совсем. Иногда получалось построить более-менее устойчивый угол или даже половину палеты, но рядом все равно оставалась пустота.

* * *

Было очевидно, что надо делать алгоритм кардинально лучше, чем «ТОПС». Но как? Идеи не сразу приходили в голову. В литературе и в интернете я находил много общих рассуждений о вычислительной сложности проблемы, о потенциальных подходах к ее решению, но практически ничего, что бы реально помогало начать делать алгоритм. В большинстве случаев задача описывалась с точки зрения максимального заполнения пространства (минимизации пустот между коробками). Но в практическом смысле не менее важна структурная устойчивость палеты, хорошие перекрытия между плоскими поверхностями из нескольких коробок, а материалов на эту тему в научной литературе практически не было. Кроме того, необходимо оптимизировать палету по весу и прочности (тяжелые и крепкие коробки должны стоять внизу), а также по категориям товаров, так, чтобы товары близких категорий, соседствующих на полках в супермаркете, были рядом и на палете. И на этот счет ни в отраслевой литературе, ни в интернете я не нашел подходов и решений, которые можно было бы начать реализовывать.

Проблема построения плоских поверхностей из коробок разного размера (в том числе совершенно разной высоты) не давала мне покоя. Я думал о ней за рулем, во время велосипедных прогулок недалеко от дома и даже по ночам. Как сделать, чтобы этих поверхностей было больше, как дотянуть их до самого верха палеты?

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

Это будет вовсе не просто. Я предположил, что плоский слой можно построить, даже если все коробки в нем разного размера, в том числе по высоте. Общая идея состояла в следующем. Мы стараемся подобрать как можно больше стеков примерно одинаковой высоты из одной, двух, трех или четырех коробок. Если мы собрали достаточное число таких стеков и их общая площадь близка к площади основания палеты или превышает ее, эти стеки можно попробовать упаковать с небольшими зазорами уже на двумерном пространстве. В этом случае сверху мы получим плоскую поверхность, куда можно уложить еще один подобный слой из стеков, и т. д.

Рис. 2. Построение стеков из двадцати коробок неповторяющихся размеров. Можно, например, подобрать коллекцию из шести стеков примерно одинаковой высоты (стоящих рядом на нижней картинке), включающую в себя тринадцать коробок. Семь коробок из двадцати останутся неиспользованными

Если бы это удалось сделать, такой метод замечательно структурировал бы задачу палетизации, сводя ее к формированию последовательности слоев из стеков (или, в некоторых случаях, из одиночных коробок). На каждом слое задача повторяется и сводится к одной и той же процедуре. Но как построить такой слой?

Было далеко не очевидно, что это вообще осуществимо при огромном количестве разных комбинаций коробок. В середине декабря к нам в офис приехал программист из «ТОПС Инжиниринг», работающий над их алгоритмом палетизации, – обсудить с нами развитие проекта. Я спросил, не пытались ли они построить целые слои с плоским верхом из коробок разной высоты. «Это, пожалуй, невозможно», – ответил он.

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

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

* * *

Я задумал попробовать другой метод, предполагающий кардинально иное решение.

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

1, 2, 3, 4;

1, 2, 3, 5;

1, 3, 4, 5;

2, 3, 4, 5

и т. д.

Допустим, у нас в выборке 50 коробок. Тогда последними комбинациями из четырех коробок будут

46, 48, 49, 50;

46, 47, 48, 50;

46, 47, 48, 49;

47, 48, 49, 50.

Кроме того, нужно проверить высоты комбинаций из трех, двух и одной коробки:

от 1, 2, 3 до 48, 49, 50;

от 1, 2 до 49, 50

и от 1 до 50.

Чем больше коробок в выборке, тем стремительнее растет количество этих комбинаций. Для выборки из 50 коробок получаем 230 300 комбинаций, для выборки из 60 коробок – 487 635, для 70 – 916 895, почти миллион. Но высóты всех этих комбинаций, сколько бы их ни было, можно сосчитать очень быстро, за малую долю секунды.

Я решил попробовать так: пересчитать высоты всех комбинаций и построить гистограмму, отображающую, сколько из них попадает в узкий (скажем, 10 мм) интервал высот. Затем взять несколько локальных максимумов этой гистограммы, для каждого из них выбрать стеки, принадлежащие к этому диапазону высот, и попробовать создать из них плоский слой, покрывающий все основание палеты.

Задача все равно оставалась намного сложнее, чем простое составление гистограммы высот. Во-первых, не все комбинации из двух, трех или четырех коробок сложатся в хороший стек. Так, если поставить длинную и узкую коробку в пару с квадратной – в таком стеке будет много пустого места, и нижняя или верхняя поверхность этого стека будет покрывать только часть площади его основания. Или, например, вариант «песочных часов»: две одинаковых широких и плоских коробки, а между ними – высокая с ощутимо меньшей площадью основания. Такой стек будет неустойчивым, и, кроме того, будет продавливаться середина нижней коробки.

В целом стеки из всевозможных комбинаций упаковок нужно отфильтровать по объемной эффективности (процент пустого места от всего объема, занимаемого стеком, – произведения его горизонтальной площади на высоту), по критерию «песочных часов» – чтобы площадь самой маленькой коробки была не намного меньше площади самой большой, – и так, чтобы площади верхней и нижней поверхности стека занимали достаточную долю от площади основания. Лучшие стеки – те, где все коробки примерно одинаковой длины и ширины. После такой фильтрации остается еще достаточно много стеков, из которых можно выбирать. Скажем, в выборке из 70 коробок из первоначальных 916 895 вариантов может остаться порядка 100 000 вполне приемлемых. Максимальные значения гистограмм в таком случае могут содержать более 1000 стеков.

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

Скажем, у нас имеются стеки примерно равной высоты, содержащие следующие комбинации номеров коробок:

1, 12, 19, 34;

8, 11, 19, 41;

1, 22, 32;

12, 15, 41.

Если мы выбираем первый стек для построения слоя, ни один другой для него больше не подходит: коробка 19, присутствующая во втором стеке, уже использована в первом, как и коробка 1 из третьего стека, и коробка 12 – из четвертого. Если же мы начнем со второго стека, мы должны исключить первый и четвертый, тогда как третий не имеет общих коробок со вторым. В этом случае два стека (второй и третий) можно добавить в коллекцию стеков для плоского слоя.

* * *

В первоначальном варианте алгоритма я опробовал примерно такой порядок действий. Сначала выбираем один из интервалов высот, куда попадает максимальное число приемлемых стеков. Сортируем стеки в каждом таком интервале по качеству, определяемому как комбинация объемной эффективности, «песочных часов» и еще нескольких подобных критериев. Начинаем отбор с первого стека. В следующих стеках, если какая-то коробка из комбинации, составляющей его, использована в уже отобранных стеках, данный стек пропускается. Если все коробки новые – стек добавляется к коллекции. Таким образом мы доходим до конца списка стеков в этом интервале высот или прекращаем поиск, когда набралось достаточное число стеков, чтобы сделать слой, – возможно, с некоторым избытком, например, чтобы общая площадь проекций стеков в коллекции на 20 % превышала площадь основания палеты. В результате такой процедуры может получиться, например, коллекция стеков с порядковыми номерами в отсортированной последовательности: 1, 3, 8, 17, 31, 50, 78 и т. д. Чем ближе к концу последовательности, тем больше разница между соседними отобранными номерами: все больше коробок уже использовано и все меньше вероятность того, что в следующем стеке окажутся только новые коробки.

Вышеупомянутая процедура подразумевает «жадный» (greedy) подход: на каждом этапе алгоритма мы выбираем ход, лучший в данный момент в локальном смысле. Но чтобы найти более оптимальное решение в глобальном смысле, нужно на каждом этапе рассматривать не только лучший в данный момент ход, но и второй по оптимальности и т. д. Такой подход требует намного большего количества вычислений, чем «жадный». Например, если исключить из рассмотрения первый – самый лучший – стек и начать коллекцию со второго или даже третьего стека, в некоторых случаях можно получить коллекцию, более приближенную к оптимальной. Это возможно тогда, когда коробки из первого стека присутствуют во многих стеках в верхней части отсортированного списка, и нам придется исключить их, так что в коллекции останутся стеки с более высокими порядковыми номерами, хуже качеством и меньшей численности. Предположим, в высотном диапазоне всего 200 стеков, и если начать с первого, то получится следующая коллекция: 1, 11, 32, 53, 89, 142, 190. Если же начать со второго, то коллекция будет такой: 2, 3, 8, 14, 26, 33, 52, 85, 101, 141, 162, 173. Эта коллекция содержит больше стеков в среднем лучшего качества: среднее качество стеков примерно обратно пропорционально усредненному номеру стеков в коллекции. Если же начать с третьего стека, то получится еще одна коллекция, отличная от предыдущих.

У коллекции, начавшейся с первого стека, больше шансов оказаться лучшей из возможных (на практике коллекции, начинающиеся с первого стека, выигрывали у последующих более чем в половине случаев), у начавшейся со второго – значительно меньше, с третьего – еще меньше. Перебирая все возможные коллекции, получим слишком много вариантов. Лучшие варианты статистически сосредоточены в начале такой процедуры отбора.

В процессе мне нужно было выработать критерий оптимальности, и он далеко не прост. Допустим, мы сравниваем две коллекции стеков. Одна – с общей площадью оснований в 84 % от площади основания палеты и 5 % пустого пространства (95 % объемной эффективности) по всем стекам. Другая коллекция – с общей площадью оснований в 96 % от площади палеты, но с объемной эффективностью 82 % в среднем по всем стекам. Какая из них лучше? Окончательного ответа нельзя дать до того, как эти стеки будут упакованы на двумерной плоскости внутри основания палеты. Скорее всего, не все стеки второй коллекции поместятся на этом пространстве, то есть эффективная общая площадь будет не 96 %, а меньше, скажем, 85 %. В этом случае первая коллекция (если все ее стеки будут упакованы в слой) образует слой лучшего качества. Но если очень повезет и все стеки второй коллекции поместятся в указанное пространство, тогда вторая коллекция будет, скорее всего, предпочтительнее первой – между стеками будут очень узкие щели, хоть и в среднем больше пустого пространства внутри самих стеков.

Предсказать заранее качество коллекции из начального списка всех возможных стеков разной высоты совсем не просто. Один диапазон высот мог дать несколько хороших коллекций, а другой, с изначальным числом стеков, не меньшим, чем в первом, – всего лишь одну хилую коллекцию с плохим покрытием площади палеты.

* * *

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

Я прогонял через алгоритм типичные наборы коробок в заказах склада в Ньюбурге, и… результат превзошел даже самые мои оптимистические ожидания. Я написал на Матлабе функцию, которая визуализировала полученные стеки. Каждый из них представлялся в виде нескольких прямоугольников, чья длина и ширина соответствовала размерам коробок, с общим центром (как стеки и должны выглядеть сверху), с обозначением высоты каждого стека и с указанием того, какие коробки из набора были использованы в данной коллекции. В диапазоне высот с разницей до 12 мм из самых полных ячеек гистограммы часто получалось 12–15 или даже больше стеков с общей площадью, значительно превышающей площадь основания палеты. Большинство стеков имели достаточно хорошую форму (основания коробок в них были похожи друг на друга). Оказалось, что почти всегда можно будет построить хорошо заполненный плоский слой из стеков! И это уже была фантастика!

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

Но в тот момент я уже чувствовал: успех вполне возможен. Задачу трехмерной упаковки удалось разделить на два независимых этапа – одномерную упаковку (нахождение стеков по высоте) и двумерную (упаковка прямоугольников). С последней я никогда еще не сталкивался и был совершенно не в курсе, какие существуют способы решения этой задачи.

* * *

Шли последние дни 2010 г. Новый год мы поехали встречать на горнолыжный курорт Киллингтон, штат Вермонт. Ни в гондоле подъемника, ни даже во время спусков на лыжном склоне меня не оставляли мысли о том, как можно сложить стеки в слое палеты. Ну, например, одна наивная идея: разделить основание палеты на ячейки (не обязательно равные, но образующие регулярную сетку), каждая из которых вмещала бы один стек. Стеки могли сильно отличаться и по форме, и по размеру, так что в такой сетке между ними во многих случаях оставалось бы большое пространство. Но даже такое решение, наверное, было бы лучше, чем разваливающиеся палеты в Ньюбурге с башнями из коробок и сквозящими пустотами между ними.

Я поискал в интернете схожие существующие алгоритмы, но не нашел ничего впечатляющего. Хоть задача упаковки прямоугольников и намного проще, чем трехмерная упаковка, но все же она весьма масштабна. Алгоритмы оптимальной упаковки, скажем, для 10 и 100 прямоугольников, скорее всего, будут разительно отличаться друг от друга. В моем случае, при характерных размерах коробок, число прямоугольников (оснований стеков из коробок) варьировалось от 4 до почти 30. К тому же в практическом смысле вариант моей задачи был не вполне классическим. В случае, когда общая площадь прямоугольников превышает площадь палеты, какие-то из них останутся не упакованы, и здесь есть свои критерии оптимальности. Например, лучше упаковать в данный слой стеки из тяжелых и прочных коробок, чтобы оставшиеся легкие коробки оказались в более высоком слое палеты. Или упаковать в слой коробки одной категории товара, оставив другие категории на последующие слои.

В первых числах января у меня появилась идея, как это можно сделать. Самую первую, очень сырую версию упаковки прямоугольников мне удалось закончить всего за несколько дней. Я сам до сих пор не понимаю, как такая сложная задача, требующая в обычном режиме многих месяцев разработки, дала важные результаты настолько быстро – почти мгновенно по меркам нормального планирования исследований.

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

Алгоритм немного напоминал тот, что я уже сделал для слоев из стеков. Только его центральной идеей было составление не стеков одинаковой высоты, а горизонтальных рядов стеков так, чтобы их общая длина совпадала со стороной палеты (или была чуть меньше). Этот принцип проиллюстрирован на рисунке ниже. За первым рядом, выровненным по одной стороне палеты (прямоугольники A, B, C, D), следует другой ряд (прямоугольники E, F, G, H), максимально прижатый к первому, но уже не выровненный по линии, так как верхний край первого ряда не ровный, а напоминает городской силуэт из разных домов-многоэтажек. За вторым рядом мог следовать третий – и т. д., если в основании палеты еще хватало места. Если нет – процесс упаковки завершали отдельные прямоугольники, втиснутые там, где для них оставалось свободное пространство.

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

Если смотреть на это так, чтобы сторона, по которой выровнен первый ряд, находилась внизу картинки, то процедура слегка напоминает игру в тетрис. Нужно укладывать фигуры, разворачивая их так, чтобы в ряду укладки оставалось как можно меньше пустот. Все фигуры – это простые прямоугольники, но они могли быть любого размера, с разным соотношением длины и ширины. Каждый ряд состоял, как правило, из трех, четырех или пяти прямоугольников (в среднем их число варьировалось от двух до шести). Но какие-то из них могли быть развернуты по длине, а другие – по ширине. Например, один ряд мог состоять из трех прямоугольников, уложенных по длине, и двух – по ширине. Возможных комбинаций было огромное множество. Даже из коллекции, состоящей из 10 прямоугольников, можно было почти всегда подобрать десятки комбинаций, составляющих ряд с общей длиной всего на несколько миллиметров меньше ограничительной длины – основания палеты плюс полей размером около 20 мм, за которые коробки могут выступать.

Как и в случае подборки коробок в стеки, возможных комбинаций было намного больше, чем позволяли перебрать реальные вычислительные ресурсы. На каждом шаге решение могло ветвиться на огромное множество следующих шагов. Основная задача состояла в том, чтобы всякий раз выбрать небольшое число самых перспективных вариантов и отбросить остальные. Этот подход называется «ветвление и обрезание» (branch and bound) и широко используется в оптимизационных задачах. Я никогда специально не изучал его и действовал чисто по интуиции. Это оказалось вполне оправданным и дало в итоге отличные результаты.

Варианты ветвились и по другим категориям. Допустим, мы выбрали первый ряд из четырех прямоугольников, хорошо покрывающих сторону палеты. Но коробки можно поместить на сторону палеты в любой последовательности, например (слева направо) – 1–2–3–4 или 1–2–4–3, – и т. д. до 4–3–2–1. Если мы выбрали после этого второй ряд, его можно разместить, прислонив к первому (или опустить на первый, как при игре в тетрис), также в любой из перестановок. Только одна из них даст оптимальный результат (минимум пустого пространства между рядами), а некоторые вариации одних и тех же рядов будут весьма «дырявыми».