В этом разделе описываются некоторые параметры решателя маршрутизации.
Ограничения поиска
Ограничения поиска завершают работу решателя после того, как он достигает заданного предела, такого как максимальная продолжительность времени или количество найденных решений. Вы можете установить предел поиска через параметры поиска решателя. Пример см. в разделе Ограничения по времени .
В следующей таблице описаны наиболее распространенные ограничения поиска.
Имя | Тип | По умолчанию | Описание |
---|---|---|---|
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 в большинстве случаев замедлит поиск и во всех случаях увеличит потребление памяти. |