Probabilistic analysis of 2-opt for travelling salesman problems
Masahiro Okada, Kouichi Taji, Masao Fukushima · International Journal of Systems Science · 1998
In this paper, we propose a probabilistic model of 2-opt heuristics and study its behaviour. 2-opt is one of the most popular heuristic methods for symmetric travelling salesman problems, and has been used as the basis of various meta-heuristics such as simulated annealing and tabu search. But until now, few theoretical results have been obtained with regard to the performance of 2-opt. At each iteration of 2-opt, the lengths of two pairs of edges, one from the current tour and the other from outside the tour, are evaluated, and the shorter one is used to construct an improved tour. In this paper, we consider the lengths of these pairs to be random variables, and derive recurrence formulae for the distribution functions of these random variables. We show that the distribution functions generated by the recurrence formulae converge to certain distribution functions, from which we can estimate the length of local optima obtained by 2-opt. Moreover, the generated distribution functions can be used to evaluate the tour length and the probability of edge exchange at each iteration. The reported computational experience shows that the proposed model enables us to estimate the average performance and the dynamic behaviour of 2-opt.