Guloso e busca local: construir rápido e melhorar com critério
Como funcionam decisões imediatas, movimentos de vizinhança e o ótimo local na alocação capacitada.
Série: dos dados à decisão logística
- Dos pedidos à rede logística: um projeto de otimização e machine learning
- MILP: transformar uma decisão logística em um modelo verificável
- Relaxação linear: quanto uma solução ainda pode melhorar
- Guloso e busca local: construir rápido e melhorar com critério
- LNS: reorganizar parte da rede para escapar do ótimo local
- Prever demanda: de uma referência populacional a Poisson e boosting
- Previsão populacional: tendências, amortecimento e teste temporal
- K-means: descobrir perfis municipais sem inventar categorias naturais
- Scoring de candidatos: aprender a filtrar sem perder boas decisões
- Cenários e SAA: decidir antes de conhecer a demanda
A primeira solução não precisa ser a última
O guloso do projeto ordena as regiões por demanda decrescente e atribui cada uma ao centro de menor custo unitário que ainda tenha capacidade. Atender primeiro os blocos grandes tenta evitar que o espaço restante fique fragmentado. É parecido com colocar primeiro as caixas grandes em prateleiras limitadas; a comparação se refere à capacidade, não às dimensões físicas, que o modelo não representa.
Esta implementação não inclui o custo fixo de abrir um centro na escolha imediata, nem compara economicamente atender com pagar a penalidade. Por isso pode abrir instalações demais. Sua utilidade é fornecer rapidamente uma solução inicial e uma referência compreensível. Pergunte se o custo de abertura domina o transporte: nesse caso, a regra do centro mais barato por unidade pode ser especialmente limitada.
Melhorar examinando alternativas próximas
A busca local pega essa solução e testa realocar uma região, trocar duas ou fechar um centro redistribuindo sua demanda. Avalia a mudança no custo total e aceita melhorias que respeitam capacidade. Uma transferência isolada pode ser impossível porque o destino está cheio, enquanto uma troca libera simultaneamente o espaço necessário. Por isso ampliar o conjunto de movimentos muda o que o algoritmo consegue encontrar.
from alocacao_capacitada.analysis.study import tiny_instance
from alocacao_capacitada.solvers.greedy import NearestFeasibleGreedy
from alocacao_capacitada.solvers.local_search import LocalSearch
from alocacao_capacitada.domain.evaluation import evaluate
inst = tiny_instance()
for solver in [NearestFeasibleGreedy(),
LocalSearch(NearestFeasibleGreedy())]:
result = solver.solve(inst, 5.0)
ev = evaluate(inst, result.solution)
print(solver.name, ev.total_cost, ev.fixed_cost, ev.transport_cost)Ler a decomposição do custo
No exemplo pequeno, o guloso custa 232: abertura 106 e transporte 126. A busca local chega a 210: abertura 68 e transporte 142. Transportar custa mais, mas fechar uma instalação compensa esse aumento. A solução ótima de 203 usa outra combinação, com abertura 73 e transporte 130. Olhar apenas quilômetros ou apenas quantidade de centros esconderia essa compensação.
Ótimo local significa que não foi encontrada uma melhoria entre os movimentos examinados, depois de completar a busca daquela vizinhança. Não prova que inexista outra rede melhor. Se o algoritmo terminar por tempo, nem mesmo se deve presumir que a vizinhança foi esgotada. Use essas heurísticas quando precisa de resposta rápida ou inicialização; compare várias instâncias e preserve sempre o custo total, a demanda não atendida e o estado de término.
Um exercício para conferir a intuição
Duplique somente os custos fixos do exemplo e repita a comparação. Antes de executar, escreva o que espera que aconteça com o número de centros. Depois verifique se o transporte adicional compensa o fechamento e se aparece demanda não atendida. A resposta depende do conjunto completo de custos e capacidades; o exercício ensina por que uma regra intuitiva precisa ser confrontada com uma avaliação independente.
Fontes e evidências
Próximo: LNS: reorganizar parte da rede para escapar do ótimo local