VNS

Búsqueda de Vecindarios Variables (VNS)

La Búsqueda de Vecindarios Variables (VNS) es una metaheurística poderosa introducida por Mladenović y Hansen (1997) para resolver problemas de optimización combinatoria y global. La idea principal es simple pero efectiva: cambiar sistemáticamente las estructuras de vecindario dentro de una búsqueda local para escapar de óptimos locales y explorar el espacio de búsqueda más completamente.

Idea Central de VNS

La Búsqueda Local tradicional usa un vecindario fijo y frecuentemente queda atrapada en un óptimo local. VNS aborda esto cambiando el vecindario dinámicamente durante el proceso de búsqueda.

VNS consiste de tres componentes principales:

Perturbación – Moverse aleatoriamente a una nueva solución en un vecindario diferente.
Búsqueda Local – Realizar búsqueda local desde la solución perturbada.
Cambio de Vecindario – Decidir si cambiar o expandir el vecindario.

Algoritmo VNS Básico

función VNS(S, k_max):
    repetir:
        k ← 1
        mientras k ≤ k_max:
            S' ← Perturbar(S, k)
            S'' ← BúsquedaLocal(S')
            si S'' es mejor que S:
                S ← S''
                k ← 1
            sino:
                k ← k + 1
    hasta que se cumpla criterio de parada
    retornar S

k es el índice del vecindario actual.
k_max es el número de diferentes estructuras de vecindario.
Perturbar(S, k) perturba la solución actual en el k-ésimo vecindario.
BúsquedaLocal(S') intenta mejorar la solución perturbada.

Estructuras de Vecindario

En VNS, se define un conjunto de estructuras de vecindario:

$$ \mathcal{N}1, \mathcal{N}2, …, \mathcal{N}{k{\max}} $$

Cada 𝒩_k(S) representa una forma diferente de modificar una solución S, frecuentemente con tamaño o complejidad creciente. Por ejemplo, en el Problema del Viajante de Comercio (TSP):

𝒩₁: Intercambiar dos ciudades (2-opt)
𝒩₂: Invertir un segmento (3-opt)
𝒩₃: Insertar una ciudad en una nueva posición

Esto permite al algoritmo escapar de óptimos locales haciendo cambios más grandes o fundamentalmente diferentes cuando sea necesario.

Variantes de VNS

VNS es altamente flexible, y se han propuesto varias variantes:

1. VNS Básico (BVNS)

Usa cambio sistemático de vecindarios sin memoria.
La Búsqueda Local se aplica después de cada perturbación.

2. VNS Reducido (RVNS)

No se realiza búsqueda local.
Solo se usa la fase de perturbación.
Mucho más rápido, útil para problemas de gran escala o tiempo real.

función RVNS(S, k_max):
    repetir:
        k ← 1
        mientras k ≤ k_max:
            S' ← Perturbar(S, k)
            si S' es mejor que S:
                S ← S'
                k ← 1
            sino:
                k ← k + 1
    hasta que se cumpla criterio de parada
    retornar S

3. VNS General (GVNS)

Combina RVNS y BVNS.
Usa RVNS como diversificación y BVNS para intensificación.

4. VNS Sesgado

Acepta soluciones peores si están suficientemente lejos de la actual.
Promueve diversificación.

si f(S') < f(S) o distancia(S, S') > umbral:
    S ← S'

5. Descenso de Vecindario Variable (VND)

Una versión determinística de VNS.
Aplica una secuencia de búsquedas locales en vecindarios crecientes.

función VND(S, k_max):
    k ← 1
    mientras k ≤ k_max:
        S' ← BúsquedaLocal_k(S)
        si S' es mejor que S:
            S ← S'
            k ← 1
        sino:
            k ← k + 1
    retornar S

Esquemas Estratégicos en VNS

VNS ofrece varias mejoras estratégicas:

1. Cambios de Vecindario Determinísticos vs. Probabilísticos

Usar aleatorización para seleccionar o cambiar vecindarios.
Ayuda a prevenir ciclado y promueve exploración.

2. Selección Adaptativa de Vecindario

Ajustar dinámicamente qué vecindarios explorar más basándose en rendimiento pasado.

3. Equilibrio entre Intensificación y Diversificación

Función de perturbación (exploración/diversificación)
Búsqueda Local (explotación/intensificación)

4. Hibridación

Combinar VNS con:
- GRASP
- Búsqueda Tabú
- Algoritmos Genéticos
Útil para problemas multiobjetivo o dinámicos.

Aplicaciones de VNS

VNS ha sido aplicado exitosamente a una amplia gama de problemas:

Problema del Viajante de Comercio (TSP)
Problemas de Enrutamiento de Vehículos (VRP)
Programación de Talleres
Problemas de Mochila
Diseño de Redes
Localización de Instalaciones
Clustering y Minería de Datos

Ventajas de VNS

Simple pero poderoso: El marco es fácil de entender e implementar.
Flexible: Estructuras de vecindario personalizables para cualquier problema.
Eficiente: Capaz de escapar óptimos locales rápidamente.
Escalable: Funciona bien en instancias de problemas grandes y complejos.

Referencias

Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers & Operations Research.
Hansen, P., Mladenović, N., & Pérez, J. A. M. (2010). Variable neighbourhood search: Methods and applications. Annals of Operations Research.
Hansen, P., & Mladenović, N. (2001). J-Measures and Variable Neighborhood Search. Journal of Heuristics.

Conclusión

La Búsqueda de Vecindarios Variables (VNS) es una metaheurística versátil que explora sistemáticamente el espacio de solución usando múltiples estructuras de vecindario. Su capacidad para equilibrar diversificación e intensificación, junto con su flexibilidad y simplicidad, la convierte en una herramienta esencial para resolver problemas de optimización difíciles.

Ya sea que esté resolviendo problemas de enrutamiento, programación o clustering, VNS ofrece una forma robusta y eficiente de alcanzar soluciones de alta calidad.

VNS