traveling salesman problem


Also found in: Acronyms.

traveling salesman problem

[¦trav·əl·iŋ ′sālz·mən ‚präb·ləm]
(mathematics)
The problem of performing successively a number of tasks, represented by vertices of a graph, with the least expenditure on transitions from one task to another, represented by edges of the graph with journey costs attached.

Traveling Salesman Problem

 

a well-known problem of finite mathematics. In the simplest case it is formulated in the following manner. Given n cities and the distance between each two cities, a traveling salesman starting from some city must visit the other n– 1 cities and return to the starting point. In what order should he visit the cities (once each) so that the total distance covered is minimum?

Problems of this type, associated with touring a number of points and returning to the starting point, include problems of delivering foodstuffs to stores, supplying electricity to consumers, and constructing circular power transmission lines, as well as various problems arising in the automation of wiring. One such problem, for example, is that of finding an optimal program of operation for an automatic milling machine to drill holes at given points in a radio-receiver panel, that is, of finding the order of proceeding through these points such that the length of the path of the drill head is minimal. Here, the beginning of the path need not coincide with its end, but mathematically this problem can be reduced to the simpler problem presented above. Methods of solving the traveling salesman problem essentially consist in scanning and evaluating all possible variants; no efficient algorithm is known.

REFERENCES

Mudrov, V. I. Zadacha o kommivoiazhere. Moscow, 1969.
Gol’shtein, E. G., and D. B. Iudin. Novye napravleniia v lineinom programmirovanii. Moscow, 1966.

V. P. KOZYREV

traveling salesman problem

(spelling)
References in periodicals archive ?
The proposal of mathematical formulation for the Single-Depot Multiple Traveling Salesman Problem (SD-MTSP) is based on applying the syntactic pattern used in the literature [16].
[3] introduce the Traveling Salesman Problem with Time-Dependent Service Times (TSP-TS) to model scenarios such as this.
Karel, "An algorithm for the traveling salesman problem," Operations Research, vol.
[9] Donald Davendra and Yuan-bin Mo "The Advantage of Intelligent Algorithms for TSP", Traveling Salesman Problem, Theory and Applications, Prof.
These problems are popularly known as Traveling Salesman Problem. The TSPs are classified into two groups by the cost matrix, symmetric and asymmetric.
Gunn, "A two-commodity network flow approach to the traveling salesman problem," vol.
Cocon et al., "Metaheuristics algorithms based on the grouping of animals by social behavior for the traveling salesman problem," International Journal of Combinatorial Optimization Problems and Informatics, vol.
A common approach is to transform the MTSP into an equivalent Traveling Salesman Problem, for which solutions can be found by exact methods (e.g., branch-and-bound algorithms and linear programming [26-28]) or approximate algorithms such as Genetic Algorithms, Simulated Annealing, and Ant System [29, 30].
The traveling salesman problem (TSP) is a classical optimization problem, whose idea is to find the shortest route between a set of given cities, starting and ending at the same city, such that each city is visited exactly once.
(1993) The Traveling Salesman Problem: A Neural Network Perspective.
It is a restricted version of the multiple traveling salesman problem and the optimal solution for 2392 cities (destinations) served from a single deposit.
The traveling salesman problem (SN Online: 2/20/12), which tries to determine the optimal route to visit a set of locations, is an NP-complete puzzle.