travelling salesman problem

(redirected from Tsp problem)

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 ?
For example, in an instance of the TSP problem with 50 cities the Epoch Length should be 50.
Niu, "A discrete artificial bee colony algorithm for TSP problem," Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol.
In order to test the efficiency of proposed algorithm on large problem, a TSP problem with 100 cities was selected from benchmark problems [52] where its length of optimal tour is 2772.31.
Considering the batches of cut tobacco every day in actual production environment do not exceed 30, which is the TSP problem of small scale.
Algorithm 3: The pseudocode for applying the mutation operator for TSP problem. (1) begin (2) Step 1: For ant A, generating mutation position random as [k.sub.1]; (3) Step 2:; (4) if ([k.sub.1] = n) then (5) [k.sub.2] = 1 (6) else (7) [k.sub.2] = k + 1 (8) end (9) Step 3: Exchanging [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]; (10) Step 4: Getting new ant A'; (11) end Mutation Operator.
Lately, 2-dimensional TSP problem has been transferred to the 3rd dimension and studied in literature.
Some scholars argued that EMU circulation scheduling problem could be seen as the tsp problem with constraints [21-23].
In this study, we design a novel clustering algorithm named special local clustering algorithm (SLC), which is applied to classify and find the solution for TSP problem. Moreover, a colony of ants acts on each class to get a local TSP path.
If F (x) <F (x *), x * = x do k = k +1 end While The taboo search met heuristic to solve the TSP problem, generates an initial route (x0) that allows to collect the products ordered by customers along with the distance it takes, F (xo) and becomes the current solution x, which is becomes the best solution found so far x *
There are two cost matrixes between cities in each TSP problem. Usually the cost matrix is the distance matrix between cities.
The TSP problem is classified as an NP-complete problem [24].
Tao, "TSP Problem Solution Based on Improved Genetic Algorithm", 4th IEEE International Conference on Natural Computation, vol.