В рамках серии статей о выдающихся достижениях в математической оптимизации руководитель направления систем бизнес-аналитики BIA Technologies Станислав Воронин рассказывает о кейсе «Кока-колы», которая экономит около $45 млн в год за счет оптимизации маршрутов своих грузовиков

Задача

Помимо собственно колы, компания Coca-Cola продает целый ряд напитков, включая минеральную воду, холодные чаи, соки и газировки под брендами Fanta, Sprite и Schweppes. Производством и дистрибуцией всех этих продуктов занимаются частично принадлежащие The Coca-Cola Company партнерские компании. В начале нулевых крупнейшей из них была Coca-Cola Enterprises (в 2016 году она будет преобразована в результате слияния в Coca-Cola Europacific Partners). В 2005 году Coca-Cola Enterprises (CCE) распространила 42 миллиарда бутылок и банок — 20% от мирового объема компании Coca-Cola.

Автопарк CCE являлся вторым по величине в Соединенных Штатах после почтовой службы США. Он вырос с 13 000 транспортных средств в 1986 году до 54 000 к началу нулевых. Гигантский рост и высококонкурентный характер индустрии напитков поставили компанию перед необходимостью оптимизировать доставку продукции. Перед CCE стояли следующие задачи: обеспечить эталонное обслуживание клиентов, оптимизировать затраты, сократить потребление природных ресурсов и предложить своим сотрудникам продуктивный, но реалистичный график работы.

Компания хотела получить автоматизированное решение для ежедневного построения оптимальных маршрутов движения заказов от более чем 430 распределительных центров до 2,4 миллиона точек розничной торговли (магазинов и торговых автоматов).

В данном случае математическая модель имеет дело как со стандартными ограничениями в задаче маршрутизации (вместимостью транспортного средства и максимальной продолжительностью маршрута), так и с некоторыми специфическими ограничениями, а именно:

  • Рабочее время водителя и время начала работы должны соответствовать правилам Министерства транспорта. Водители должны иметь при себе права на управление грузовым автомобилем, в которых указываются дополнительные разрешения (например, разрешение на перевозку опасных материалов, управление транспортным средством с пневматическим тормозом или управление тягачом с прицепом).
  • Система должна соблюдать требования к конкретному типу транспортного средства и оборудованию для каждого заказа и/или торговой точки (например, подъемные ворота, квалификация сотрудников, сертификаты или лицензия). Парк CCE состоял из 15 типов грузовиков, которые отличались по размеру, грузоподъемности, расположению базы, структуре затрат и доступному оборудованию.
  • Схемы движения должны избегать определенных районов, таких как центр города в часы пик.
  • В модель должны быть заложены временные окна приемки в торговых точках. Розничные магазины постоянно сокращают временные окна, и многие магазины требуют, чтобы компания доставляла товары либо до их открытия, либо после закрытия.
  • Система должна учитывать очень конкретное и точное время разгрузки и мерчандайзинга. Оно различается в зависимости от типов торговых точек и типов транспортных средств.
  • Должны быть учтены особые правила загрузки товара для определенных типов транспортных средств.
  • Модель должна учитывать требования к минимальному размеру заказа для определенных типов транспортных средств.
  • По возможности, количество водителей, которых видит каждый конкретный клиент (сотрудник магазина), следует ограничить тремя или четырьмя.

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

Решение

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

  1. Построение начальных маршрутов на основе алгоритма последовательной вставки.
  2. Улучшение маршрутов на основе алгоритмов локального поиска.
  3. Оптимизация визуальной привлекательности плана с помощью функции кластеризации (диспетчеры предпочитают «визуально привлекательные» планы, то есть похожие на те, что выдавались предыдущей системой планирования, с минимальным количеством перекрывающихся маршрутов и с группированием торговых точек на пути движения).
  4. Назначение водителей на маршруты с учетом их знаний о регионе и налаженных отношений с сотрудниками торговых точек (система старается сделать так, чтобы водители как можно чаще посещали торговые точки, с которыми они уже знакомы).

Результат

К концу 2005 года более 300 диспетчеров CCE в 25 подразделениях компании (каждое из которых отвечает примерно за 30 распределительных центров и охватывает доставку в одну европейскую страну или несколько американских штатов) начали ежедневно использовать новую систему для оптимизации маршрутов примерно 10 000 грузовиков.

Внедрение системы позволило увеличить продуктивность водителей и обеспечить доставку большего количества товара в те же сроки, сократить расход топлива, а также свести к минимуму случаи пропуска доставки и повысить ее предсказуемость, тем самым лучше подстраиваясь под временные предпочтения сотрудников магазинов. Всё это помогло CCE значительно улучшить качество обслуживания клиентов, снизить стоимость доставки на $0,03 в расчете на один ящик и добиться ежегодной экономии затрат в размере $45 миллионов.

Решение оказалось настолько успешным, что Coca-Cola поспешила распространить его за пределы CCE — на другие компании по розливу напитков (например, Coca-Cola HBC, которая обслуживает 25 стран, в основном в Восточной Европе) и дистрибьюторов пива (Carlsberg, Heineken, Inbev и др.).

В 2007 году математики, создавшие оптимизационную модель для Coca-Cola, стали финалистами Премии Франца Эдельмана за достижения в области исследования операций (лауреатами в тот год стали создатели системы оптимизации планирования лучевой терапии, о которой я недавно рассказывал). Подробнее о кейсе Coca-Cola можно прочитать в статье из научного журнала Interfaces, где ежегодно публикуются описания проектов-финалистов Премии Франца Эдельмана.

Актуально

Решения BIA

bia-tech.ru использует cookie-файлы для корректной работы и анализа использования сайта согласно политике использования файлов cookie. Отключить cookie можно в настройках браузера.

Понятно