To appear in Proceedings of the III Workshop on Efficient and Experimental Algorithms (WEA2004), LNCS, 2004
ABSTRACT
This paper describes a GRASP with path-relinking
heuristic for the quadratic assignment problem. GRASP is a multi-start
procedure, where different points in the search space are probed with
local search for high-quality solutions. Each iteration of GRASP
consists of the construction of a randomized greedy solution, followed
by local search, starting from the constructed solution.
Path-relinking is an approach to integrate intensification and
diversification in search. It consists in exploring trajectories
that connect high-quality solutions. The trajectory is generated
by introducing in the initial solution, attributes of the guiding
solution. Experimental results illustrate the effectiveness of
GRASP with path-relinking over pure GRASP on the quadratic assignment
problem.
PDF file of full paper
DjVu file of full paper
Mauricio G.C. Resende's Home PageLast modified: 16 March 2004