Greedy Randomized Adaptive Search Procedures

Leonidas S. Pitsoulis and Mauricio G. C. Resende

ABSTRACT

GRASP (greedy randomized adaptive search procedure) is a metaheuristic for combinatorial optimization. GRASP is usually implemented as a multistart procedure, where each iteration is made up of a construction phase, where a randomized greedy solution is constructed, and a local search phase, which starts at the constructed solution and applies iterative improvement until a locally optimal solution is found. This article gives an overview of GRASP. Besides describing the basic building blocks of a GRASP, the article covers enhancements to the basic procedure, including reactive GRASP, hybrid GRASP, and intensification strategies.