travelling salesman problem


Also found in: Dictionary, Thesaurus, Wikipedia.

travelling salesman problem

(algorithm, complexity)
(TSP or "shortest path", US: "traveling") Given a set of towns and the distances between them, determine the shortest path starting from a given town, passing through all the other towns and returning to the first town.

This is a famous problem with a variety of solutions of varying complexity and efficiency. The simplest solution (the brute force approach) generates all possible routes and takes the shortest. This becomes impractical as the number of towns, N, increases since the number of possible routes is !(N-1). A more intelligent algorithm (similar to iterative deepening) considers the shortest path to each town which can be reached in one hop, then two hops, and so on until all towns have been visited. At each stage the algorithm maintains a "frontier" of reachable towns along with the shortest route to each. It then expands this frontier by one hop each time.

Pablo Moscato's TSP bibliography. Fractals and the TSP.
References in periodicals archive ?
The complexity of solving the travelling salesman problems is estimated by the number of tours and sub-tours that are required to be analysed before conclusively determining the optimal solution.
Travelling Salesman Problem. One of the best-known optimization problems is the Travelling Salesman Problem (TSP), which can be described as the problem of finding the tour between N cities (or jobs), which means that the tour needs to start and end in the same point and visit each point of the tour once, with the smallest possible distance (or makespan) [3].
Piwonska, "Genetic algorithm finds routes in travelling salesman problem with profits.
An example of an optimization problem commonly used in the literature is the travelling salesman problem (TSP) [5, 7, 9].
Ilic."A general variable neighborhood search for the one-commodity pickup and delivery travelling salesman problem".
Yang, "Solving large travelling salesman problems with small populations," in Proceedings of the 2nd International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications (GALESIA '97), pp.
Zamanifar, "Study of some recent crossovers effects on speed and accuracy of genetic algorithm, using symmetric travelling salesman problem," International Journal of Computer Applications, vol.
Table II: Computational results for the Travelling Salesman Problem with [alpha] = 0.01.
The problem area of the technical inspection and maintenance systems discussed here is closest to the multiple travelling salesman problems (MTSP).
"Genetic Algorithms for the Min-Max Travelling Salesman Problem".
A sampling of topics: diagnostics techniques of power transformer, a novel algorithm for union between complex polygons, image denoising using Countourlet transform, designing a framework for distributing serial applications, identification of nonlinear predictor and simulator models of a cement rotary kiln by locally linear neuro-fuzzy technique, GLS optimization algorithm for solving travelling salesman problem, and segmentation of touching hand written numerals and alphabets.