В прошлой статье мы препарировали математику «Алгоритма Динамического Шампура» на примере задачи коммивояжера. Однако, каким бы элегантным ни был «голый» код, в отрыве от бизнес-процессов он остается лишь академическим упражнением. Реальная ценность любой разработки проявляется в её прикладном применении — там, где алгоритм начинает экономить время, топливо и место на складе.
Логичным продолжением нашей работы стал перенос инерционной логики «Шампура» в плоскость трехмерной упаковки.
Если в TSP мы боролись за миллиметры пути, то здесь мы боремся за каждый кубический сантиметр полезного пространства. Это переход от абстрактных точек к физическим объектам, которые имеют вес, габариты и — что самое важное в логистике — свою очередность разгрузки. Перед нами встал прикладной вызов: не просто эффективно заполнить объем, а создать масштабируемую систему, способную учитывать LIFO-последовательность для многоточечных рейсов и требования к развесовке.
На текущий момент эта методология и её программная реализация проходят регистрацию в Роспатенте, и сегодня я поделюсь результатами того, как этот подход работает в «боевых» условиях: от формирования 2D-рядов до полной 3D-загрузки. Причем область применения не ограничивается фурами — это могут быть трюмы судов, склады маркетплейсов или любые системы хранения, где пространство стоит денег.
<cut />
Архитектура решения: Синергия инерции и комбинаторики
Главная сложность любой объемной упаковки — экспоненциальный рост вариантов. Если просто перебирать все возможные положения каждой коробки, расчет затянется на часы. Чтобы сохранить скорость (те самые доли секунды), мы разделили процесс на три иерархических уровня.
Уровень 1: Векторный «Шампур» (Стратегия)
На верхнем уровне алгоритм по-прежнему мыслит векторами. Он определяет «магистраль» заполнения пространства. В случае с транспортом — это движение от передней стенки к задним дверям. Но это не просто прямая: «Шампур» задает очередность зон ответственности для разных точек разгрузки (LIFO). Сначала мы формируем «виртуальный объем» для самого дальнего города, затем для следующего, и так далее. Это гарантирует, что груз будет выходить из системы ровно в том порядке, в котором он в нее зашел.
Уровень 2: Адаптивный «Скребок» (Тактика)
Внутри каждой зоны включается логика «Скребка». Вместо того чтобы искать место для каждой коробки в отдельности, мы формируем слои и ряды.Здесь проявляется важная инженерная деталь: динамические допуски. Мы ввели параметры погрешности по ширине и высоте, которые привязаны к средним габаритам объектов. Алгоритм «разрешает» себе небольшие зазоры в текущем ряду, если это позволяет сохранить общую инерцию заполнения и избежать геометрических тупиков в будущем.
Уровень 3:Subset Sum движок (Исполнение)
Когда вектор задан и слой определен, в дело вступает «микро-оптимизатор». Чтобы заполнить ширину ряда максимально плотно, мы используем модифицированный алгоритм задачи о сумме подмножеств.
Как это работает: Алгоритм анализирует доступные контейнеры и через динамическое программирование находит комбинацию ширин, которая идеально (или с минимально допустимым зазором) вписывается в габарит трюма.
Результат: Мы получаем «ювелирную» подгонку объектов друг к другу, при этом время расчета одного такого ряда остается в пределах миллисекунд.
Такой трехслойный пирог позволяет нам не жертвовать скоростью ради плотности: стратегия «Шампура» бережет время, а тактика «Скребка» и рюкзака — каждый кубический сантиметр.
От плоскости к объему: геометрический предел в 2D
Прежде чем переходить к полноценной 3D-укладке, необходимо было отладить работу алгоритма в двух измерениях. 2D-упаковка стала для нас своего рода «лабораторным стендом». На этом этапе связка «Скребка» и Subset Sum движка показала, что заполнение плоскости с КПД, стремящимся к 100%, нескольких тысяч объектов за 1-2 секунды — задача технически решенная.
На первой (монохромной) анимации наглядно представлена работа алгоритма в чистом геометрическом поле. Благодаря внедрению «умного допуска» по ширине (ПШ), система ювелирно подбирает комбинации объектов, формируя ряды практически без зазоров.
В процессе этих изысканий мы решили две важные инженерные задачи:
Оптимизация памяти (Backtracking):
Первая версия алгоритма буквально «захлебывалась» в памяти, пытаясь хранить все возможные комбинации путей для каждой суммы. Мы пересмотрели подход, внедрив метод обратных указателей («хлебных крошек»). Теперь система хранит лишь минимальные кортежи связей, восстанавливая финальную цепочку объектов только в момент принятия решения. Это позволило снизить потребление RAM в десятки раз и обрабатывать массивы в 10 000+ объектов на обычном ноутбуке.Симметричная ротация:
Алгоритм перестал быть «заложником» исходной ориентации контейнера. В каждом ряду «Скребок» оценивает объект дважды: как он ложится в текущую высоту «дворника» в оригинальном виде и после поворота на 90 градусов. Это добавило системе гибкости — если коробка не подходит как «стена», она может идеально лечь как «плита», дополнительно уплотняя ряд.
Высокая плотность в 2D подтвердила: инерционная логика позволяет формировать структуру предсказуемо, сводя риск возникновения случайных пустот к минимуму. Однако в реальной логистике «чистая геометрия» — это только половина дела. Настоящие вызовы начались при переходе в объем.
Добавляем вес и высоту: переход к 3D
Реальный транспортный отсек диктует свои правила, где к геометрии добавляется физика. Как только мы ввели ось Zcap Z 𝑍 и весовые параметры грузов, задача перешла в разряд многофакторной оптимизации. Здесь в игру вступила система весовых приоритетов и цветовая индикация.
На второй (цветной) анимации можно увидеть работу весового фильтра в динамике.
Теперь «Шампур» управляет не только объемом, но и центром тяжести. Алгоритм распределяет массивные контейнеры на нижних ярусах, оставляя легкий груз для верхних полок. Для промышленной эксплуатации это критически важно: высокая плотность упаковки не имеет смысла, если нарушена устойчивость платформы. В итоге мы получили систему, которая находит баланс между коммерческой эффективностью (заполнением пространства) и требованиями безопасности.
Мы отказались от дорогостоящего копирования массивов внутри циклов. Вместо того чтобы таскать за собой "рюкзак" с индексами для каждой возможной суммы, мы применили метод обратного отслеживания через кортежи (index, prev_sum). Это превратило наш движок из прожорливого скрипта в эффективный вычислительный инструмент, способный переваривать тысячи контейнеров на обычном ноутбуке
Когда КПД перевалил за 89%, мы уже открывали шампанское. Но Unit-тесты на коллизии (AABB) окатили нас ледяной водой: 306 пересечений. Алгоритм оказался слишком жадным — в погоне за плотностью он начал ставить коробки друг на друга. Оказалось, что допуск PSV позволял деталям быть выше лидера ряда, из-за чего они "прошивали" потолок. Исправление одной строчки h_row = max(...) снизило КПД на 0.5%, но вернуло нас в реальный мир, где коробки не умеют проходить сквозь стены
Исправив коллизии, мы столкнулись с новой проблемой: "эффект перелива". Когда алгоритм подстраивает высоту ряда под самую высокую деталь, общая высота груза неминуемо растет. Один контейнер на самой вершине трюма вылетел за габариты всего на пару единиц. Это научило нас, что проверка границ должна быть финальным аккордом в каждом цикле укладки.
Подводя итог, можно сказать, что путь от базовой укладки с КПД 58% до комплексной 3D-модели с эффективностью под 90% стал отличным инженерным вызовом. Нам удалось не просто "запихать" коробки в трюм, а научить алгоритм соблюдать правила реальной логистики: очередность выгрузки по городам (LIFO) и весовой баланс для остойчивости судна. Финальным аккордом стало внедрение 12 Unit-тестов, которые подтвердили отсутствие коллизий и соблюдение всех физических границ. На разработку и отладку этого "цифрового грузчика" ушло немало сил, но результат в виде стабильных "12 PASSED" и скорости обработки 14 000 объектов в секунду говорит сам за себя — система готова к реальным задачам
Реальное LIFO: Мы упаковали 6000 объектов для 3 разных городов. Города 1 и 2 загружены на 100%, что гарантирует отсутствие лишних движений при разгрузке — «первый зашел, последний вышел».
Плотность vs Физика: При КПД почти 90% мы не забыли про безопасность. Средний вес распределен так, что самые тяжелые ярусы находятся внизу и в середине, обеспечивая устойчивость судна или фуры.
Визуальный контроль: Каждая секунда анимации — это результат работы сотен итераций Subset Sum, который в реальном времени находит идеальное место для каждого груза.
Испытания и бенчмарки: когда алгоритм встречается с реальностью
Чтобы подтвердить эффективность метода «Динамического Шампура», мы провели серию стресс-тестов на массиве из 6000 объектов разного габарита и веса. Для чистоты эксперимента мы сравнили наши результаты с классическим «жадным» алгоритмом (First Fit Decreasing) и продвинутыми эвристиками, которые часто используются в подобных задачах.
Сравнительная таблица эффективности (3D-кейс, 6000 объектов)
Критерий | Традиционный "Жадный" метод | Продвинутые эвристики | Shampur-Scraper Method |
|---|---|---|---|
КПД (заполнение объема) | 68–74% | 80–84% | 88.21% 🏆 |
Учет LIFO (города) | Практически невозможен | Требует ручной правки | Нативная поддержка |
Время расчета | < 1 сек | 40–150 сек | 12.6 сек ⚡ |
Развесовка (Безопасность) | Игнорируется | Опционально | Интегрирована в ядро |
Прыжки (лишние переходы) | Хаотичные | Снижены | Отсутствуют (0) ✅ |
Результаты стресс-тестирования (30+ сценариев)
Алгоритм прошел через «геометрический ад» в 30 различных сценариях. Мы проверяли систему на устойчивость в экстремальных условиях:
«Длинномеры»: Упаковка объектов, длина которых составляет более 70% длины трюма.
«Микро-объекты»: Обработка 5000+ элементов размером со спичечный коробок (тест на утечку ��амяти и вычислительную стабильность).
«LIFO-конфликт»: Ситуация, когда тяжелый груз для самого первого города (глубина фуры) мешает загрузке легкого груза для последнего. Система успешно нашла баланс приоритетов, не обрушив общий КПД.
«Численная нестабильность»: Тесты на коллинеарность (точки на одной линии) и микроскопические допуски.
Итог испытаний: алгоритм не только показывает высокую плотность заполнения в 88.21%, но и делает это со скоростью 362 контейнера в секунду, что позволяет использовать его в real-time системах управления складом и транспортом.
Заключение: от алгоритма к экосистеме
Подводя итог второй части исследования, можно констатировать: инерционный подход к упаковке — метод «Динамического Шампура» — доказал свою эффективность не только в теории траекторий, но и в прикладной задаче заполнения объемов. КПД на уровне 88% в 3D-пространстве при строгом соблюдении LIFO-очередности — это тот результат, который позволяет перевести логистические расчеты из режима «на глазок» в режим математически обоснованного плана.
Мы научили систему чувствовать физику процесса: «осаживать» тяжелые грузы на пол трюма, учитывать последовательность разгрузки и мгновенно адаптироваться к разным габаритам. Но даже самый совершенный алгоритм остается лишь набором функций, если он заперт в локальном Python-скрипте.
"Мы начали с простого алгоритма полочной упаковки с КПД 58%, который был эффективен, но расточителен. Перейдя к 3D-моделированию, внедрив динамическое программирование для поиска идеальных сумм (Subset Sum) и приоритизацию грузов по городам (LIFO) и весу, мы подняли плотность загрузки до 84.79%. При этом система сохраняет высокую скорость расчетов, обрабатывая 400 контейнеров в секунду."
Это готовый кейс. Можно запускать сервис «Шампур-Логистик»! 🔥
В следующей, финальной статье цикла мы совершим качественный скачок: разберем, как превратить этот математический движок в полноценный высоконагруженный микросервис.
Впереди нас ждет:
Стек технологий: Как FastAPI, Celery и Redis распределяют нагрузку при расчете сотен планов погрузки одновременно.
География в БД: Зачем нам понадобился PostGIS и как мы храним маршруты и точки остановок.
Интерфейс в кармане: Telegram WebApp как окно в 3D-мир. Как передать тысячи координат из облачного воркера в браузер мессенджера через SSH-туннели и вебхуки.
Битва с инфраструктурой: Те самые «грабли» асинхронности и сессий, на которые мы наступили, чтобы вы по ним не ходили.
Метод «Шампура» уже навел порядок в геометрии и объемах. Пришло время навести порядок в архитектуре.
Что дальше:
⭐ Поставьте звезду, если интересно
💬 Напишите в Issues, для каких задач хотите попробовать
🤝 Коммерческое использование? Напишите в личку
