Application of the simulated annealing algorithm to the combinatorial optimisation problem with permutation property: An investigation of generation mechanism

Application of the simulated annealing algorithm to the combinatorial optimisation problem with permutation property: An investigation of generation mechanism

0.00 Avg rating0 Votes
Article ID: iaor20003006
Country: Netherlands
Volume: 118
Issue: 1
Start Page Number: 81
End Page Number: 94
Publication Date: Oct 1999
Journal: European Journal of Operational Research
Authors: , ,
Keywords: combinatorial analysis
Abstract:

Focusing on the generation mechanism of random permutation solutions, this paper investigates the application of the Simulated Annealing (SA) algorithm to the combinatorial optimisation problems with permutation property. Six types of perturbation scheme for generating random permutation solutions are introduced. They are proved to satisfy the asymptotical convergence requirements. The results of experimental evaluations on Traveling Salesman Problem (TSP), Flow-shop Scheduling Problem (FSP), and Quadratic Assignment Problem (QAP) reveal that the efficiencies of the perturbation schemes are different in searching a solution space. By adopting a proper perturbation scheme, the SA algorithm has shown to produce very efficient solutions to different combinatorial optimisation problems with permutation property.

Reviews

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