Транспортные задачи и оптимальные маршруты.

Поиск оптимальных путей в логистике - мощный инструмент, позволяющий существенно сэкономить время и деньги.

Транспортная задача или задача Монжа-Канторовича - это классическая задача линейного программирования о построении оптимального плана перевозок грузов из пунктов отправления в пункты назначения с минимальными затратами.

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

Леонид Канторович был удостоен Нобелевской премии за вклад в математическую экономику.


В статье "Транспортные задачи в Python и Tableau" я показал пример поиска оптимальных и неоптимальных маршрутов такси. Геометрия дорог не учитывается - рассматриваются прямые, соединяющие точки посадки с точками высадки. На визуализации можно оценить изменение общей длины маршрутов - почти в 5 раз.

Для иллюстрации задачи были взяты координаты 392 отелей на Манхэттене и 392 местоположений такси (все данные с Kaggle). Представим, что нужно все такси отправить во все 392 отеля для 392 постояльцев в один момент.

Для решения задачи в Python используется библиотека "POT: Python Optimal Transport".

〰 Берутся точки начала маршрутов (Source) и точки концов маршрутов (Target).
〰 Строится матрица расстояний или затрат на перемещение (Cost Matrix)
〰 Вычисляются оптимальные маршруты на матрице Optimal Transport
〰 Визуализируются траектории

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

У компании беспилотного такси Waymo есть патент "Route optimization for autonomous driving systems" - в нём описывается способ оптимизации маршрута для автономного автомобиля. Но там всё сложнее, и оптимальные траектории зависят не только от расстояния, но и от других факторов. Оптимальность здесь - баланс безопасностью, данными, надежностью и временем. А Weymo уже начинает локально замещать Uber в Штатах.

Решение сложных транспортных задач задач в масштабах государств находит применение в таких областях как:
〰 Расчёт местоположения логистических центров
〰 Планирование маршрутов транспорта при проведении крупных мероприятий (например, Олимпийские игры или Чемпионат мира по футболу)
〰 Строительство и развитие дорожной инфраструктуры

@data_bar 🍀