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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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