Коммивояжеры XXI века: как оптимизировать маршруты доставки

Руководитель направления систем бизнес-аналитики BIA Technologies Станислав Воронин объясняет, что такое задача коммивояжёра, почему её решение стоит $1 миллион, и как математики помогают компаниям увеличить свою прибыль.

Фото: freepik vectorjuice
Фото: freepik vectorjuice

Классическая транспортная задача

Одна из первых и самых известных задач математической оптимизации — так называемая задача коммивояжёра — была сформулирована в 1930 году. Суть её заключается в поиске наиболее выгодного (кратчайшего и самого дешёвого) маршрута, пролегающего через указанные города по одному разу с последующим возвратом домой.

Несмотря на простоту формулировки, нахождение оптимального пути является по-настоящему сложной проблемой. Количество возможных маршрутов возрастает экспонентально с увеличением числа городов. Если их 66 и более, решить задачу простым перебором вариантов ни одна вычислительная машина не сможет быстрее, чем за несколько миллиардов лет.

В 2000 году Математический институт Клэя назвал задачу коммивояжёра в числе семи Проблем тысячелетия. За решение любой из них назначен приз в 1 миллион долларов. По состоянию на 2021 год элегантный алгоритм для решения задачи коммивояжёра по-прежнему не найден. По ссылке можно посмотреть захватывающую визуализацию нескольких подходов к проблеме, которые, впрочем, не дают оптимального результата.

Начиная со второй половины XX века решение проблемы коммивояжёра используется в качестве модели для разработки новых алгоритмов оптимизации. Среди практических применений модификаций задачи — секвенирование ДНК, изготовление печатных плат (планирование пути передвижения станка для сверления отверстий) и, конечно, построение транспортно-логистических маршрутов.

Последнее актуально в первую очередь для розничной торговли, интернет-магазинов, курьерских сервисов, служб доставки ресторанов и dark kitchen, сервисов переезда офисов, квартир и домов, да и вообще для доставки любых товаров — от продуктов или цветов до крупногабаритных грузов вроде мебели или товаров для ремонта.

Математическая оптимизация доставки

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

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

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

Западные компании, помимо критериев скорости и экономии, закладывают в математическую модель ещё и показатель экологичности: при сокращении количества транспорта и холостых пробегов снижается количество выбросов углекислого газа в атмосферу. Потребители и регуляторы поощряют компании, которые следуют ESG-принципам устойчивого развития. Чтобы удержаться на рынке, отечественным службам доставки тоже в скором времени придётся перенять этот тренд.

Финальное звено цепочки (от склада до клиента) называют «последней милей доставки». Система планирования последней мили должна учитывать пропускную способность склада, количество машин в распоряжении компании, ситуацию на дорогах, физические ограничения по грузоподъемности и вместимости грузовиков, а также пожелания клиентов о временном диапазоне доставки (порой допустимое «окно» составляет всего 15 минут).

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

При внутригородской доставке возникает особенно много различных форс-мажоров (отказ клиента, появление срочного заказа день в день, пробки на дорогах), и план, сформированный утром, может претерпевать большое количество изменений в течение дня. Построить такой динамично меняющийся маршрут «на коленке» невозможно, поэтому дальнейшее развитие индустрии перевозок будет немыслимо без автоматизированных систем математического моделирования.

Оптимизация аэропортов и перелётов

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

Таким образом главная задача математической оптимизации для авиакомпании — сформировать полётную сетку так, чтобы самолёты не простаивали ни минуты без дела. При этом модель должна учитывать график конкурентов, погодные условия, регламентное время на осмотры и пополнение топливных запасов.

Компании-лоукостеры отличает как раз максимальная оптимизация расписания полётов, которая помогает им удерживать более низкую цену на билеты по сравнению с конкурентами. Обратная сторона медали — лоукостеры не могут позволить себе выбиться из графика, поэтому при регистрации на рейс действует принцип «кто не успел — тот опоздал». Отсюда и жёсткие ограничения по ручной клади: чем меньше у пассажиров сумок, тем быстрее они осуществляют посадку на самолёт.

Помимо сетки полётов, оптимизировать можно также расписание работы персонала. Эффект подобной оптимизации недавно оценила российская авиакомпания NordStar, которая воспользовалась услугами компании-разработчика ПО для автоматизации графика работы (до 2020 года расписание экипажа составлялось вручную). Это решение помогло NordStar сократить операционные расходы, повысить эффективность работы команды и минимизировать задержки рейсов.

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

В авангарде цифровой оптимизации сейчас находятся оба аэропорта города Рим. Их оператор, компания Aeroporti di Roma (ADR), одной из первых осознала происходящую трансформацию классических аэровокзалов в своеобразные торгово-развлекательные центры. Она проанализировала большие данные о поведении пассажиров (а речь почти о 50 миллионах человек в год) и оптимизировала всю логистику на территории аэропортов так, чтобы сократить время ожидания и направить покупателей к ресторанам и магазинам. Эти изменения помогли ADR существенно увеличить выручку и занять первое место в рейтинге европейских аэропортов, наиболее высоко оцениваемых пассажирами.

Мы как потребители не замечаем, как именно компании адаптируются под наши всё растущие ожидания и запросы. А делают они это с помощью методов математического моделирования. Анализ больших данных и алгоритмы нахождения наилучшего решения помогают выстраивать бизнес в новых условиях, оптимизировать маршруты и удовлетворять прихоти клиентов в кратчайшие сроки. Впрочем, предел эффективности пока не достигнут: задача на миллион по-прежнему ждёт своего решения.

P. S. Пожалуйста, пишите в комментариях, что вам интересно узнать о мире математической оптимизации, и я непременно затрону это в будущих статьях :)

1313
4 комментария

Господи, как вспомню как переезжала с 400 кг вещей, всей мебелью и техникой из Перми в Москву, очень удивлялась, почему вещи просто нельзя было перевести из точки А в точку Б, а обязательно нужно провозить через четыре промежуточных пункта. Что-то кажется я теперь начала понимать, почему :) Ну, или нет )

Ладно, не буду больше на весь фейсбук ругать службы доставки, так и быть )

4
Ответить

да, все так. Решение задачи для каждого отдельного груза не всегда выглядит оптимальным. Выгода видна только на общем объеме перевозок.

2
Ответить

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

1
Ответить

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

1
Ответить