The traveling salesman problem encompasses the problem of the existence of a Hamilton cycle in a graph. In a practical form, the problem is that of a traveling salesman who has to tour a certain number of cities, leaving from one of them, going exactly once through the others, to return at the end to the city from which he departed. This traveler wants to minimize the total distance covered.

 In graph terms, the problem is set in its most general form in the following manner.

       Let K_n be a complete graph, G =(X,E), weighted by the mapping v : E → R⁺ (real numbers ≥ 0). The question is to find a Hamilton cycle of G of which the total value, defined as the sum of the values by v of its edges and denoted by v(C), is as small as possible. In the case of “the traveling salesman”, the weighting v corresponds to the distances between the cities. Our frame here, in terms of graphs, is more general and v is random; in particular it does not verify the triangular inequality specific to distances. However, we will still consider this interesting particular caselater.

1.1 Complexity of the problem

As for any optimization problem, the goal here is to find an element which is an extremum following a certain measure, in a set which has in general so many elements that it is impossible in practice to consider them all. A search which would consider all cases is impracticable. For example, in a complete graph with n vertices there are(n−1)!/2 distinct Hamilton cycles.

It is easy to understand that as soon as integer n is large, considering all the cycles in order to find one that is less than or equal to all the others is not possible even using the most powerful machine. To define the difficulty of the traveling salesman problem, let us show how it contains the problem of the existence of a Hamilton cycle in a graph, a problem which we already mentioned as NP-complete.

Let H =(X,F) be a graph with n vertices. Let us associate with this graph the complete graph G =(X,E) with the same set of vertices and weighted by putting: v(xy)=1if xy ∈ F and v(xy)=2if xy ∈ E F.Itis easy to verify that a Hamilton cycle of H corresponds in G to a Hamilton cycle of total value n, and conversely. So the existence of a Hamilton cycle in H corresponds to the existence of a Hamilton cycle in G with a total value ≤ n (in fact equal to n). Thus, an algorithm which solves the traveling salesman problem in G also solves at one blow the problem of the Hamilton cycle in H. In what we just did, which is called the reduction of a problem to another (see Appendix B), we have used the decision problem associated with the traveling salesman problem, which can be put as follows (and which is, in fact, of an equivalent algorithmic difficulty): given a complete weighted graph G andaninteger k ,is therein G a Hamilton cycle with a total value ≤ k? This problem, which contains the problem of the existence of a Hamilton cycle, is therefore NP-complete.

1.2 Applications

We can wonder what the practical interest of the traveling salesman problem is. Indeed, there are probably very few traveling salesmen who organize their tours in such simple terms. They usually have a lot more constraints to take into account such as, for example, the need to be in a certain city on a certain date to meet someone. The constraint of the shortest distance covered is therefore not always the most pertinent in practice. However, we can cite real applications of the traveling salesman problem. The first one, which is quite obvious, concerns the programming of the articulate arm of a robot which needs to cover certain points of a sheet for welding. For speed, and possibly in order to economize and limit the wear out of machine tools, we might want to minimize the total distance covered by the extremity of the arm of this robot. Modeling this problem into a “traveling salesman problem” is direct.

The other application considered here is less direct. In a paint workshop, a number of blends have to be prepared each day. A mixer prepares the blends but going from one mixing to another requires adjusting the mixer depending on the blends to be made. We know the time necessary to adjust the machine to go from one mixing of a pair of colors to another. This time is assumed to be symmetric with regard to the order of the two blends. The problem is to define the order of passage of the blends in the mixer in order to minimize the total time spent in adjusting it. If we want to finish with the machine set for the first mixing, and if each mixing is only done once, the problem can once again be modeled as a traveling salesman problem by considering the graph of which the vertices are the blends to be prepared, each edge being weighted by the time necessary to go from one mixing to another. A Hamilton cycle with a minimal total value answers the question.

_______________________________________________________________________________

Graph Theory  and Applications ,Jean-Claude Fournier, WILEY, page(217-220)

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength