A heuristic method for the quadratic assignment problem

A heuristic method for the quadratic assignment problem

0.00 Avg rating0 Votes
Article ID: iaor20061018
Country: Germany
Volume: 11
Issue: 1
Start Page Number: 3
End Page Number: 16
Publication Date: Mar 2003
Journal: Central European Journal of Operations Research
Authors:
Keywords: heuristics, programming: assignment
Abstract:

In this paper a new evolutionary algorithm is described for the Quadratic Assignment Problem. This method can be divided into three stages: a preparatory and two local search stages. The first stage improves the quality of the initial population. The second stage improves the quality of the solutions with a local search procedure while periodically generating new solutions. In the third stage the algorithm continues the application of the local search procedure and replaces the weakest solutions with new ones. We tested our algorithm on all the benchmark problems of QAPLIB. The algorithm managed to find solutions which are either best-known or within 1% of the best known solutions for 98% of all tasks.

Reviews

Required fields are marked *. Your email address will not be published.