LNS: reorganizar parte da rede para escapar do ótimo local
Destruição, reparo com MILP, sementes e curvas de convergência em uma busca de vizinhança grande.
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
Por que mudar uma peça pode não bastar
Uma rede pode precisar mover várias regiões ao mesmo tempo para fechar uma instalação. Se apenas mudanças pequenas que melhoram imediatamente forem aceitas, essa economia fica fora de alcance. Large Neighborhood Search, ou LNS, libera um conjunto de atribuições, mantém o restante e resolve como reorganizar a parte liberada. A imagem útil é reformar um cômodo preservando o restante da casa: ganha-se liberdade local sem reconstruir o problema inteiro.
No projeto, a seleção alterna regiões com perfis de custo semelhantes e regiões associadas a centros abertos, respeitando o tamanho máximo da vizinhança. O reparo usa MILP e capacidade residual: a demanda congelada continua ocupando espaço. A nova solução só é aceita se melhorar estritamente o custo. Assim, o custo da melhor solução mantida não aumenta, embora algumas iterações não produzam melhoria.
Preparar uma execução observável
from alocacao_capacitada.analysis.study import tiny_instance
from alocacao_capacitada.solvers.greedy import NearestFeasibleGreedy
from alocacao_capacitada.solvers.lns import LnsSolver
from alocacao_capacitada.domain.evaluation import evaluate
inst = tiny_instance()
trace = []
solver = LnsSolver(NearestFeasibleGreedy(), seed=0, free_size=5,
sub_time_limit_s=1.0, max_iterations=10,
on_progress=lambda i,t,c: trace.append((i,t,c)))
result = solver.solve(inst, 5.0)
print(evaluate(inst, result.solution).total_cost)
print(trace)O exemplo libera até cinco regiões porque só existem cinco. Em problemas maiores, teste tamanhos pequenos e médios com o mesmo orçamento total, incluindo inicialização. Vizinhanças grandes permitem mudanças mais profundas, mas cada reparo consome mais tempo; vizinhanças pequenas permitem mais tentativas. A semente controla a seleção aleatória. Repita sementes e salve cada execução, não apenas a melhor.
O que uma curva permite concluir
Na trajetória, uma queda indica melhoria aceita e um patamar indica tentativas sem melhoria. Um patamar não prova optimalidade. Em 50×15, as três execuções salvas custaram 885420,59, 893046,17 e 903462,92, com gaps em relação ao LP de 1,57%, 2,41% e 3,53%. A variação importa: apresentar apenas a primeira esconderia a sensibilidade à semente. Três repetições descrevem esta amostra, mas não estabelecem uma distribuição universal de desempenho.
Embora o comentário inicial do módulo fale em resolver exatamente o subproblema, o código também aceita soluções viáveis no limite de tempo. A descrição precisa é reparo com MILP sob orçamento, sem garantia de ótimo em cada reparo. Também não há certificado global de optimalidade do LNS. Para analisá-lo, compare custo, atendimento, tempo real e limite inferior sobre a mesma instância; observe ainda quanto ele melhora depois dos primeiros segundos.
Fontes e evidências
Próximo: Prever demanda: de uma referência populacional a Poisson e boosting