Руководство по передовой ИИ:«В последние годы индустрия экспресс-доставки в моей стране выросла с развитием Интернета и электронной коммерции, и темпы ее развития были быстрыми. Статистические данные Государственного почтового бюро показывают, что в 2016 году национальный объем экспресс-доставки достиг 31,28 миллиарда штук, что на 51,7% больше, чем в прошлом году. Индустрия экспресс-доставки в Китае быстро растет. С годовым темпом роста более 50% в течение шести лет подряд Китай стал крупнейшей в мире страной экспресс-доставки. непрерывный рост объемов экспресс-доставки, экспресс-доставка не только приносит большое удобство в нашу жизнь, но и увеличивает стоимость упаковки курьерских компаний.В 2016 году национальный курьер израсходовал около 3,2 млрд тканых мешков, 6,8 млрд пластиковых пакетов, 3,7 млрд упаковочных коробок. и 330 миллионов рулонов ленты Чрезмерная упаковка, избыточная емкость, скорость переработки Низкая стоимость привела к увеличению стоимости упаковки, уменьшению пользовательского опыта и большой трате ресурсов, а низкая карбонизация и защита окружающей среды расходных материалов для упаковки должны быть срочно укрепить».
Группа исследований и разработок Suning Logistics, занимающаяся большими данными, использует анализ исторических данных и технологию алгоритмов больших данных для запуска «интеллектуального решения для упаковки», которое объединяет информацию о заказах клиентов, основные данные о товарах, данные о расходных материалах для упаковки и другие связанные данные для оптимизации моделей алгоритмов больших данных и автоматически предоставить клиентам Продукт подтверждает тип упаковочного материала, применение упаковки, определяет последовательность упаковки и положение упаковки, а также реализует интеллектуальное применение упаковки. Благодаря применению интеллектуальных упаковочных решений для складской упаковки Suning Logistics может ежегодно экономить почти 10 миллионов долларов на упаковке. В то же время за счет продвижения и использования новых упаковочных материалов (перерабатываемых «дрейфующих ящиков») поощряется сокращение и переработка упаковки, что не только экономит затраты на упаковку и улучшает качество обслуживания пользователей, но также защищает окружающую среду и экономит Ресурсы. Каждый проходной ящик перерабатывается 2000 раз, спасая примерно 1 10-летнее дерево. Дрифт-боксы запускаются по всей стране, а сэкономленные каждый год курьерские ящики могут облететь Землю.
Интеллектуальная технология упаковки Suning
Консолидация и распаковка
Консолидацию заказа и распаковку можно понимать как две «противоположные» операции.Короче говоря, консолидация заказа — это объединение заказов с одним и тем же адресом доставки в одном временном окне в единое целое, а распаковка — добавление еще одного заказа. доставка согласно бизнес-логике. Цель обеих операций — улучшить качество обслуживания клиентов.
Чтобы обеспечить эффективность объединенных заказов, мы рассматриваем только объединенные заказы, созданные в течение одного и того же временного окна, а не объединяющие заказы в течение дня. В одном и том же временном окне каждый заказ будет сопоставляться с другими заказами.Если обнаружится, что несколько заказов имеют один и тот же адрес доставки, система автоматически объединит эти заказы вместе и объединит их в единое целое. Из-за различных свойств продуктов и ограничения размера упаковочных материалов один и тот же заказ необходимо разделить на несколько пакетов для упаковки. Например, клиенты купили много продуктов для чистки туалетов и продуктов питания во время большой акции.Если два вида продуктов смешать в одну упаковку, качество обслуживания клиентов значительно ухудшится.Поэтому мы разделяем два вида продуктов и упаковки. их в разные пакеты.Доставка в пакете. При этом, если две упаковки не могут вместить весь товар заказчика, то мы разделим товар на несколько упаковок.
После завершения заказа и распаковки и определения количества и типа упаковочных материалов следующим шагом будет вызов алгоритма рекомендаций по упаковке, который порекомендует упаковочные материалы подходящего размера.
Рекомендации по упаковке
Проблема упаковки — классическая и очень важная проблема оптимизации в логистических и производственных системах. Система использует функцию рекомендаций по упаковке, чтобы найти подходящие упаковочные материалы и рекомендовать их бизнес-операторам для упаковки товаров клиента.Рекомендация по упаковке является типичным применением проблемы упаковки.Суть заключается в том, как разумно разместить товары для достижения максимальной скорости упаковки. изменять. Было показано, что двумерная задача упаковки в контейнеры является NP-трудной (Coffman et al., 1980), где NP означает недетерминированный полином (сокращенно NP). Так называемый недетерминизм означает, что для решения задач, которые можно решить за полиномиальное время, можно использовать определенное количество операций. NP-сложная задача — это задача, правильность решения которой можно «легко проверить», где «легко проверить» означает существование полиномиального алгоритма проверки. Соответственно, если все задачи в NP сводятся по Тьюрингу к некоторой задаче, то задача является NP-трудной. Точно так же проблема упаковки трехмерных контейнеров также является NP-сложной задачей.
3D математическая модель упаковки коробок
Ограничения (1), (2), (3) и (4) используются вместе, чтобы гарантировать отсутствие перекрытия позиций разных элементов при размещении элементов. Ограничения (5), (6) и (7) гарантируют, что товар не может быть помещен вне упаковочного материала. Для одного и того же продукта разные методы размещения будут иметь разную длину, ширину и высоту. , ограничения (8), (9) и (10) используются для переопределения длины, ширины и высоты товара i. В начале этого параграфа мы предположили, что все товары являются правильными прямоугольными параллелепипедами, а прямоугольный товар имеет три разных грани, и каждая грань имеет два маятниковых метода, поэтому у товара есть всего 6 различных методов размещения. 6 способов размещения, как показано ниже
Из модели видно, что данная задача представляет собой смешанную задачу целочисленного нелинейного программирования, из-за сложности которой невозможно получить точное решение за разумное время. Короче говоря, эту проблему трудно решить в разумные сроки, и она не может удовлетворить потребности нашего бизнеса в обратной связи и рекомендациях по расчетам в реальном времени, поэтому мы разработали собственный алгоритм рекомендаций по упаковке, чтобы найти лучшее возможное решение.
Алгоритм рекомендаций по упаковке
Для проблемы упаковки есть два фактора, которые напрямую влияют на скорость упаковки, а именно порядок упаковки товаров и положение упаковки товаров. Для этих двух факторов мы используем разные алгоритмы оптимизации для их решения. Сначала мы использовали генетический алгоритм для оптимизации порядка упаковки продуктов, а затем использовали алгоритм трехмерной упаковки для оптимизации позиций упаковки продуктов.
Общий процесс
Весь процесс алгоритма рекомендации упаковки показан на следующем рисунке. Сначала мы сортируем коробки по убыванию самой длинной стороны и отфильтровываем упаковочные материалы, соответствующие требованиям самой длинной стороны и объема.
Блок-схема алгоритма рекомендаций по упаковке
Затем мы инициализируем последовательность упаковки предметов и используем генетический алгоритм, чтобы внести коррективы в последовательность упаковки предметов. При оценке годности текущего заказа вызываем алгоритм 3D упаковки для размещения товара, если алгоритм упаковки может упаковать весь товар в упаковочный материал согласно текущему заказу упаковки, расчет останавливается. В противном случае продолжите генетический алгоритм, чтобы скорректировать порядок бинирования, а затем оцените пригодность нового порядка. В случае помещения более одного продукта в один и тот же пакет невозможно определить, может ли продукт быть загружен только по наибольшей стороне и объему, поэтому необходимо использовать метод обхода для расчета всех упаковочных материалов по в соответствии с приведенной выше логикой: один проход, а затем найти тот, у которого самая высокая скорость заполнения.
Мы кратко представили общий процесс расчета алгоритма рекомендаций по упаковке. Далее мы углубимся в детали и подробно представим логику реализации каждого модуля алгоритма.
Оптимизация порядка упаковки
В случае упаковки нескольких товаров различные эффекты упаковки могут быть получены путем изменения порядка упаковки товаров. Как показано на рисунке ниже, при размещении сначала мелких предметов, а затем более крупных, результаты упаковки будут различаться.
Сравнительная таблица порядка упаковки
Генетический алгоритм имеет хорошие возможности глобальной оптимизации, поэтому мы выбираем этот алгоритм для оптимизации порядка упаковки. Генетический алгоритм (Genetic Algorithm) — вычислительная модель процесса биологической эволюции, имитирующая естественный отбор и генетический механизм дарвиновской теории биологической эволюции, метод поиска оптимальных решений путем имитации процесса естественной эволюции. Мы использовали реальное кодирование для создания популяций генов, представляющих порядок бинирования. Затем в процессе эволюции мы выполняем операции кроссовера и мутации над выбранными родительскими генами. Как показано на рисунке ниже, скрещивание генов заключается в обмене элементами двух выбранных генов для создания нового потомства. Есть много способов пересечения, здесь мы перечислим некоторые из наиболее часто используемых способов.
Диаграмма примера скрещивания генов
Операция кроссовера в основном предназначена для обеспечения локального обмена информацией в популяции для получения нового потомства, в то время как операция мутации предназначена для добавления новой случайной информации в популяцию. Поскольку эта случайная новая информация может быть полезной информацией, которая способствует сходимости к оптимальному решению, или может быть вводящей в заблуждение информацией, которая заставляет поиск отклоняться от оптимального решения, нам нужно осторожно использовать операцию мутации. Мы используем значение вероятности для управления операцией мутации.При достижении определенной вероятности операция мутации будет активирована для получения новой случайной информации. По сравнению с операцией кроссинговера операция мутации представляет собой операцию трансформации одного гена. Существует также много способов мутации.На следующем рисунке показаны наиболее часто используемые способы мутации.
Диаграмма примера вариации гена
После завершения операции кроссовера и мутации нам необходимо оценить вновь полученный геном. Мы вызываем алгоритм трехмерного биннинга, чтобы попытаться бинировать в соответствии с вновь полученными генами, то есть порядком бинирования.
Оптимизация положения упаковки
В дополнение к порядку упаковки, при упаковке товаров размещение товаров также напрямую влияет на окончательный эффект упаковки. Позиция упаковки включает в себя две подзадачи позиции размещения и способа размещения продукта в упаковочной коробке. На следующих двух сравнительных диаграммах соответственно показано влияние различных положений и методов размещения на результаты упаковки.
Сравнение различных позиций размещения и различных методов размещения
После того, как последовательность упаковки известна, трехмерный алгоритм упаковки решает, как найти нужное место и как разместить предметы. Каждый раз, когда предмет размещается, мы пробуем 6 различных вариантов размещения предмета, чтобы увидеть, какой из них поместится в коробку. Помещая товар в прямоугольное пространство, мы называем свободное пространство, не занятое товаром, остаточным пространством. Алгоритм вырезает остаточное пространство и сохраняет метод вырезания, который может оставить наибольшее остаточное пространство. Поскольку чем больше остаточного пространства остается, тем больше вероятность того, что после этого останется остальная часть товара. Алгоритм будет жадно использовать метод размещения, который может создать наибольшее остаточное пространство среди 6 методов размещения товаров, чтобы обеспечить плавную упаковку оставшихся товаров.
Сравнение планов раскроя
На картинке выше показано сравнение двух разных методов резки. Серая область — это место размещения предыдущего продукта, а A, B, A' и B' — это разные остаточные пространства, созданные двумя разными методами резки. Поскольку площадь A' больше, чем у B, мы склонны придерживаться плана резки B.
В процессе размещения товаров полное пространство непрерывно разрезается на более мелкие остаточные пространства.Когда оставшиеся товары не могут быть размещены во всех остаточных пространствах, алгоритм рассматривает корректировку некоторых остаточных пространств для получения более подходящих мест для размещения товара. Есть много способов настройки, но время вычислений ограничено, поэтому мы искусственно сужаем пространство поиска: только два алгоритма пространства выживших, которые находятся в одной горизонтальной плоскости и имеют общую вершину и ребро, пытаются настроиться. Алгоритм выбирает два остаточных пространства, которые удовлетворяют условиям из всех остаточных пространств, и пытается их подогнать, то есть они находятся в одной горизонтальной плоскости и имеют общую вершину и ребро. Как показано на рисунке ниже, остаточными пространствами до настройки являются A и B соответственно, и эти два пространства имеют общую вершину и ребро. Алгоритм попытается отрегулировать остаточное пространство и сгенерировать новые остаточные пространства A' и B', чтобы попытаться упаковать. Если вновь сгенерированное остаточное пространство может разместить товар, то мы сохраняем план корректировки, в противном случае пытаемся настроить оставшееся остаточное пространство. Регулируя оставшееся пространство, мы более эффективно используем пространство упаковочной коробки.
Сравнительная диаграмма до и после корректировки остаточного пространства
До уравнивания, как показано на рисунке выше, остаточные пространства A' и B' имеют общую ребро (a, b) и вершину b и находятся на одном уровне. После корректировки мы получаем новые пространства A и B, где B может поместить длинные и узкие предметы, которые A' и B' не могли поместиться раньше.
Параллельные вычисления Spark
У Suning 47 складов по всей стране.Ежедневно большое количество упаковок нужно рекомендовать для упаковочных материалов в режиме реального времени.Алгоритм автономной версии не может удовлетворить бизнес-требованиям. Поэтому мы используем Spark Streaming для распараллеливания алгоритма. Как показано на рисунке ниже, вышестоящая система записывает пакетные данные в Kafka в режиме реального времени. Spark Streaming получает данные из разных разделов Kafka в режиме реального времени, генерирует RDD и сохраняет их в памяти, а затем разбивает RDD в памяти по номеру пакета и распределяет их по разным Исполнителям. В каждом отдельном исполнителе вызывается алгоритм рекомендуемого упаковочного материала в режиме реального времени для расчета соответствующих выделенных данных. После завершения расчета каждый Executor записывает результаты расчета, то есть рекомендуемые результаты, в разные разделы Kafka. Затем нижестоящая система получает результаты рекомендаций от Kafka в режиме реального времени.
Схема архитектуры параллельного выполнения алгоритма
Интеллектуальное упаковочное решение Suning было введено в эксплуатацию на складах Suning.Благодаря унификации стандартов расходных материалов для упаковки количество типов расходных материалов для упаковки было сокращено с 30 до 14, а скорость заполнения упаковки была увеличена на 59% на основе улучшения эффективность упаковки. В то же время в восьми городах, включая Пекин, Шанхай, Гуанчжоу, Нанкин, Шэньчжэнь, Ханчжоу, Ухань и Чэнду, поставлено на конвейер более 10 000 перерабатываемых пластиковых ящиков - «плавучих ящиков» длиной около 0,3 метра и шириной 0,2 м., используется для замены обычного картона для загрузки продуктов, приобретаемых потребителями, а доставка «последней мили» осуществляется курьером. Пользователи могут забрать экспресс-доставку в пунктах самовывоза Suning и общественных пунктах сбора.После получения товара сдайте «коробку для дрейфа» обратно в пункт самовывоза для переработки. Кроме того, пользователи также могут выбрать доставку «от двери до двери»: после распаковки и личного осмотра товара ящик передается курьеру для возврата на переработку. Чтобы повысить удобство использования, эти дрейфующие ящики также специально разработаны с прочными «уплотняющими пряжками», чтобы обеспечить безопасность продукта и конфиденциальность пользователя. Внедрение интеллектуального упаковочного решения Suning может ежегодно экономить 10 миллионов юаней на упаковке.В то же время применение «коробок для дрейфа» и различных упаковок для конфиденциальности защищает конфиденциальность покупок клиентов и повышает качество покупок клиентов.
об авторе
Е Мэнсянь, магистр исследования операций и количественной логистики, инженер-алгоритм научно-исследовательского центра Suning Logistics, в основном отвечает за оптимизацию логистики, применение алгоритмов исследования операций и оптимизации в Suning Logistics. Раньше он был старшим аналитиком в Accenture, отвечая за проектирование и разработку алгоритмов, связанных с логистикой. Сосредоточьтесь на оптимизации логистики, исследованиях операций и исследованиях и применении алгоритмов оптимизации, надеясь использовать исследования операций и алгоритмы оптимизации для понимания технологических изменений и развития умной розничной торговли.
Следите за нами в WeChat"Передовая линия ИИ", ответьте "AI" в фоновом режиме, чтобы получить электронную книгу в формате PDF из серии "AI Frontline"