Traveling Salesman Problem

The traveling salesman problem is one of the difficult algorithms and it is because there is no clear solution that exists, and many experts and researchers have given their solution but no one has been able to provide the best algorithm ever. 

Traveling salesman is a classic combinatorial optimization problem.  This problem is used to find the shortest that the salesman can take to travel the list of many cities and after that, the traversal is over he has to return to his origin city from where he started. The information or the metrics that are given to us can vary, it can be the distance between each pair of the city or the time duration that it may take to traverse the city.

Traveling Salesman Problem finds a great deal of usefulness in the real-life and especially in business where the logistics and the planning has a very high value. We can take the example of a tour manager he is assigned with the responsibility of scheduling the performances of the band. In that case he has to determine how he can make the tour that reduces the cost that is spent in traveling and it can be done by choosing the shortest path possible.

And the specialty about this problem is it is an NP-hard problem or in simpler words is that you cannot guarantee the solution of the problem in the limited time possible. And this is not common to the Traveling salesman problem, most of the real-world optimization problem that we have the chance to have an algorithm is always a sub-optimum solution or they are not perfect but can get the work done for the time and there is a  higher chance that in future with the help of research and development we may find out the exact solution of it and then it can be called as the optimum solution to the problem.

There are various approaches to the traveling salesman problem 

Dynamic programming method

One way of solving the problem can be dynamic programming. The dynamic programming guarantees to find the best solution to the Traveling salesman problem, but the time complexity of the dynamic programming will increase exponentially when the number of cities is increased in the graph. Let’s take an example of the time complexity if we applied the Traveling Salesman Problem on 10 cities it can be solved by the DP in just 0.3 seconds with the help of intel core i5 computer, and when we increase the number of the cities say up to 15 cities than the problem-solving time will increase up to 60 times greater and will take up to 17 seconds and that time will keep on increasing exponentially with even smaller increment in the number of the cities. So a small suggestion that DP may give up the best solution but it is much time consuming and requires good computational power and this cannot be afforded in real life.

Simulated annealing method

Simulated Annealing is another way of solving the Traveling Salesman Problem, it is a heuristic algorithm that is derived from the functioning of the annealing mechanism that is widely used in the metallurgical industry. Annealing is a way of controlling cooling the metal in such a way that we can get the desired state of the metal, but how it relates to the way we have to solve our problem.  The lesson that is applied to the annealing mechanism is to enforce more control over the search process. The major rules that the SA method has to follow are

We have to determine each search step in such a way that the solution should be focusing on the global optimum rather than the local optimum.

The size of the search step should be reduced as we move towards the final result.

This method is very sensitive to the parameters that have been passed to the search steps and how the moving direction of the search process is formulated. Therefore the outcome can be easily influenced greatly if the parameter is not provided accurately, which is one of the drawbacks of the simulated annealing method as of its parameter sensitivity and the stopping criteria. The simulated annealing is a very powerful method but if you want for it to work with the help of this method you must make sure that you are aware of its flaws.

2-opt method

The 2-opt method is one of the best methods that can solve the traveling salesman problem in the given constraint of time. This algorithm uses the local search algorithm and has a special swapping mechanism. The major concept behind the 2-opt method is to remove the path crossing in each neighborhood of cities. This helps in the execution of the algorithm for example the traveling salesman problem with 120 cities within 5 to 6 seconds. And the solution to the problem is sub-optimum. The 2-opt method is much faster and much deterministic to the simulated annealing method.

The 2-opt method may trap the algorithm into the local parameter since they have not a definitive method to come out of the local optimums. Excluding this flaw, the method can work very well in solving the Traveling Salesman Problem since the algorithm is heuristic and is effective in solving such a problem. The final input of this heuristic search algorithm may influence the outcome of the problem, so we have to extra on reducing the sensitivity on the initial points.

7 thoughts on “Traveling Salesman Problem”

Leave a Comment