Телеграмм чат группы prog

⁠Дневник капитана, желтая ДАТАВРЕМЯ(2020, 3, 24).

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

Я вспомнил, что читал статью гуру запросов ildarovich'а как раз о решении задачи 3D упаковки. С предвкушением легкой добычи пошел качать файл обработки и понял... что его нет. К сожалению, хотя для саморазвития можно сказать, что и к счастью, Сергей привел не полное решение задачи, а только некоторые выдержки и объяснение общих принципов. Поэтому пришлось вооружиться мозгами, свести это все в единое целое, оптимизировать для текущего проекта.

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

Алгоритм был реализован, и он даже заработал. Я был горд собой, еще больше горд и благодарен ildarovich'у. Однако вся радость разбилась о жесткие реалии бизнеса. У заказчика отгрузки, оказалось, обычно насчитывают тысячи коробок. При таких объемах компьютер уходил в долгое раздумье из которого, кажется, уже не возвращался. Какого-то результата можно было добиться, если сделать более грубые вычисления, но тогда уже не стоило говорить об оптимальности решения.

Начал искать онлайн сервисы для решения такой задачи (кстати, официально она называется Bin packing) с API. Нашел бесплатный иностранный сервис packit4me. Прикольно в нем было то, что он не только проводит вычисления, но потом еще возвращает ссылку на страницу с визуализацией всего этого в 3D. Красиво, но не очень практично, упаковщики не будут вертеть фигуры на мониторе, им нужны печатные формы со схемой упаковки. Однако главная проблема этого сервиса была в том, что он считал тоже не очень оптимально. Т.е. вычислял быстро, но иногда такая фигня получалась, как в анекдоте про машинистку.

Дальнейшие поиски привели меня к конечной остановке - российскому платному сервису packer3d. Тут все серьезно, в основе их разработки лежат научные работы, применяются нейросети и генетические алгоритмы. И сервис работает действительно хорошо, за несколько минут вычисляется решение для огромного числа коробок и намного оптимальней других вариантов.

В итоге, поставленная задача была решена, хоть и не так как предполагалось в начале. Зато конфигурация предоставляла три варианта решения:
1. Оффлайн, бесплатно, но долго и не очень оптимально;
2. Онлайн, бесплатно, быстро, но не очень оптимально;
3. Онлайн, платно, но быстро и оптимально.
Можно выбирать любое по вкусу.