Abstract
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.
| Original language | English |
|---|---|
| Title of host publication | Meta-heuristics : theory and applications |
| Editors | I.H. Osman, J.P. Kelly |
| Publisher | Kluwer Academic Publishers |
| Pages | 605-618 |
| ISBN (Print) | 0-7923-9700-2 |
| Publication status | Published - 1996 |