Metaheuristic

A metaheuristic is an umbrella term for strategic higher-level algorithmic frameworks designed to explore the search space beyond local optima. The term was coined by Glover (1986) in the context of tabu search and standardized in the OR literature in the 1990s. Principal metaheuristic families include: (1) tabu search (Glover 1989) — forbids recent local-search moves via a tabu list to prevent cycling; (2) simulated annealing (Kirkpatrick, Gelatt and Vecchi 1983) — physics-inspired temperature parameter that probabilistically accepts worsening moves; (3) genetic algorithm (Holland 1975) — evolutionary search with population, selection, crossover, and mutation; (4) variable neighborhood search (Mladenović and Hansen 1997) — systematic transitions across multiple neighborhood structures; (5) GRASP (Feo and Resende 1995) — randomized-greedy construction plus local search; (6) ant colony optimization (Dorigo 1992) and particle swarm optimization (Kennedy and Eberhart 1995). Hybrid metaheuristics (matheuristics) have risen in the last twenty years, using a MIP solver as a subproblem solver inside a metaheuristic loop. Parameter tuning (tabu list length, cooling schedule, population size, mutation rate) largely determines the quality-time trade-off. Standard references are Glover and Kochenberger (2003), Talbi (2009), and Gendreau and Potvin (2010) Handbook of Metaheuristics.