Simulated annealing with probabilistic neighborhood for traveling salesman problems

The traveling salesman problem (TSP) is a classical combinatorial optimization problem. Due to its NP-hard nature, modern heuristic methods are usually applied to find an approximation of the best tour of a TSP. It has been proved that most of the edges of a best tour are linked by neighbor cities. By using this heuristic information, a probabilistic neighborhood model is defined in this paper to guide the tour constructing in a heuristic method. This probabilistic neighborhood model is then applied in the framework of a simulated annealing (SA) algorithm. The proposed algorithm is compared to a basic SA algorithm on a set of test instances. The preliminary results show that an SA with probabilistic neighborhood can outperform a generic SA.