Traveling Salesman Problem Solution Is A Vivid Example Of Optimization Activity

Foreword

Optimization problems… More and more often we hear this phrase. Day by day we use optimization, making various decisions not only in business, but also in everyday life. Our goal in this case is to make the only correct derivation among a certain number of other alternative variants.

Like any problem, an optimization problem must meet certain criteria. First, there must be alternative options to solve it and there must be more than two of them. Secondly, a criterion must be defined according to which one of the solutions will be considered the best. Thirdly, certain conditions for choosing a solution must be established in the problem.

All of these criteria are fully consistent with the classical “Traveling salesman problem” (TSP). The task is ancient, but its solution is completely match for modern requirements regarding the choice of the best option from many ones in various areas of human activity, including in the field of route planning for a wide variety of movements. The relevance of the traveling salesman problem solution is confirmed by the demand for the service.

The essence of the traveling salesman problem

So, the TSP condition is as follows: there is a certain number of settlements. Between each pair of them, there is at least one road. Our responsible salesman (SM) must leave his city, visit each settlement to sell goods, and return home again. All the way he must realize in the shortest possible time. That is, in fact, the task of optimization is set before the SM.

A brief statement of the problem`s input will look like this. We know the number of the settlements, the distance between each pair of the settlements, the number of the city from which the SM came out. Let’s remember the criteria that any optimization problem must meet. Obviously, the best solution for TSP is to choose the shortest path, since the shortest path means the shortest time to overcome it, and hence the lowest costs.

What are the conditions for choosing a solution to the problem? The first condition is that the SM must visit each settlement no more than once. The second condition concerns the beginning and end of the journey – it must be the city of SM. And the last condition is that the CV must visit all settlements.

Naturally, if the TSP condition includes a small number of settlements and there are no any additional conditions, then a simple iteration of all alternative known options can find the most optimal solution to this problem. Such a solution will be called a “local optimum”.

But after all, there can be much more TSP solutions, and a simple enumeration of known options is hardly enough here. The highest aerobatics in solving TSP is the choice of the most optimal variant among all, not only known, but also potential alternative options. This solution is called the “global optimum”.

TSP solution in the modern world

What practical applications follow from TSP today? First of all, this is the area of ​​logistics, where the optimization of the transport translocations is one of the highest priority tasks. The TSP solution is also relevant for companies that install computer or telephone networks not centrally, but in separate buildings and are interested in reducing cable consumption.

Also, the use of the TSP solution algorithm helps with the laying of various gas and pipelines. This is only a small list of aspects of human activity where the TSP solution can be applied.

What are the methods for solving TSP now? We have already mentioned the simple iteration method. This method is called the “exact method”. The exact methods also include the branch and bound method and some others. However, with a large amount of data in the TSP, the use of exact methods will not only be time-consuming, but unacceptably time-consuming.

Therefore, instead of exact methods, the so-called “approximate methods” are most often used. These methods make it possible to find a global optimum, the value of which is not exact, but as close as possible to its true value. Despite the fact that the values obtained is not exact approximate methods are successfully applied because of the short time to find necessary solutions.

Approximate methods, as a solvers of TSP, exist in several variants. One of the best options for solving TSP, which is gaining more and more popularity, is the use of services that work with such instrument as API. The API interface itself has already become an indispensable assistant to any IT user in solving various problems, and in combination with such a tool as the distance matrix, its capabilities increase many times over.

In a word, the distance matrix api service can be successfully applied to solve any optimization problem, including solving TSP.

Gretchen is a homemaker by day and writer by night. She takes a keen interest in life as it unfolds around her and spends her free time observing people go about their everyday affairs.