Voraz y búsqueda local: construir rápido y mejorar con criterio
Cómo funcionan las decisiones inmediatas, los movimientos de vecindad y el óptimo local en la asignación capacitada.
Serie: de los datos a la decisión logística
- De los pedidos a la red logística: un proyecto de optimización y aprendizaje automático
- MILP: convertir una decisión logística en un modelo verificable
- Relajación lineal: cuánto puede mejorar una solución
- Voraz y búsqueda local: construir rápido y mejorar con criterio
- LNS: reorganizar parte de la red para escapar del óptimo local
- Predecir demanda: de una referencia poblacional a Poisson y boosting
- Previsión poblacional: tendencias, amortiguación y prueba temporal
- K-means: descubrir perfiles municipales sin inventar categorías naturales
- Scoring de candidatos: aprender a filtrar sin perder buenas decisiones
- Escenarios y SAA: decidir antes de conocer la demanda
La primera solución no necesita ser la última
El voraz del proyecto ordena las regiones por demanda decreciente y asigna cada una al centro de menor coste unitario que todavía tenga capacidad. Atender primero los bloques grandes intenta evitar que el espacio restante quede fragmentado. Es parecido a colocar primero las cajas grandes en estantes limitados; la comparación se refiere a capacidad, no a dimensiones físicas, que el modelo no representa.
Esta implementación no incluye el coste fijo de abrir un centro en la elección inmediata, ni compara económicamente servir con pagar la penalización. Por eso puede abrir instalaciones de más. Su utilidad es ofrecer rápidamente una solución inicial y una referencia comprensible. Pregunte si el coste de apertura domina al transporte: en ese caso, la regla del centro más barato por unidad puede ser especialmente miope.
Mejorar examinando alternativas cercanas
La búsqueda local toma esa solución y prueba realocar una región, intercambiar dos o cerrar un centro reasignando su demanda. Evalúa el cambio en el coste total y acepta mejoras que respetan capacidad. Una mudanza aislada puede ser imposible porque el destino está lleno, mientras que un intercambio libera simultáneamente el espacio necesario. Por eso ampliar el conjunto de movimientos cambia lo que el algoritmo consigue 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)Leer la descomposición del coste
En el ejemplo pequeño, el voraz cuesta 232: apertura 106 y transporte 126. La búsqueda local llega a 210: apertura 68 y transporte 142. Transportar cuesta más, pero cerrar una instalación compensa ese aumento. La solución óptima de 203 utiliza otra combinación, con apertura 73 y transporte 130. Mirar solo kilómetros o solo número de centros ocultaría esta compensación.
Óptimo local significa que no se encontró una mejora entre los movimientos examinados, una vez completada la búsqueda de esa vecindad. No demuestra que no exista otra red mejor. Si el algoritmo termina por tiempo, ni siquiera debe suponerse agotada la vecindad. Use estas heurísticas cuando necesita respuesta rápida o inicialización; compare varias instancias y conserve siempre el coste total, la demanda no atendida y el estado de terminación.
Un ejercicio para comprobar la intuición
Duplique únicamente los costes fijos del ejemplo y repita la comparación. Antes de ejecutar, escriba qué espera que ocurra con el número de centros. Después verifique si el transporte adicional compensa el cierre y si aparece demanda no atendida. La respuesta depende del conjunto completo de costes y capacidades; el ejercicio enseña por qué una regla intuitiva debe confrontarse con una evaluación independiente.
Fuentes y evidencias
Siguiente: LNS: reorganizar parte de la red para escapar del óptimo local