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

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

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

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

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

Имя Тип По умолчанию Описание
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 (см. ограничение_solver.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 в большинстве случаев замедлит поиск и во всех случаях увеличит потребление памяти.