Этот пост вдохновлен статьей Дэмиана Лопеза из Decision Lab Who wants to figure out how to pack anyway, опубликованной на Medium.
Проблема трехмерной упаковки в контейнер — одна из наиболее частых на складах и в логистике. Ее решение заключается в заполнении контейнера (коробки или поддона) предметами как можно ближе друг к другу, чтобы сократить количество требуемых контейнеров.
А вы знали, что начали решать эту проблему еще в детстве? Вспомните игру «Тетрис» — отличное упражнение по использованию пространства в условиях дефицита времени.
Вы также наверняка сталкивались с этой проблемой, когда собирали вещи для переезда или отпуска. В обоих случаях, чем больше свободного места в коробке или чемодане вы оставляете, тем больше коробок или чемоданов потребуется.
Если их немного, при упаковке можно положиться на интуицию и опыт (как мы все обычно делаем). Но что, если у вас десятки коробок? В логистике интуиция и просчеты могут привести к оплате лишнего поддона или грузовика — а это существенные расходы для компании.
Decision Lab решила протестировать три метода упаковки. Она сравнила математическую оптимизацию, обучение с подкреплением и алгоритм, основанный на наборе правил, чтобы определить наиболее эффективный из них.
Оптимизация
Для математической оптимизации Decision Lab указала целевую функцию и ограничения, а также использовала математический оптимизатор для поиска решения. В качестве целевой функции компания установила сокращение до минимума пустого пространства контейнеров, чтобы снизить количество используемых контейнеров.
Обучение с подкреплением и моделирование
Обучение с подкреплением — это подход к машинному обучению, при котором решения, принятые в текущем состоянии, влияют на те, что будут приняты в следующем. Он применим в сценариях, в которых важен контекст, и этим отличается от математической оптимизации.
В любом сценарии обучения с подкреплением вам нужны состояние, действие и функция вознаграждения.
Агент в процессе обучения с подкреплением узнает, какое действие следует предпринять для этого состояния. Когда агент получает информацию об окружающей среде (состоянии), он совершает действие. В зависимости от влияния этого действия на окружающую среду агент получает вознаграждение — либо положительное, либо отрицательное. Этот процесс многократно повторяется, чтобы увеличить ценность вознаграждения.
Для обучения такого агента Decision Lab использовала Microsoft Bonsai. Bonsai интегрируется с AnyLogic и помогает инженерам, бизнес-аналитикам и специалистам по имитационному моделированию, не имеющим опыта работы с ИИ, создавать, тренировать и внедрять агентов в свои проекты.
Чтобы решить проблему упаковки в контейнеры, компания разработала имитационную модель ленточного конвейера, перемещающего товары в зону упаковки. Decision Lab интегрировала модель с платформой Bonsai и использовала ее, чтобы обучить агента.
Одна из тех политик, которых должен был придерживаться обучаемый агент, заключалась в том, что товар на ленточном конвейере обрабатывался по мере поступления и помещался в контейнер. Когда агент заканчивал упаковку этого товара, он переходил к следующему.
Кроме того, Decision Lab позволила агенту заранее видеть следующий элемент, чтобы он мог выполнять ограниченное планирование.
Таким образом, этот подход намного сложнее, чем математическая оптимизация, при которой данные обо всех предметах, подлежащих упаковке, заранее известны. Наш агент, наоборот, в процессе обучения видит только один предмет из случайной последовательности.
Когда все было готово, Decision Lab провела эксперименты, чтобы сравнить обучение с подкреплением и оптимизацию с алгоритмом, основанным на наборе правил. Результаты показали, какая стратегия позволяет достичь наибольшей плотности при упаковке предметов в течение ограниченного времени.
В этом посте мы рассмотрела две из трех стратегий. Посмотрите видео (на англ.), чтобы узнать, какая из них оказалась наиболее успешной. Подробности проекта и результаты сравнения:
Теперь вы знаете, как решить проблему упаковки в контейнеры, и можете добавить выигрышную стратегию к своему опыту игры в «Тетрис» и сборов в отпуск.
Больше новостей и свежих статей по имитационному моделированию — в нашей ежемесячной рассылке.
