travelling salesman problem

(redirected from Salesman 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 ?
Travelling Salesman Problem is a well-known problem in computer science.
Abu Qudeiri [4] solved The Traveling Salesman Problem for two different arrival and departure points with constraints for tool collision.
Thomas, in his chapter on the development of "Theories of Decision, Allocation and Design" (chapter 20), discusses the Travelling Salesman Problem, and he devotes chapter 21 to Inventory Theory.
Enhanced Traveling Salesman Problem Solving by Genetic Algorithm Technique (TSPGA) [C].
A group of nine high school students participating in the Pennsylvania Governor's School for the Sciences (PGSS) at Carnegie Mellon University have tied eight world records for solving a version of the infamous Traveling Salesman Problem.
The final chapter states linear programming models for the set partitioning problem, the vertex coloring problem, and the multiple traveling salesman problem.
It is a restricted version of the multiple traveling salesman problem and the optimal solution for 2392 cities (destinations) served from a single deposit.
One of the most popular combinatorial optimization problems is the traveling salesman problem (TSP) [1].
A traveling salesman problem on path (TSPP for short) arises in dispatching an automated guided vehicle (AGV) to visit a set of locations along the wire which transmits signal to navigate the AGV.
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.
Indeed, it is related to travelling salesman problem with additional preference to the order of visited sites.
A very famous example solved using the GA is called a Travelling Salesman Problem "TSP".