Metaheuristic algorithms for combinatorial optimization problems (Review)

We survey metaheuristic algorithms that perform directed random searches of possible solutions of combinatorial optimization problems, optimal or near optimal, until a particular termination condition is met or after a predefined number of iterations. Metaheuristics combine basic heuristic methods in higher level frameworks aimed at efficiently and effectively exploring a search space. Metaheuristics fall in two categories: local search metaheuristics and evolutionary algorithms. In this paper, we describe the major solution methods: Local Search Metaheuristics (Simulated Annealing, Tabu Search, Greedy Randomized Adaptive Search Procedure (GRASP), Variable Neighborhood Search) and Evolutionary Algorithms (Genetic Algorithms, Ant Colonies Optimization).