MilleMiglia: реалистичный генератор сценариев для логистики «средней мили».
MilleMiglia устраняет разрыв между академической теорией и промышленной логистикой, предоставляя реалистичные эталонные показатели с открытым исходным кодом, которые позволяют исследователям оптимизировать сложные сети доставки «средней мили», что в конечном итоге приводит к созданию более надежных и эффективных глобальных цепочек поставок.
Быстрые ссылки
- Бумага
- Код
- Делиться
Как получается, что голландский пофферт доставляется к вам домой, на расстояние 700 км, уже на следующий день? Это стало возможным благодаря тщательной оптимизации логистики, особенно на промежуточном этапе. Эта часть пути является самой длинной, составляет значительную часть общих затрат и, что наиболее важно, определяет, будет ли ваш пофферт свежим или несвежим.
Исследования в области логистики исторически фокусировались на «первой миле» (перемещение товаров от производителей до первоначальных пунктов консолидации) и «последней миле» (доставка потребителю). Оба этапа обычно моделируются как варианты задачи маршрутизации транспортных средств (VRP). Однако «средняя миля», которая обеспечивает перемещение больших объемов товаров между распределительными центрами в региональном или континентальном масштабе, получила значительно меньше внимания в исследованиях операционной деятельности, несмотря на то, что составляет значительную часть общих логистических расходов. Академический прогресс в оптимизации «средней мили» сдерживается отсутствием общедоступных высококачественных данных. Действительно, большинство логистических компаний рассматривают топологию своих сетей и объемы спроса как крайне конфиденциальную информацию.
Логистика «средней мили» находит широкое применение в цепочке поставок. Она включает в себя перемещение товаров с заводов к потребителям в электронной коммерции и розничным магазинам в центрах городов, а также доставку необходимых комплектующих с отдельных заводов и центральных складов на автопроизводителей и в магазины. Сюда также входят срочные перевозки, например, транспортировка фармацевтических препаратов с регулируемой температурой между складскими помещениями и больницами.
Логистика «средней мили» заполняет пробел между первой и последней милей.
Для решения проблемы отсутствия стандартизированных данных в этой области, в статье «Новый генератор экземпляров для моделирования логистических сетей средней мили» мы представляем MilleMiglia, генератор экземпляров на C++, предназначенный для создания реалистичных эталонных задач для проблем доставки на средней миле. Эта работа служит основополагающим элементом для будущих исследований. В этой статье мы рассматриваем уникальные ограничения средней мили и то, как MilleMiglia успешно учитывает их для генерации реалистичных данных, обеспечивающих конфиденциальность. Исходный код и документация доступны на GitHub.
Логистический спектр: первая, последняя и средняя миля.
Различие между логистикой первой, средней и последней мили заключается в пути, который проходит отдельная партия груза. На протяжении всего этого пути основная операционная задача состоит в эффективном использовании автопарка для посещения нескольких пунктов назначения. Рассмотрим пример производителя, который продает товары на типичной онлайн-площадке для доставки отдельным потребителям.
В логистике «первой и последней мили» конкретный груз остается в одном транспортном средстве от места отправления (завод на первой миле, распределительный центр на последней миле) до места назначения (распределительный центр на первой миле, клиент на последней миле). Эти задачи маршрутизации транспортных средств (VRP) предполагают оптимизацию парка из нескольких транспортных средств в течение ограниченного промежутка времени, обычно одного дня. Задача оптимизации по сути сводится к распределению и упорядочиванию: определению того, какое транспортное средство будет обрабатывать какой набор грузов и в каком порядке.
В нашем примере «первая миля» соответствует сбору товаров, проданных производителем (например, поффертс ), а «последняя миля» охватывает окончательную доставку потребителям (некоторые из которых довольно голодны!). В обоих случаях один грузовик перевозит товары в региональный распределительный центр или из него. Однако, если производитель и потребитель находятся в разных регионах, логистика «средней мили» заполняет пробел между удаленными распределительными центрами. Например, товары от производителя из Гронингена (Нидерланды) сначала попадают в региональный распределительный центр в Утрехте, затем в другой центр в Париже (Франция), прежде чем быть доставленными потребителю в Версаль.
В отличие от первой и последней мили, средняя миля представляет собой эстафету. Один и тот же груз может перевозиться несколькими разными транспортными средствами по континентальной сети, прежде чем достигнет конечного пункта назначения, возможно, через неделю после отправления. В промежуточных распределительных центрах груз может быть разгружен, отсортирован по месту назначения и объединен с другими грузами, прежде чем быть погруженным на следующее транспортное средство. Это создает сложную проблему синхронизации: груз должен прибыть в распределительный центр в течение определенного временного интервала, чтобы успеть на запланированный отправление грузовика. Если он пропустит запланированный рейс, ему придется ждать в распределительном центре до следующего цикла, что приведет к значительным задержкам.
В нашем примере, после прибытия товара производителя в региональный центр Утрехта, он загружается в первый грузовик, следующий в Антверпен (Бельгия), и доставляется в тот же день. Поскольку ближайший грузовик в Париж заполнен, и предположим, что клиент выбрал стандартную доставку, на следующий день товар отправляется из Антверпена в Париж вторым грузовиком. Посылка прибывает в Париж ночью второго дня, где попадает в сеть доставки «последней мили» для окончательной доставки клиенту на следующий день.
Жизненный цикл груза: от производителя в Гронингене (Нидерланды) до клиента в Версале (Франция) большая часть пути проходит по сети промежуточных пунктов экспедитора.
Ограничения математического моделирования и решателей.
Математическая структура доставки «средней мили» отличается от стандартной программы VRP по нескольким ключевым параметрам.
В традиционной задаче маршрутизации транспортных средств (VRP), например, решаемой с помощью инструментов с открытым исходным кодом, таких как OR-Tools, или специализированных API, таких как Google Maps Platform Route Optimization (GMPRO), цель обычно состоит в оптимизации маршрутов для автопарка. Основное внимание уделяется маршрутизации транспортных средств и последовательности остановок для соблюдения жестких сроков выполнения заказов клиентов. В отличие от доставки «последней мили», логистика «средней мили» обладает дополнительной гибкостью, позволяющей перемещаться между грузовиками. Мы моделируем это дополнительное измерение как задачу многотоварного потока на пространственно-временном графе. В этих моделях:
- Узлы: Представляют собой данные о конкретном распределительном центре в определенный временной интервал.
- Дуги: Отражают перемещение транспортных средств во времени или нахождение груза на складе распределительного центра (хранение/сортировка по месту назначения).
Жесткие ограничения
Хотя многие академические задачи маршрутизации виртуальных машин определяются с небольшим количеством ограничений, ограничения, накладываемые на этапе «промежуточного звена», трудно ослабить без искажения структуры рассматриваемой операционной проблемы:
- Фиксированное расписание: Транспортные средства, как правило, работают по фиксированному расписанию, которое необходимо соблюдать.
- Пропускная способность распределительного центра: Распределительные центры имеют физические ограничения на объем товаров, которые могут быть отсортированы или перегружены в течение часа.
- Синхронизация: Прибытие одного транспортного средства является необходимым условием для отправки грузов другим транспортным средством.
Из-за этих зависимостей существующие решатели задачи маршрутизации транспортных средств не могут применяться к доставке «средней мили». Задача требует последовательности промежуточных распределительных центров и распределения грузов между несколькими транспортными средствами, часто в течение нескольких дней.
MilleMiglia: Создание реалистичных эталонных показателей
Распределения, управляемые данными
Компания MilleMiglia использует различные статистические распределения, чтобы гарантировать, что синтетические сети выглядят как реальные распределительные сети, не раскрывая при этом никакой конфиденциальной информации:
- Пространственное распределение: Распределительные центры размещаются с использованием гравитационных моделей или пространственной кластеризации, чтобы отразить реальную плотность населения и промышленных предприятий.
- Спрос: Отправка грузов формируется на основе пар «пункт отправления — пункт назначения» с учетом реалистичного распределения объемов и веса.
- Ротации: Генератор создает структурированные графики движения транспортных средств, а не произвольные связи между узлами, соединяя либо два крупных распределительных центра, либо крупный распределительный центр и соседние, меньшие по масштабу распределительные центры.
Данные распределения получены путем интерполяции между общедоступной информацией от участников отрасли и данными, раскрытыми в частном порядке.
Производительность и масштабируемость
Программа MilleMiglia написана на C++. Она использует протокол Protocol Buffers для сериализации данных, благодаря чему данные во всем их многообразии могут храниться в одном файле для каждого экземпляра. Таким образом, сгенерированные экземпляры являются компактными и могут легко использоваться решателями, написанными на разных языках программирования.
В отличие от задач маршрутизации транспортных средств (VRP), имеющих множество вариантов, таких как CVRP (с указанием пропускной способности ), VRPTW (с указанием временных окон ) или PDPTW ( погрузка и разгрузка с указанием временных окон ), для учета разнообразных операционных требований, структура нашего формата данных для маршрутов средней протяженности включает все важные ограничения в одном и том же формате файла: фиксированные графики движения транспортных средств, ограничения пропускной способности распределительных центров и сложные условия синхронизации — все это фундаментальные элементы структуры задачи.
Цель состоит в том, чтобы предоставить сообществу ряд примеров:
- Небольшие примеры: Эквивалентны академическим «игрушечным» задачам для проверки точных алгоритмов.
- Примеры из промышленной сферы: крупномасштабные проблемы, охватывающие целые континенты. Для решения таких проблем требуются сложные эвристические или метаэвристические методы.
- Размеры могут быть любыми промежуточными , встречаются также экземпляры среднего размера и/или твердости.
Генератор также позволяет создавать сценарии обучения, поскольку он может генерировать огромные наборы данных для тренировки алгоритмов машинного обучения.
Совместные исследования и решения будущих задач
MilleMiglia — это первый шаг к стандартизированному набору инструментов для сравнительного анализа логистики на средних дистанциях, аналогичному тому, что предоставляет CVRPLIB (Capacitated Vehicle Routing Problem Library) для сообщества VRP.
Этот проект является результатом продолжающегося сотрудничества между Google и академическими партнерами из Университета Брешии и ENPC в Париже. Помимо генерации экземпляров, в настоящее время мы работаем над специализированным решателем и API, разработанным специально для решения операционных задач на промежуточных этапах доставки. Этот решатель призван использовать уникальную структуру потоков на промежуточных этапах.
Выпустив наш генератор экземпляров в открытом доступе, мы надеемся побудить более широкое исследовательское сообщество сосредоточиться на операционных проблемах «средней мили», что приведет к созданию более надежных и эффективных глобальных цепочек поставок. Мы надеемся запустить конкурс по проблемам «средней мили», чтобы повысить интерес со стороны ученых и разработчиков промышленных решателей к этой малоизученной, но нуждающейся в оптимизации области. Любой желающий может начать с ознакомления с примером экземпляра, размещенным в репозитории GitHub.
Благодарности
Данное исследование было проведено в основном Айманом Лотфи во время его работы в качестве студента-исследователя в Google и Маттео Петрисом (в настоящее время в ENPC Paris) в рамках продолжающегося сотрудничества. Благодарим Тибо Кювелье и Бруно Де Бакера за их вклад в эту работу. Особая благодарность Клаудии Арчетти (в настоящее время в Университете Брешии) за ее лидерство и поддержку.
Источник: research.google
Оцените материал:
