Но я был еще очень далек от окончательной победы. Даже если удастся найти достаточное число хороших стеков для построения плоского слоя, их нужно упаковать внутри основания палеты. Эту проблему – упаковки множества разных прямоугольников внутри одного большого – еще оставалось решить, и она была очень, очень трудна.
Но в тот момент я уже чувствовал: успех вполне возможен. Задачу трехмерной упаковки удалось разделить на два независимых этапа – одномерную упаковку (нахождение стеков по высоте) и двумерную (упаковка прямоугольников). С последней я никогда еще не сталкивался и был совершенно не в курсе, какие существуют способы решения этой задачи.
Шли последние дни 2010 г. Новый год мы поехали встречать на горнолыжный курорт Киллингтон, штат Вермонт. Ни в гондоле подъемника, ни даже во время спусков на лыжном склоне меня не оставляли мысли о том, как можно сложить стеки в слое палеты. Ну, например, одна наивная идея: разделить основание палеты на ячейки (не обязательно равные, но образующие регулярную сетку), каждая из которых вмещала бы один стек. Стеки могли сильно отличаться и по форме, и по размеру, так что в такой сетке между ними во многих случаях оставалось бы большое пространство. Но даже такое решение, наверное, было бы лучше, чем разваливающиеся палеты в Ньюбурге с башнями из коробок и сквозящими пустотами между ними.
Я поискал в интернете схожие существующие алгоритмы, но не нашел ничего впечатляющего. Хоть задача упаковки прямоугольников и намного проще, чем трехмерная упаковка, но все же она весьма масштабна. Алгоритмы оптимальной упаковки, скажем, для 10 и 100 прямоугольников, скорее всего, будут разительно отличаться друг от друга. В моем случае, при характерных размерах коробок, число прямоугольников (оснований стеков из коробок) варьировалось от 4 до почти 30. К тому же в практическом смысле вариант моей задачи был не вполне классическим. В случае, когда общая площадь прямоугольников превышает площадь палеты, какие-то из них останутся не упакованы, и здесь есть свои критерии оптимальности. Например, лучше упаковать в данный слой стеки из тяжелых и прочных коробок, чтобы оставшиеся легкие коробки оказались в более высоком слое палеты. Или упаковать в слой коробки одной категории товара, оставив другие категории на последующие слои.
В первых числах января у меня появилась идея, как это можно сделать. Самую первую, очень сырую версию упаковки прямоугольников мне удалось закончить всего за несколько дней. Я сам до сих пор не понимаю, как такая сложная задача, требующая в обычном режиме многих месяцев разработки, дала важные результаты настолько быстро – почти мгновенно по меркам нормального планирования исследований.
Рис. 3. Идея алгоритма в том, чтобы составлять не стеки одинаковой высоты, а горизонтальные ряды стеков так, чтобы их общая длина совпадала со стороной палеты (или была чуть меньше)
Алгоритм немного напоминал тот, что я уже сделал для слоев из стеков. Только его центральной идеей было составление не стеков одинаковой высоты, а горизонтальных рядов стеков так, чтобы их общая длина совпадала со стороной палеты (или была чуть меньше). Этот принцип проиллюстрирован на рисунке ниже. За первым рядом, выровненным по одной стороне палеты (прямоугольники A, B, C, D), следует другой ряд (прямоугольники E, F, G, H), максимально прижатый к первому, но уже не выровненный по линии, так как верхний край первого ряда не ровный, а напоминает городской силуэт из разных домов-многоэтажек. За вторым рядом мог следовать третий – и т. д., если в основании палеты еще хватало места. Если нет – процесс упаковки завершали отдельные прямоугольники, втиснутые там, где для них оставалось свободное пространство.