THRESHOLD ACCEPTING - A GENERAL-PURPOSE OPTIMIZATION ALGORITHM APPEARING SUPERIOR TO SIMULATED ANNEALING

A new general purpose algorithm for the solution of combinatorial optimization problems is presented. The new threshold accepting method is even simpler structured than the wellknown simulated annealing approach. The power of the new algorithm is demonstrated by computational results concerning the traveling salesman problem and the problem of the construction of error-correcting codes. Moreover, deterministic (!) versions of the new heuristic turn out to perform nearly equally well, consuming only a fraction of the computing time of the stochastic versions. As an example, the deterministic threshold accepting method yields very-near-to-optimum tours for the famous 442-cities traveling salesman problem of Grötschel within 1 to 2 s of CPU time. © 1990.