Acceleration of simulated annealing and its application for virtual path management in ATM networks

Simulated annealing (SA) is a very promising general purpose algorithm which can be conveniently utilized for various complicated combinatorial optimization problems. But its slowness has been pointed as a major drawback. In this paper, the authors propose an accelerated SA and test its performance experimentally by applying it for two standard combinatorial optimization problems (TSP (Travelling Salesman Problem) and GPP (Graph Partitioning Problem)) of various sizes. It turns out that performance of the proposed method is consistently better both in convergence speed and the quality of solution than the conventional SA or SE (Stochastic Evolution). In the second part of the paper the authors apply the accelerated SA to solve the virtual path management problem encountered in ATM networks. The problem is modeled as a combinatorial optimization problem to optimize the utility of links and an efficient SA implementation scheme is proposed. Two application examples are given to demonstrate the validity of the proposed algorithm. [In Korean.]