Одной из наиболее распространенных задач оптимизации является маршрутизация транспортных средств , цель которой — найти наилучшие маршруты для парка транспортных средств, посещающих набор локаций. Обычно под «лучшими» подразумеваются маршруты с наименьшим общим расстоянием или стоимостью. Вот несколько примеров проблем с маршрутизацией:
- Компания по доставке посылок хочет назначить водителям маршруты для доставки.
- Компания кабельного телевидения хочет назначить маршруты для звонков технических специалистов на дом.
- Компания по совместному использованию поездок хочет назначить водителям маршруты для посадки и высадки пассажиров.
Самая известная задача маршрутизации — это задача коммивояжера (TSP): найти кратчайший маршрут для продавца, которому необходимо посетить клиентов в разных местах и вернуться в исходную точку. TSP можно представить в виде графа, в котором узлы соответствуют местоположениям, а ребра (или дуги) обозначают прямое перемещение между местоположениями. Например, на графике ниже показан TSP всего с четырьмя точками, обозначенными A, B, C и D. Расстояние между любыми двумя точками определяется числом рядом с ребром, соединяющим их.
Подсчитав расстояния всех возможных маршрутов, можно увидеть, что кратчайшим маршрутом является ACDBA, для которого общее расстояние равно 35 + 30 + 15 + 10 = 90 .
Проблема усложняется, когда локаций становится больше. В приведенном выше примере всего шесть маршрутов. Но если локаций десять (не считая начальной точки), количество маршрутов равно 362880. Для 20 локаций число подскакивает до 2432902008176640000. Перебор всех возможных маршрутов гарантированно приведет к нахождению кратчайшего, но это вычислительно трудноразрешима для всех, кроме небольших наборов локаций. Для более крупных задач необходимы методы оптимизации, позволяющие разумно искать пространство решений и находить оптимальное (или близкое к оптимальному) решение.
Более общая версия TSP — это задача маршрутизации транспортных средств (VRP), в которой имеется несколько транспортных средств. В большинстве случаев VRP имеют ограничения: например, транспортные средства могут быть рассчитаны на максимальный вес или объем предметов, которые они могут перевозить, или водители могут быть обязаны посещать места в определенные временные интервалы, запрошенные клиентами.
OR-Tools может решить многие типы VRP, включая следующие:
- Задача коммивояжера — классическая задача о маршруте, в которой имеется только одно транспортное средство.
- Задача маршрутизации транспортных средств , обобщение TSP с несколькими транспортными средствами.
- VRP с ограничениями вместимости , при которых транспортные средства имеют максимальную вместимость для предметов, которые они могут перевозить.
- VRP с временными окнами , в которых транспортные средства должны посещать локации в заданные промежутки времени.
- VRP с ограничениями по ресурсам , например, по пространству или персоналу для загрузки и разгрузки транспортных средств в депо (начальная точка маршрутов).
- VRP с исключенными посещениями , при котором транспортные средства не обязаны посещать все места, но должны платить штраф за каждое исключенное посещение.
Ограничения на решение задач выбора маршрута транспортных средств
Проблемы маршрутизации транспортных средств по своей сути неразрешимы: время, необходимое для их решения, растет экспоненциально с размером проблемы. Для достаточно больших проблем OR-Tools (или любому другому программному обеспечению для маршрутизации) могут потребоваться годы, чтобы найти оптимальное решение. В результате OR-Tools иногда возвращает хорошие, но не оптимальные решения. Чтобы найти лучшее решение, измените параметры поиска решателя. Пример см. в разделе Изменение стратегии поиска .