Simulated annealing for the quadratic assignment problem: A further study

Concentrating on the generating mode of random permutation solutions and the corresponding theory and evaluation problems, this paper carries out a further study on the Simulated Annealing (SA) algorithm for the Quadratic Assignment Problem (QAP) which has many applications in practice. The paper introduces and analyzes the six different kinds of interchanges of facility locations for generating random permutations. The theoretical analyses prove that the relevant generation probabilities satisfy the asymptotical convergence conditions. The results of experimental evaluations reveal the relations between the random sampling modes, and show that adopting the proper generating mode the SA algorithm can produce better quality solutions of the QAP. At the same time, the conclusions reached in the paper are available for many extensive heuristics to solve combinatorial optimization problems.