Если вы следили за моими предыдущими статьями, то знаете, что я одержим скоростью в задачах оптимизации.Сначала была «точка»: мы приручили задачу коммивояжера (TSP), решив её векторным способом — 10 000 точек за 0.4 секунды. Затем была «топология»: мы усложнили мир, победили злую спираль и упрямый трилистник, научились работать с графами (искать тупики) и упаковали 45 000 стандартных контейнеров в трюм, учитывая LIFO, весовые лимиты и еще 4 критических параметра. Тогда наш воркер на FastAPI + Redis справлялся за 2 минуты. И вот подошли к царь-задаче Упаковка разногабарита. Результатом этой работы станет публичный API. Логика простая: вы отправляете JSON с параметрами груза и склада (нужен ли обсчет крена, лимиты по весу, LIFO), а на выходе получаете готовый план загрузки.
Стандарты современного логистического сервиса
Что отличает качественный сервис оптимизации загрузки? На текущем уровне развития индустрии недостаточно просто «впихнуть» груз в объем. Профессиональный инструмент обязан поддерживать четыре критических параметра:
LIFO (Last In, First Out): Соблюдение очередности выгрузки. Груз, который должен покинуть борт первым, обязан находиться в зоне прямой доступности.
Весовые ограничения (Stack Limit): Учет допустимой нагрузки на нижние слои. Мы не можем поставить многотонный станок на коробку с электроникой.
Скорость расчета: В условиях реального порта или склада план погрузки, который считается часами, бесполезен. Решение должно приниматься за доли секунды.
Балансировка (Центр тяжести): Равномерное распределение массы по осям судна или склада.
Если первые три пункта в нашей системе уже реализованы на базе «Гибридного Шампура» и пакетной обработки, то четвертый — балансировка — потребовал отдельной инженерной интеграции
Визуальный баттл: Как мы учили алгоритм «чувствовать» вес
Чтобы проверить работу балансировки в деле, мы создали стресс-тест test_visual_balancing_battle. Условия задачи специально подобраны так, чтобы «сломать» обычный геометрический упаковщик:
Тяжелая артиллерия: 20 монолитных блоков по 5 тонн каждый.
Легкая пехота: 200 коробок по 20 кг для заполнения пустот.
Ограниченное пространство: Узкий трюм (2.4 м шириной), где любая ошибка в распределении веса моментально уводит судно в крен.
Описание что видим:
Случай №1 (
use_cog=False): Алгоритм работает как обычный строитель. Он видит «дырку» слева — кладет туда блок. Видит следующую — кладет рядом. Ему плевать, что блок весит 5 тонн, он видит только его габариты В итоге весь свинец уехал на левый борт. Крен 16% — судно тонет.Случай №2 (
use_cog=True): Алгоритм работает как старпом. Положил блок слева — весы качнулись. Он тут же говорит MaxRects-у: «Следующий клади только справа!». Он буквально «жонглирует» весом в реальном времени. Крен 0.04% — судно стоит ровно, как скала.
Раздел: Когда физика встречается с математикой
Мы убедились: алгоритм умеет не просто паковать «тетрис», но и чувствовать вес. Крен в 0.04% против 16% в слепом режиме — это победа физики над голым геометризмом.
Но что со скоростью? Хо��оший логистический сервис — это когда все четыре параметра (LIFO, Вес, Базовые габариты и Балансировка) считаются одновременно. Чтобы наш API не «висел» под нагрузкой, мне нужно решение, которое выдает результат не за минуты, а за доли секунды. Ведь в реальном порту или на складе очередь из фур ждать не будет.
Погодите, я что-то слышу... Да, да точно. Слышу это слово: «Миллион».
Миллион
Нет, мне не послышалось. Это я сам себе говорю: «А давай проверим производительность Гибридного Шампура на миллионе айтемов?».
Для тех, кто не читал прошлые части: мой «Шампур» — это алгоритм, который «нанизывает» задачи на стратегический вектор движения. Но если раньше мы работали со стандартными контейнерами, то теперь нам нужно упаковать «зоопарк» из коробок всех мастей. Чтобы делать это эффективно, я совместил Шампур с эвристикой MaxRects.
Тактический инструмент: Пару слов о MaxRects
Нельзя просто так использовать алгоритм и не помянуть добрым словом Юкку Ютилу (Jukka Jylänki). Его фундаментальная работа «A Thousand Ways to Pack the Bin» — это библия для каждого, кто хоть раз пытался эффективно разложить спрайты в атласе или коробки в контейнере.Саму статью Юкки я не читал, но его метод нарезки пространства — это база, которую я взял и заставил работать на стероидах
Холодный душ от NumPy и 34 Гб памяти
Первым делом мы решили не мелочиться и выкатили параметры настоящего океанского гиганта: 200 метров в длину, 25 в ширину и 30 в высоту. План был дерзкий: создать 3D-сетку с шагом в 1 мм и честно обсчитать коллизии.
Но тут вмешался NumPy и выдал «предупреждение», которое выглядело как вежливая пощечина:
Сообщение было ясным: «Друг, чтобы я просто создал тебе пустой трюм с такой точностью, мне нужно 35 ГБ оперативной памяти здесь и сейчас».
Делать софт, который «падает» на обычном ноутбуке — сомнительное удовольствие. Но давайте будем честны: если перед вами стоит задача обсчитать склад или трюм длиной в 200+ метров с миллиметровой точностью, то экономить на оперативной памяти — это как пытаться заправить океанский лайнер из садовой лейки.
Для домашнего ПК — это предел.
Для условного Maersk или логистического хаба мирового уровня — это стоимость одного обеда в портовой столовой. Если оптимизация загрузки экономит хотя бы 1% топлива или времени простоя, компания с радостью выделит сервер с терабайтом RAM.
Однако, оставаясь в рамках здравого смысла и имея в распоряжении стандартные 32 Гб, мы решили «умерить аппетит» и перешли к тестам на 200 000 объектов. Этого объема более чем достаточно, чтобы проверить алгоритм на прочность, не превращая тестовый стенд в суперкомпьютер.
Тест-драйв «Флота» (Реалистичный сценарий)
Мы создали четыре конфигурации судов. На этот раз мы работаем в честных единицах, которые позволяют не просто «раскидать» груз, а реально проверить, как Гибридный Шампур справляется с плотностью и весовым балансом.
Тип судна | Габариты (м) | Время расчета | Успешность (шт) | Плотность (КПД) |
|---|---|---|---|---|
Feeder (Малый) | 60 x 20 x 10 | 0.04 сек | 14 960 (7.5%) | 64.27% |
Handysize (Средний) | 150 x 25 x 15 | 0.15 сек | 60 930 (30.5%) | 44.29% |
Panamax (Гигант) | 250 x 32 x 20 | 0.66 сек | 161 900 (81.0%) | 42.94% |
ULCV (Левиафан) | 400 x 60 x 30 | 0.76 сек | 200 000 (100%) | 11.37% |
Бенчмарк: Мы против «индустриальных стандартов»
Когда заходит речь об упаковке 3D-объектов (Bin Packing Problem), на рынке обычно доминируют два подхода: либо тяжеловесные математические солверы (типа Gurobi/CPLEX), либо специализированные библиотеки на Python/C++.
Давайте сравним наш «Гибридный Шампур + MaxRects» с типичными представителями класса по ключевым параметрам.
Сводная таблица производительности
Параметр | Типичный Open-Source | Коммерческие движки | Наш Гибридный Шампур |
|---|---|---|---|
Скорость (объектов/сек) | 10 – 100 шт/сек | 1 000 – 5 000 шт/сек | 150 000 – 440 000+ ⚡🚀 |
Масштабируемость | Падает после 1 000 шт | Тяжело идет до 10к | Легко держит 1 000 000+ 🤯 |
Учет LIFO / Очереди | Через «костыли» | Да, но тормозит | Вшито в ядро (Векторно) 🎯 |
Динамический крен | ❌ Нет | Опционально (дорого) | Native (в каждом цикле) ⚖️ |
Обработка ULCV (400м) | Зависнет навсегда | ~ 20-40 минут | 0.76 секунды! 😱💥 |
Почему это выглядит как магия?
Многие спросят: «Как Python-скрипт может обгонять промышленные решения на C++ в сотни раз?».Все дело в том, что мы перестали играть по правилам «одна коробка за раз».
Векторный Batching: Мы не итерируем по миллиону объектов. Мы используем мощь NumPy для пакетной укладки целых SKU.
MaxRects как скальпель: Мы не ищем место «методом тыка», мы мгновенно нарезаем свободное пространство на идеальные прямоугольники.
Отсечение комбинаторики: «Шампур» ограничивает область поиска узким фронтом погрузки, предотвращая комбинаторный взрыв, который «душит» конкурентов.
0.76 секунды на 200 000 объектов.Это не просто цифры. Это новая реальность для логистики, где план погрузки пересчитывается мгновенно при каждом чихе на складе.
Вместо эпилога: О точности и скорости
Меня часто спрашивают: «Слушай, ну при такой бешеной скорости — 400 000 объектов в секунду — насколько точны твои расчеты? Это вообще математика или гадание на кофейной гуще?»
Знаете, когда нас спрашивают, сколько будет 2+2 , мы отвечаем стремительно и быстро:— Около четырех!
И в этом — вся суть инженерного подхода. Если вам нужна академическая точность до нанометра, готовьте суперкомпьютер и ждите неделю. Но если вам нужно упаковать реальный ULCV-левиафан здесь и сейчас, учитывая крен, LIFO и весовые лимиты — добро пожаловать на «Гибридный Шампур».
Мы не просто считаем коробки. Мы управляем хаосом со скоростью света. 🚀⚡
