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. |