The traveling salesman problem – 02/13/2024 – Marcelo Viana

José is a traveling salesman: he travels from the factory to customer stores, to deliver merchandise and receive new orders, and returns to the factory at the end. And he would like to know what is the shortest route he can take passing through all the stores.

Similar questions arise in many areas, from logistics to chip design. Therefore, the “travelling salesman problem” – given a finite set of points whose distances are known, finding the shortest route that connects all the points and returns to the starting point – is one of the most important in the area of ​​computer science applications. mathematics.

The first known mention of this issue was in an instruction manual for traveling salesmen dated 1832. But its mathematical study only began a century later, becoming very popular in the 1950s, with the advent of the computer.

When the number N of points (“cities”) is small, the problem can be solved using brute force, listing all possible routes to check which is the shortest. But this soon becomes unfeasible as N increases, even with powerful computers, because the number of possible routes is given by the factorial N! = 1 x 2 x … x N, which grows very quickly.

Perhaps the reader is thinking that there is a simple strategy: start with the store closest to the factory, then visit the store closest to that, and so on, always choosing the closest store that has not yet been visited. But no, in general this “natural” strategy does not give the shortest route!

More sophisticated methods have been developed over the years. In 1954, researchers GB Dantzig, R. Fulkerson and SM Johnson expressed the question in the language of linear programming, that is, in the form of a set of linear equations. Linear programming is one of the most developed and powerful areas of numerical analysis: in this language, a computer can methodically analyze different combinations to find the best solution to the problem.

The method of Dantzig, Fulkerson and Johnson was improved and, also taking advantage of more powerful computers, today it already solves problems with 1 million cities or more. But, in all known methods, the time to obtain the solution of the traveling salesman problem increases at least exponentially with N. This is much better than the factorial N!, but it is still too much for certain applications. In fact, we know that, in a precise computational sense, this problem is among the hardest there are.

LINK PRESENT: Did you like this text? Subscribers can access five free accesses from any link per day. Just click the blue F below.