Thomas A. Feo and Mauricio G.C. Resende
Journal of Global Optimization, vol. 6, pp. 109-133, 1995
ABSTRACT
Today, a variety of heuristic approaches are
available
to the operations research practitioner. One methodology that has
a strong intuitive appeal, a prominent empirical track record, and is
trivial to efficiently implement on parallel processors is GRASP
(Greedy
Randomized Adaptive Search Procedures). GRASP is an iterative
randomized sampling technique in which each iteration provides a
solution to the problem at hand. The incumbent solution over all
GRASP iterations is kept as the final result. There are two
phases
within each GRASP iteration: the first intelligently constructs
an
initial solution via an adaptive randomized greedy function; the second
applies a local search procedure to the constructed solution in hope of
finding an improvement.
In this paper, we define the various components comprising a GRASP and
demonstrate, step by step, how to develop such heuristics for
combinatorial optimization problems. Intuitive justifications for
the observed empirical behavior of the methodology are discussed.
The paper concludes with a brief literature review of GRASP
implementations and mentions two industrial applications.
PDF file of full paper
Go back
Mauricio G.C. Resende's Home PageLast modified: 23 May 2005