Contents of the page


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.

Example

Let’s take an example. Consider the following graph, where the starting point is vertex v_1. Let’s consider a situation where the salesman doesn’t have to return to the initial vertex.

tsp-example


Path \{v_1,v_4\}, \{v_3,v_4\}, \{v_2,v_3\} has a total weight of 3 + 1 + 8 = 12. 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 \{v_1,v_3\}, \{v_3,v_4\}, \{v_2,v_4\}  has a total weight of 4 + 1 + 2 = 7, and is the shortest path starting from v_1 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.

Drilling holes

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 p is reducible to problem q if an algorithm for efficiently solving problem q can also be used to solve problem p. In a way, this means that when you solve problem q, a part of what you’re doing can also be considered as solving problem p.

More formally, reducing a problem p to a problem q is done by finding two polynomial algorithms \mbox{alg}_1 and \mbox{alg}_2 such that, if algorithm \mbox{alg}_q solves problem q, then the concatenated algorithm [\mbox{alg}_1, \mbox{alg}_q, \mbox{alg}_2] solves problem p.

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 p is reducible to q, then you can solve p using an algorithm designed to solve q. This doesn’t tell you anything about the ability to solve q using an algorithm designed to solve p, so we can only say that q is at least as difficult as p.

The meta-graph

mazegraph
mazegraph

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.



To go further


Quiz

In graph theory, the TSP corresponds to...
Reducing a problem p to a problem q involves...
The TSP processes an input that is best described as...