Перейти к основному содержимому

Параметры поиска

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

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

Двухфазный поиск​

Поиск решения состоит из двух фаз:

  1. Построение первого допустимого решения — решатель применяет одну из стратегий первого решения, чтобы быстро получить решение, удовлетворяющее всем жёстким ограничениям (даже если оно далеко от оптимального).
  2. Локальный поиск улучшений — построенное решение последовательно улучшается метаэвристикой: решатель пробует локальные изменения (поменять местами два узла, переместить узел из одного маршрута в другой и т. п.) и принимает или отклоняет их по правилам выбранной метаэвристики.

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

Передача параметров поиска​

Параметры поиска модели маршрутизации передаются через поле ДополнительныеНастройки объекта НастройкиРешателя. Каждая настройка задаётся парой «имя поля → JSON-литерал значения»:

Настройки = О2.СоздатьНастройкиРешателя();
Настройки.ДополнительныеНастройки.Вставить(
    "firstSolutionStrategy",
    """PATH_CHEAPEST_ARC"""
);
Настройки.ДополнительныеНастройки.Вставить(
    "localSearchMetaheuristic",
    """GUIDED_LOCAL_SEARCH"""
);
Настройки.ДополнительныеНастройки.Вставить(
    "timeLimit",
    """10s"""
);

ПараметрыПоиска = О2.СоздатьПараметрыПоиска();
ПараметрыПоиска.НастройкиРешателя = Настройки;

Решение = Модель.Решить(ПараметрыПоиска);

Имя ключа — поле RoutingSearchParameters в формате lowerCamelCase (proto-имя, разбираемое через JsonParser.Default).

Значение — JSON-литерал:

  • строки передаются в двойных кавычках: """PATH_CHEAPEST_ARC""";
  • числа — без кавычек: "0.1";
  • длительности — в формате "Ns", где N — количество секунд: """10s""".

Полный перечень доступных полей и их допустимых значений — в документации: Routing Options (developers.google.com).

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

Задаются ключом firstSolutionStrategy. Ниже — наиболее употребимые значения:

ЗначениеКогда применять
AUTOMATICРешатель сам выбирает стратегию исходя из структуры задачи. По умолчанию.
PATH_CHEAPEST_ARCУниверсальная стратегия: на каждом шаге добавляется самая дешёвая из доступных дуг. Хорошо работает для большинства VRP.
SAVINGSМетод экономий Кларка-Райта. Классическая эвристика для VRP с одним депо.
SWEEPМетод подметания: клиенты группируются по угловой координате относительно депо.
CHRISTOFIDESАлгоритм Кристофидеса. Сильная стратегия для TSP с симметричной матрицей.
PARALLEL_CHEAPEST_INSERTIONПараллельная вставка по самой дешёвой стоимости. Подходит для VRP среднего размера.
LOCAL_CHEAPEST_INSERTIONПоследовательная вставка с локальным выбором. Часто даёт хорошее начальное решение для задач с временными окнами.

Метаэвристики локального поиска​

Задаются ключом localSearchMetaheuristic. Ниже — наиболее употребимые значения:

ЗначениеКогда применять
AUTOMATICРешатель сам выбирает метаэвристику. По умолчанию.
GREEDY_DESCENTЖадный спуск: принимаются только улучшения. Быстро сходится, но застревает в локальных минимумах.
GUIDED_LOCAL_SEARCHУправляемый локальный поиск: помогает выходить из локальных минимумов через штрафы за устойчивые признаки. Часто рекомендуется как первый вариант при тонкой настройке.
SIMULATED_ANNEALINGИмитация отжига: с убывающей вероятностью принимает ухудшающие изменения.
TABU_SEARCHТабу-поиск: запоминает недавно сделанные изменения и не повторяет их.

Лимит времени​

Общий лимит времени поиска задаётся через поле ЛимитВремени объекта НастройкиРешателя (в секундах):

Настройки = О2.СоздатьНастройкиРешателя();
Настройки.ЛимитВремени = 30;

Для ограничения только фазы локального поиска используйте ключ localSearchTimeLimit в ДополнительныеНастройки:

Настройки.ДополнительныеНастройки.Вставить("localSearchTimeLimit", """20s""");
Рекомендация

В большинстве случаев достаточно общего лимита через НастройкиРешателя.ЛимитВремени. Ограничение только фазы улучшения через ДополнительныеНастройки применяется в специальных случаях, когда нужно разделить бюджет между фазами.

Полный перечень параметров​

Полный набор полей RoutingSearchParameters — в официальной документации: Routing Options (developers.google.com).