We present a theoretical average-case analysis of a 2-opt algorithm for the traveling salesman problem. First, we give a model which allows us to compute the required number of steps and the distribution of final solutions found by a best improvement algorithm. This model is empirically validated for a restricted version of the 2-opt neighborhood. Secondly, we present a semi-empirical analysis of the average-case performance of an iterated 2-opt and Lin-Kernighan algorithm based on empirically obtained parameters.
|Title of host publication||Meta-heuristics : theory and applications|
|Editors||I.H. Osman, J.P. Kelly|
|Publisher||Kluwer Academic Publishers|
|Publication status||Published - 1996|