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.

This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)

References in periodicals archive ?

For example, in an instance of the TSP problem with 50 cities the Epoch Length should be 50.

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.

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].