Búsqueda Tabú

La búsqueda tabú es una metaheurística basada en memoria introducida por Glover (1986, 1989, 1990); una idea relacionada fue propuesta de forma independiente por Hansen (1986). Su rasgo distintivo es la memoria explícita: mientras el recocido simulado se apoya en azar y los algoritmos genéticos en una población, la búsqueda tabú mantiene una lista de los movimientos o atributos recientes y prohíbe revertirlos. Componentes clave: (1) estructura de vecindad y evaluación de movimientos; en cada iteración se va al mejor vecino no tabú aunque empeore el objetivo (escape del óptimo local); (2) memoria de corto plazo (lista tabú) de longitud k, denominada tenencia tabú; (3) criterio de aspiración — un movimiento tabú se permite si mejora la mejor solución conocida; (4) memoria intermedia para intensificación — profundizar la búsqueda alrededor de soluciones buenas visitadas con frecuencia; (5) memoria de largo plazo para diversificación — saltos a regiones inexploradas. Variantes incluyen búsqueda tabú granular, reactiva (Battiti y Tecchiolli 1994, con ajuste automático de tenencia) y Adaptive Memory Programming. Para VRP, scheduling, secuenciación y asignación es una de las metaheurísticas más fuertes; los trabajos VRP de Cordeau y Laporte son referencia industrial. Frente al recocido simulado es más determinista y consume más memoria, con calidad similar y menor sensibilidad a parámetros. Referencias: Glover y Laguna (1997), Gendreau y Potvin (2010).