Opções de roteamento

Esta seção descreve algumas das opções para o solucionador de roteamento.

Limites de pesquisa

Os limites de pesquisa encerram o solucionador depois que ele atinge um limite especificado, como o tempo máximo ou o número de soluções encontradas. É possível definir um limite de pesquisa por meio dos parâmetros de pesquisa do solucionador. Consulte Limites de tempo para ver um exemplo.

A tabela a seguir descreve os limites de pesquisa mais comuns.

Nome	Tipo	Padrão	Descrição
solution_limit	int64	kint64max	Limite para o número de soluções geradas durante a pesquisa.
time_limit.seconds	int64	kint64max	Limite em segundos ao tempo gasto: na pesquisa.
lns_time_limit.seconds	int64	100	Limite em segundos ao tempo gasto em : a pesquisa de conclusão para cada vizinho.

Primeira estratégia da solução

A primeira estratégia é o método que o solucionador usa para encontrar uma solução inicial. A tabela a seguir lista as opções para first_solution_strategy.

Opção	Descrição
AUTOMATIC	Permite que o solucionador detecte qual estratégia usar de acordo com o modelo que está sendo resolvido.
PATH_CHEAPEST_ARC	A partir de um nó "start" da rota, conecte-o ao node que produz o segmento de trajeto mais barato e, em seguida, estenda a rota iterando no último node adicionado à rota.
PATH_MOST_CONSTRAINED_ARC	Semelhante a PATH_CHEAPEST_ARC, mas os arcos são avaliados com um seletor baseado em comparação, que favorecerá o arco mais restrito primeiro. Para atribuir um seletor ao modelo de roteamento, use o método ArcIsMoreConstrainedThanArc().
EVALUATOR_STRATEGY	Semelhante a PATH_CHEAPEST_ARC, exceto que os custos do arco são avaliados usando a função transmitida para SetFirstSolutionEvaluator().
SAVINGS	Algoritmo de poupança (Clarke e Wright). Referência: Clarke, G. & Wright, J.W. "Scheduling of Vehicles from a Central Depot to a a number of Delivery Points" (Pesquisa de operações de veículos de um depósito central para um número de pontos de entrega), Vol. 12, 1964, pp. 568-581.
SWEEP	Limpar algoritmo (Wren e Holliday). Referência a Anthony Wren e Alan Holliday Programação de veículos de um ou mais depósitos para vários pontos de entrega. Pesquisa trimestral trimestral (1970-1977), 23, no 3 (setembro de 1972), pág. 333-344.
CHRISTOFIDES	Na verdade, o algoritmo Christofides é uma variante do algoritmo Christopides que usa uma correspondência máxima em vez de uma correspondência máxima, o que não garante o fator 3/2 da aproximação em um vendedor de viagem métrica. Funciona em modelos genéricos de roteamento de veículos, estendendo uma rota até que nenhum nó possa ser inserido nela. Referência a Nicos Christofides, análise de pior cenário de uma nova heurística para o problema do caixeiro viajante, relatório 388, Pós-Graduação em Administração Industrial, CMU, 1976.
ALL_UNPERFORMED	Tornar todos os nós inativos. Só encontrará uma solução se os nós forem opcionais (são elementos de uma restrição de disjunção com um custo de penalidade finito).
BEST_INSERTION	Crie uma solução iterativamente inserindo o nó mais barato na posição mais barata. O custo da inserção é baseado na função de custo global do modelo de roteamento. Desde 2/2012, só funciona em modelos com nós opcionais (com custos de penalidade finitos).
PARALLEL_CHEAPEST_INSERTION	Crie uma solução iterativamente inserindo o nó mais barato na posição mais barata. O custo da inserção é baseado na função de custo do arco. É mais rápido que BEST_INSERTION.
LOCAL_CHEAPEST_INSERTION	Crie uma solução iterativamente inserindo cada nó na posição mais barata. O custo de inserção é baseado na função de custo do arco. É diferente de PARALLEL_CHEAPEST_INSERTION pelo nó selecionado para inserção. Aqui, os nós são considerados na ordem de criação. É mais rápido que PARALLEL_CHEAPEST_INSERTION.
GLOBAL_CHEAPEST_ARC	Conecte iterativamente dois nós que produzam o segmento de rota mais barato.
LOCAL_CHEAPEST_ARC	Selecione o primeiro nó com uma sucessora ilimitada e conecte-o ao nó que produz o segmento de rota mais barato.
FIRST_UNBOUND_MIN_VALUE	Selecione o primeiro nó com um sucessor ilimitado e conecte-o ao primeiro nó disponível. Isso é equivalente à estratégia CHOOSE_FIRST_UNBOUND combinada com ASSIGN_MIN_VALUE (cf.constraint_solver.h).

Status da pesquisa

Você pode retornar o status de uma pesquisa usando o método status do modelo de roteamento. Veja o código Python para imprimir o status de uma pesquisa:

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

Isso gera um número inteiro com os seguintes significados:

Valor	Descrição
0	ROUTING_NOT_SOLVED: o problema ainda não foi resolvido.
1	ROUTING_SUCCESS: problema resolvido com sucesso.
2	ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED: problema resolvido com sucesso depois de chamar RoutingModel.Solve(), exceto que um máximo local foi atingido. Deixar mais tempo permitiria melhorar a solução.
3	ROUTING_FAIL: nenhuma solução foi encontrada para o problema.
4	ROUTING_FAIL_TIMEOUT: o limite de tempo foi atingido antes de encontrar uma solução.
5	ROUTING_INVALID: modelo, parâmetros do modelo ou sinalizações não são válidos.
6	ROUTING_INFEASIBLE: problema comprovado como inviável.

Opções de pesquisa local

A tabela a seguir lista as opções de estratégias de pesquisa local (também chamadas de metaheurística). Consulte Como alterar a estratégia de pesquisa para ver exemplos de como configurar essas opções.

Opção	Descrição
AUTOMATIC	Permite que o solucionador selecione a metaheurística.
GREEDY_DESCENT	Aceita a melhoria da vizinhança (redução de custos) até que um mínimo local seja atingido.
GUIDED_LOCAL_SEARCH	Usa pesquisa local guiada para escapar do mínimo local. (cf. Pesquisa local guiada) em geral, essa é a metaheurística mais eficiente para roteamento de veículos.
SIMULATED_ANNEALING	Usa a simulação de escape para escapar do mínimo local (consulte Alocação simulada).
TABU_SEARCH	Usa a pesquisa Tabu para escapar do mínimo local (consulte Pesquisa Tabu).
GENERIC_TABU_SEARCH	Usa a pesquisa tabular do valor objetivo da solução para escapar do mínimo local.

Controle de propagação

Nome	Tipo	Padrão	Descrição
use_full_propagation	bool	true	Use restrições com propagação completa no modelo de roteamento (em vez de apenas propagação leve). A propagação completa só é necessária ao usar a pesquisa de profundidade ou para modelos que exigem uma forte propagação para finalizar o valor das variáveis secundárias. Alterar essa configuração para "true" atrasará a pesquisa na maioria dos casos e aumentará o consumo de memória em todos os casos.