Параметры маршрутизации

В этом разделе описываются некоторые параметры решателя маршрутизации.

Ограничения поиска

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

В следующей таблице описаны наиболее распространенные ограничения поиска.

Имя Тип По умолчанию Описание
solution_limit int64 кинт64макс Ограничьте количество решений, генерируемых во время поиска.
time_limit.seconds int64 кинт64макс Ограничьте в секундах время, проведенное : в поиске.
lns_time_limit.seconds int64 100 Ограничение в секундах времени, затраченного на : завершение поиска для каждого соседа локального поиска.

Стратегия первого решения

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

Вариант Описание
AUTOMATIC Позволяет решателю определить, какую стратегию использовать в соответствии с решаемой моделью.
PATH_CHEAPEST_ARC Начиная с «начального» узла маршрута, соедините его с узлом, создающим самый дешевый сегмент маршрута, затем расширьте маршрут, повторяя последний узел, добавленный к маршруту.
PATH_MOST_CONSTRAINED_ARC Аналогичен PATH_CHEAPEST_ARC , но дуги оцениваются с помощью селектора на основе сравнения, который сначала отдает предпочтение наиболее ограниченной дуге. Чтобы назначить селектор модели маршрутизации, используйте метод ArcIsMoreConstrainedThanArc() .
EVALUATOR_STRATEGY Аналогичен PATH_CHEAPEST_ARC , за исключением того, что стоимость дуг оценивается с помощью функции, переданной в SetFirstSolutionEvaluator() .
SAVINGS Алгоритм сбережений (Кларк и Райт). Ссылка Кларк, Г. и Райт, Дж. В. «Планирование движения транспортных средств из центрального депо в несколько точек доставки», Operations Research, Vol. 12, 1964, стр. 568-581.
SWEEP Алгоритм развертки (Врен и Холлидей). Ссылка Энтони Рен и Алан Холлидей Компьютерное планирование транспортных средств от одного или нескольких складов до нескольких точек доставки Ежеквартальное исследование операций (1970–1977), Vol. 23, № 3 (сентябрь 1972 г.), стр. 333–344.
CHRISTOFIDES Алгоритм Кристофидеса (на самом деле вариант алгоритма Кристофидеса, использующий максимальное соответствие вместо максимального соответствия, что не гарантирует 3/2 коэффициента приближения для метрического коммивояжера). Работает с общими моделями маршрутизации транспортных средств, расширяя маршрут до тех пор, пока на него нельзя будет вставить узлы. Ссылка Никос Кристофидес, Анализ наихудшего случая новой эвристики для задачи коммивояжера, Отчет 388, Высшая школа промышленного администрирования, CMU, 1976.
ALL_UNPERFORMED Сделайте все узлы неактивными. Находит решение только в том случае, если узлы являются необязательными (являются элементом ограничения дизъюнкции с конечными штрафными затратами).
BEST_INSERTION Итеративно создавайте решение, вставляя самый дешевый узел в его самую дешевую позицию; стоимость вставки основана на глобальной функции стоимости модели маршрутизации. По состоянию на 2/2012 работает только на моделях с дополнительными узлами (с конечными штрафными затратами).
PARALLEL_CHEAPEST_INSERTION Итеративно создавайте решение, вставляя самый дешевый узел в его самую дешевую позицию; стоимость вставки основана на функции стоимости дуги. Быстрее, чем BEST_INSERTION .
LOCAL_CHEAPEST_INSERTION Итеративно создавайте решение, вставляя каждый узел в самую дешевую позицию; стоимость вставки основана на функции стоимости дуги. Отличается от PARALLEL_CHEAPEST_INSERTION узлом, выбранным для вставки; здесь узлы рассматриваются в порядке их создания. Работает быстрее, чем PARALLEL_CHEAPEST_INSERTION .
GLOBAL_CHEAPEST_ARC Итеративно соедините два узла, которые создают самый дешевый сегмент маршрута.
LOCAL_CHEAPEST_ARC Выберите первый узел с несвязанным преемником и соедините его с узлом, создающим самый дешевый сегмент маршрута.
FIRST_UNBOUND_MIN_VALUE Выберите первый узел с несвязанным преемником и соедините его с первым доступным узлом. Это эквивалентно стратегии CHOOSE_FIRST_UNBOUND в сочетании с ASSIGN_MIN_VALUE (см. ограничение_решателя.h).

Статус поиска

Вы можете вернуть статус поиска, используя метод status модели маршрутизации. Вот код Python для вывода статуса поиска:

print("Solver status: ", solver.status())

Это печатает целое число со следующими значениями:

Ценить Описание
0 ROUTING_NOT_SOLVED : проблема еще не решена.
1 ROUTING_SUCCESS : проблема успешно решена.
2 ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED : проблема успешно решена после вызова RoutingModel.Solve() , за исключением того, что локальный оптимум не был достигнут. Если оставить больше времени, это позволит улучшить решение.
3 ROUTING_FAIL : решение проблемы не найдено.
4 ROUTING_FAIL_TIMEOUT : достигнут лимит времени до поиска решения.
5 ROUTING_INVALID : модель, параметры модели или флаги недействительны.
6 ROUTING_INFEASIBLE : Проблема оказалась неразрешимой.

Параметры локального поиска

В следующей таблице перечислены варианты стратегий локального поиска (также называемых метаэвристикой ). См. Изменение стратегии поиска для примеров настройки этих параметров.

Вариант Описание
AUTOMATIC Позволяет решателю выбрать метаэвристику.
GREEDY_DESCENT Принимает улучшение (снижение стоимости) соседей локального поиска до тех пор, пока не будет достигнут локальный минимум.
GUIDED_LOCAL_SEARCH Использует управляемый локальный поиск, чтобы избежать локальных минимумов. (см. Управляемый локальный поиск ) это, как правило, наиболее эффективная метаэвристика для маршрутизации транспортных средств.
SIMULATED_ANNEALING Использует имитацию отжига, чтобы избежать локальных минимумов (см. Имитация отжига ).
TABU_SEARCH Использует табу-поиск для обхода локальных минимумов (см. Табу-поиск ).
GENERIC_TABU_SEARCH Использует табу-поиск по целевому значению решения, чтобы избежать локальных минимумов.

Контроль распространения

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