Contents of the page
- The TSP in everyday problems:
- The TSP as a reduction for other problems.
- The meta-graph.
- To go further.
On this page you will learn about the traveling salesman problem (TSP), which is probably one of the best-known problems in computer science. It’s also often used as the first example of an NP-complete problem, which means that we have not yet identified a fast‘ resolution algorithm.
Let’s begin with some basic definitions: given a set of cities and the cost of travel between each pair of cities, the traveling salesman problem, or TSP for short, is to find the cheapest way of visiting all of the cities and, optionally, returning to the starting point. Problems such as the TSP are called « optimization problems », because the goal is to find parameters that optimize a certain quantity, which in the TSP is to minimize the total cost.
The TSP can be represented by a weighted graph, where the vertices represent the cities, and the weights on the edges represent the travel cost between the pairs of cities. Solving the TSP comes down to finding a path passing once and only once through all vertices of the graph and which has a minimal total weight.
Let’s take an example. Consider the following graph, where the starting point is vertex . Let’s consider a situation where the salesman doesn’t have to return to the initial vertex.
Path has a total weight of . This path could potentially be a solution of the TSP. However, it’s not an optimal solution, as we can find a path with a smaller weight.
Path has a total weight of , and is the shortest path starting from and passing through all the vertices of the graph. So, this is the optimal solution of the TSP for this graph.
The TSP in everyday problems
The TSP is a recurrent problem found in many fields of computing. Here’s some examples :
Transportation and logistics
The TSP naturally arises as a subproblem in many transportation and logistics applications, such as, for example, planning school bus routes and picking up students from different locations. Other examples that can be modeled as TSPs include planning meal deliveries to people who are homebound and the routing of mail trucks for parcel collection.
Routing an artificial satelite
The TSP also arises when it comes to minimizing the time and expense of a potentially long and costly journey. This is the case, for example, for satellites that have to pass through a number of different locations to carry out their missions.
Length of an optical fiber network
The deployment of optical fiber raises the problem of serving a set of locations while limiting the construction work involved. Such a problem can usually be formalized as a TSP.
The scheduling of a machine to drill holes in an object in a manufacturing process can also be seen as a TSP. The holes to be drilled are the « cities », and the cost of travel is the time it takes to move the drill head from one hole to the next.
The TSP as a reduction for other problems
In computer science, a reduction is a method for transforming one problem into another problem, typically for which solutions are already known.
Intuitively, problem is reducible to problem if an algorithm for efficiently solving problem can also be used to solve problem . In a way, this means that when you solve problem , a part of what you’re doing can also be considered as solving problem .
More formally, reducing a problem to a problem is done by finding two polynomial algorithms and such that, if algorithm solves problem , then the concatenated algorithm solves problem .
To better understand reduction, think of language translation. Imagine you have a way to solve a problem in French, but your problem is expressed in English. A possible solution is to first translate your problem into French, solving it in French, then translating the solution back to English. This is an example of a reduction.
Reduction is a very convenient way to quickly obtain results. For example, reduction can be used to prove that a problem can be solved by a given algorithm, or to show that a problem is at least as difficult as another one. In other words, if is reducible to , then you can solve using an algorithm designed to solve . This doesn’t tell you anything about the ability to solve using an algorithm designed to solve , so we can only say that is at least as difficult as .
Let’s now see how picking up all the pieces of cheese in a maze is a reduction of the TSP. Let’s consider this maze, which also shows its associated graph. The pieces of cheese are represented by yellow vertices. Our starting position is shown in red.
It’s easy to see how determining the shortest path to collect all the pieces of cheese will somehow come down to solving a TSP. However, if we use this graph to solve the TSP, you can see that we will travel through many « parasitic » vertices, which don’t contain any cheese. We’d like to only go through vertices that contain a piece of cheese.
So, we propose to transform our graph to a new graph, which we call the meta-graph. The meta-graph’s vertices are the starting position plus the pieces of cheese. The weight between two vertices in the new graph corresponds to the length of a shortest path between corresponding vertices in the maze.
If we do this for any colored vertex pair in the previous example, we get a complete graph with seven vertices.
To decide how to move from one vertex to another, a routing algorithm has to be used.
Now we can solve the problem of finding the shortest route to grab all pieces of cheese. First we build the meta-graph. Then we solve the TSP on the meta-graph. Then we use routing to find the corresponding routes in the maze. We concatenated three algorithms, the first and the third one being polynomial, and proved that our problem is reducible to the TSP.