Local optimization and the traveling salesman problem. (English) Zbl 0766.90079
Automata, languages and programming, Proc. 17th Int. Colloq., Warwick/GB 1990, Lect. Notes Comput. Sci. 443, 446-461 (1990).
Summary: [For the entire collection see Zbl 0758.00017.]
The Traveling Salesman Problem (TSP) is often cited as the prototypical “hard” combinatorial optimization problem. As such, it would seem to be an ideal candidate for nonstandard algorithmic approaches, such as simulated annealing, and, more recently, genetic algorithms. Both of these approaches can be viewed as variants on the traditional technique called local optimization. This paper surveys the state of the art with respect to the TSP, with emphasis on the performance of traditional local optimization algorithms and their new competitors, and on what insights complexity theory does, or does not, provide.
The Traveling Salesman Problem (TSP) is often cited as the prototypical “hard” combinatorial optimization problem. As such, it would seem to be an ideal candidate for nonstandard algorithmic approaches, such as simulated annealing, and, more recently, genetic algorithms. Both of these approaches can be viewed as variants on the traditional technique called local optimization. This paper surveys the state of the art with respect to the TSP, with emphasis on the performance of traditional local optimization algorithms and their new competitors, and on what insights complexity theory does, or does not, provide.
MSC:
| 90C35 | Programming involving graphs or networks |
| 90-02 | Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming |
| 90C60 | Abstract computational complexity for mathematical programming problems |
| 90C27 | Combinatorial optimization |
| 68T05 | Learning and adaptive systems in artificial intelligence |
