What is traveling salesman problem (TSP)?

Example of a typical traveling salesman problem

A typical explanation of the is traveling salesman problem is, "A salesman needs to drive to N number of cities on the map then return home. He wants to spend as little money on gas as possible. Write a program to find the shortest route for him to take."

This is a deceptively simple problem. It is easy to write a program to try every possible path and return the shortest one. The difficulty is that as the number of points, N, goes up, the number of possible paths goes up as the factorial N! of points. Even a small number of points, like 10, would require checking 3.6 million possible paths.

This becomes difficult for a normal computer to calculate quickly, with larger problems becoming impossible for even supercomputers. Problems that increase in difficulty greater than exponentially with the number of items are known as NP-hard problems.

Solving the traveling salesman problem

Rather than focusing on finding the most optimal route, traveling salesman problem is often concerned with finding the fastest solution that gives good enough results. In traveling salesman problems, the large number of variables creates a challenge when finding the shortest route, which makes approximate, fast and cheap solutions more attractive.

Focused on optimization, the traveling salesman problem is often used in computer science to find the most efficient route for data to travel between various nodes. Applications include identifying network routing, optimizing hardware, pathing tools and sequencing DNA.

History of the traveling salesman problem

Irish mathematician W.R. Hamilton and British mathematician Thomas Kirkman first described the traveling salesman problem in the 1800s through the creation of a game named the Icosian Game. It was solvable by finding a Hamilton cycle, which is a non-overlapping path between all nodes.

TSP has been studied for decades and several solutions have been theorized. Many use heuristics, which provide probability outcomes. However, the results are approximate and not always optimal. Other solutions include branch and bound, Monte Carlo and Las Vegas algorithms. Using these methods, answers that are only a couple percent away from optimal even with millions of nodes can be found.

Traveling salesman problem: Humans vs. computers

The traveling salesman problem is also interesting because humans are good at solving it, while computers are not. Given the same set of about a hundred points, a person can find a solution in a couple of moments about as well as the best heuristic algorithm.

It is also expected that quantum computers will be able to offer solutions to optimization questions, such as the traveling salesman problem. Because they use qubits to arrive at an answer instead of computing each possibility, quantum computers could solve these types of problems much faster.

Supercomputers are becoming more prevalent as AI plays a bigger role in enterprise computing. Learn the top nine applications of AI in business and why businesses are using AI. Explore the future potential quantum computing uses.