Opções de roteamento

Nesta seção, descrevemos 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. Você pode definir uma pesquisa usando os parâmetros de pesquisa do solucionador. Consulte Limites de tempo, por exemplo.

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

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

Estratégia da primeira solução

A primeira estratégia de solução é o método que o solucionador usa para encontrar uma solução. A tabela abaixo 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 a que o modelo está sendo resolvido.
PATH_CHEAPEST_ARC	Começar no "início" de uma rota nó, conectá-lo ao que produz o trecho de trajeto mais barato e, em seguida, estende o trajeto pela iterando no último nó adicionado à rota.
PATH_MOST_CONSTRAINED_ARC	Semelhante a PATH_CHEAPEST_ARC, mas os arcos são avaliado com um seletor baseado em comparação que favorecerá a primeiro arco restrito. Para atribuir um seletor ao modelo de roteamento, use o método ArcIsMoreConstrainedThanArc().
EVALUATOR_STRATEGY	Semelhante a PATH_CHEAPEST_ARC, exceto pelo custo da arco são avaliadas usando a função passada para SetFirstSolutionEvaluator().
SAVINGS	Algoritmo de economia (Clarke e Wright). Referência Clarke, G. & Wright, J.W. “Agendamento de veículos de uma estação central para vários pontos de entrega” , Pesquisa de Operações, Vol. 12, 1964, pág. 568-581.
SWEEP	Algoritmo de limpeza (Wren e Holliday). Referências Anthony Wren e Alan Holliday: programação de veículos de Um ou mais depósitos para um número de pontos de entrega operacional Research Quarterly (1970-1977), Vol. 23, no 3 (set., 1972), pp. 333-344.
CHRISTOFIDES	Algoritmo de Christofides (na verdade, uma variante do Algoritmo de Christofides usando uma correspondência máxima em vez da máxima correspondência, o que não garante o fator 3/2 da aproximação em um vendedor de viagens por 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 de Nicos Christofides, análise do pior caso de uma nova heurística para o problema do vendedor viajante, Report 388, Graduate School of Industrial Administração, CMU, 1976.
ALL_UNPERFORMED	Tornar todos os nós inativos. Só encontra uma solução se os nós são opcionais (elementos de uma restrição de disjunção com um custo de penalidade finito).
BEST_INSERTION	Crie iterativamente uma solução inserindo as o nó mais barato na posição mais barata. o custo da inserção é baseado no tamanho função de custo do modelo de roteamento. A partir de 2/2012, funciona apenas em modelos com nós opcionais (com custos de penalidade finitos).
PARALLEL_CHEAPEST_INSERTION	Crie iterativamente uma solução inserindo o nó mais barato na posição mais barata; o custo da inserção se baseia a função de custo do arco. É mais rápido que BEST_INSERTION.
LOCAL_CHEAPEST_INSERTION	Crie iterativamente uma solução inserindo cada o nó mais barato na posição mais barata. o custo da inserção é baseado no arco função de custo. Difere de PARALLEL_CHEAPEST_INSERTION pelo nó selecionados para inserção aqui os nós são considerados na ordem criação. É mais rápido que PARALLEL_CHEAPEST_INSERTION.
GLOBAL_CHEAPEST_ARC	Conecta iterativamente dois nós que produzem a no trecho de trajeto mais barato.
LOCAL_CHEAPEST_ARC	Selecione o primeiro nó com um sucessor ilimitado e e conectá-lo ao nó que produz o segmento do trajeto mais barato.
FIRST_UNBOUND_MIN_VALUE	Selecionar o primeiro nó com um sucessor não vinculado e conectá-lo ao primeiro nó disponível. Isso equivale à Estratégia CHOOSE_FIRST_UNBOUND combinada com ASSIGN_MIN_VALUE (cf. restrição_solver.h).

Status da pesquisa

Para retornar o status de uma pesquisa, use o método status do modelo de roteamento. Este é o código Python para exibir o status de uma pesquisa:

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

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

Valor	Descrição
0	ROUTING_NOT_SOLVED: problema ainda não resolvido.
1	ROUTING_SUCCESS: problema resolvido.
2	ROUTING_PARTIAL_SUCCESS_LOCAL_OPTIMUM_NOT_REACHED: problema resolvido após chamar RoutingModel.Solve(), exceto pelo fato de que um o ideal não foi atingido. Deixando mais tempo permitiria melhorar a solução.
3	ROUTING_FAIL: nenhuma solução foi encontrada para o problema.
4	ROUTING_FAIL_TIMEOUT: limite de tempo 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 comprovadamente inviável.

Opções de pesquisa local

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

Opção	Descrição
AUTOMATIC	Permite que o solucionador selecione a metaheurística.
GREEDY_DESCENT	Aceita melhorar (reduzir o custo) vizinhos de pesquisa local até que um mínimo seja atingido.
GUIDED_LOCAL_SEARCH	Usa a pesquisa local guiada para escapar dos mínimos locais. (cf. pesquisa local guiada) essa é geralmente a metaheurística mais eficiente para o roteamento de veículos.
SIMULATED_ANNEALING	Usa a animação simulada para escapar dos mínimos locais (cf. recondicionamento simulado).
TABU_SEARCH	Usa a pesquisa tabu para escapar dos mínimos locais (cf. Tabu Search (em inglês).
GENERIC_TABU_SEARCH	Usa a pesquisa tabu no valor objetivo da solução para escapar do local mínimos.

Controle de propagação

Nome	Tipo	Padrão	Descrição
use_full_propagation	bool	verdadeiro	Usar restrições com propagação completa no modelo de roteamento (em vez de somente propagação da luz). Cheia a propagação é necessária apenas ao usar a pesquisa em profundidade ou para modelos que exigem uma propagação forte para finalizar o valor do papel variáveis. Alterar essa configuração para "true" torna a pesquisa mais lenta no na maioria dos casos e aumentar o consumo de memória em todos os casos.