GRASP with path-relinking for the quadratic assignment problem

C.A. Oliveira, P.M. Pardalos, and M. G. C. Resende

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 Page
Last modified: 16 March 2004

Copyright Notice