GRASP: Greedy Randomized Adaptive Search Procedures

GRASP, or greedy randomized adaptive search procedure, is a multi-start metaheuristic that repeatedly applies local search starting from solutions constructed by a randomized greedy algorithm. In this chapter we review the basic building blocks of GRASP. We cover solution construction schemes, local search methods, and the use of path-relinking as a memory mechanism in GRASP. Combinatorial optimization can be defined by a finite ground set E ={1,...,n}, a set of feasible solutions F 2E, and an objective function f : 2E! R, all three defined for each specific problem. In this chapter, we consider the minimization version of the problem, where we seek an optimal solution S∗ 2 F such that f(S∗) f(S), 8S 2 F. Combinatorial optimization finds applications in many settings, including routing, scheduling, inventory and production planning, and facility location. While much progress has been made in finding provably optimal solutions to com- binatorial optimization problems employing techniques such as branch and bound, cutting planes, and dynamic programming, as well as provably near-optimal solu- tions using approximation algorithms, many combinatorial optimization problems arising in practice benefit from heuristic methods that quickly produce good-quality solutions. Many modern heuristics for combinatorial optimization are based on guidelines provided by metaheuristics. Among these, we find genetic algorithms, simulated annealing, tabu search, variable neighborhood search, scatter search, path-relinking, iterated local search, ant colony optimization, swarm optimization, and greedy randomized adaptive search procedures (GRASP). In this chapter, we review the basic building blocks of GRASP, including so- lution construction schemes, local search methods, and use of path-relinking as a memory mechanism in GRASP. The chapter is organized as follows. In Section 1, we introduce a basic local search scheme. In Section 2 we examine the relationship between the metaheuristic GRASP and local search. Section 3 covers construction schemes while In Section 4, we introduce a memory mechanism in GRASP through path-relinking. Concluding remarks are made in Section 5. 1. Local search Local search is a fundamental operator in GRASP heuristics. It is fully specified by a feasible starting solution s02 F, an objective function f(·), for which we seek