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 ?
These problems are popularly known as Traveling Salesman Problem.
In this paper, a new hybridized metaheuristic algorithm, called annealing elitist ant system with mutation operator for traveling salesman problem, has been introduced.
Ricciardelli, "Dynamic programming strategies for the traveling salesman problem with time window and precedence constraints," Operations Research, vol.
Zemlin, "Integer programming formulation of traveling salesman problems," J.
A multiple traveling salesman problem model for hot rolling scheduling in Shangai Baoshan Iron & Steel Complex".
This paper has proposed an integrated intelligent approach for solving a multi-objective traveling salesman problem (MOTSP).
The traveling salesman problem (TSP) is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science [5].
There are many problems for which no polynomial-time algorithm is known, this paper will consider three of them; Traveling Salesman Problem (TSP), 0/1 Knapsack problem, and Shubert function.
The first application of an ACO was done using the traveling salesman problem as a test problem.
Thus, cutting plane algorithms for the traveling salesman problem must solve a large number of edge connectivity problems reported that the solution of edge connectivity problems was the computational bottleneck in their state-of-the-art cutting-plane based algorithm.
Based on converting this idea to a search mechanism, ant colony system can be applied for solving some combinatorial optimization problems such as the job-shop scheduling problem (JSP), quadratic assignment problem (QAP) and traveling salesman problem (TSP) [4]etc.