IMPROVING LOCAL SEARCH FOR THE TRAVELING SALESMAN PROBLEM

Abstract

The subject of this paper is the improving of local search for the traveling salesman problem (TSP). In particular, a so-called fast descent-random ascent (FDRA) strategy is proposed. The FDRA approach is based on the fast-modified 2-opt algorithm combined with certain perturbation (random ascent) procedures. The results obtained from the experiments demonstrate that the new improved local search strategy is better than the other local search algorithms. This approach may also be applied to other combinatorial optimization problems.