The Travelling Salesman Problem

Travelling Salesman Problem (TSP) is a very common problem used everyday in our life. The problem is basically travelling to all the vertices at once starting from a single source, and return back to the source using the shortest possible routes. For real life example, let an Amazon delivery man wants to deliver 3 parcels to 3 different locations 1, 2 and 3 from the location 0. He can choose to deliver at location 1 first then 2 and then 3. Or, he may choose first 3, then 1 and then 2. Or, He can choose other paths as well. However, he have to measure the shortest paths in which he can save time and the cost of travelling. But how can he find that path? That’s all about this TSP.

Though this problem is usually known as Travelling salesman problem, the real life uses of this problem is too vast. Picking up students for school, connecting nodes of a particullar network for data transmission and deciding the flow of the transmission, using robots and automation to do the all the tasks with efficiency, choosing the best possible Nucleic Acid Base for DNA sequencing are some of the many real world problems. All these problems need one thing to be implemented, efficiency.

Here’s the catch, the solution is not so easier as the problem is. Finding the efficient way gets harder as the node increases. The number of possible solution is (n-1)!/2 using combinatorics. The possibility increases exponentially. So, manual brute force or dynamic approach to find all the possible cases and selecting the best solution is not feasible enough even for the fastest computer available. For this reason, researchers haven’t been able to find any polynomial time solution till now that can give the exact only one result for this NP-hard problem. So, they rely on the approximation algorithms to select one of the best possible scenario from a large number of permutations but not the exact single solution.

Some Approaches to solve TSP:

1. Brute Force Approach: Figuring out all the possible cases and selecting the lowest cost path with O(n!) time complexity. Only feasible for small datasets.

2. Greedy Approach: Selecting the node with lowest possible edge cost among all the connected nodes of the source. But skip that node if it forms a cycle or already visited. Repeat this process until all nodes are visited and returns back to the origin. Doesn’t give the optimal solution always.

3. Dynamic Programming Approach: Instead of calculating the total problem, it divides the problem into sub-problems. Calculate in the base levels and store that to reuse later which takes a time complexity of O(n² x 2^n).

4. Genetic Algorithm: Based on the biological processes of choosing, such as natural selection, mutation, crossing-over etc. It is one of the approximation algorithms to give a near-optimal solution.

5. Ant Colony Optimization: Ant’s searching for food and processing the path is used in this algorithm for finding a near-optimal solution.

6. Machine Learning speed up vehicle routing: Uses machine learning to approximate solution.

Solving TSP using Dynamic Programming Approach:

Here, the general formulation is g(i, s) = min{c(i, k) + g(k, s - {k})} where i is the currently source node, s is the set of visitable nodes, c(i, k) is the cost to go from i to k node.

For this case, we need to find the g(0, {1, 2, 3}).

Steps:

1. Let source is 0. The next option to visit can be 1, 2 or 3. g(0, {1, 2, 3})

2. a. If first visit is 1, then the 2nd visit can be 2 or 3. g(1, {2, 3})

   i) if 2nd visit is 2, then 3rd visit must be 3 then 3 to 0. So, total cost is 20.

   ii) if 2nd visit is 3, then 3rd visit must be 2. Lastly, cost of 2 to 0. So, total cost is 17.

   So, if 1 is selected first, then the minimum cost is 17.

   b. If first visit is 2, then the 2nd visit can be 1 or 3. g(2, {1, 3})

   i) If 2nd visit is 1, then 3rd visit must be 3 then 3 to 0. So, total cost is 15.

   ii) If 2nd visit is 3, then 3rd visit must be 1, then 1 to 0. So, total cost is 17. So, If 1st visit is 2, then minimum cost is 15.

   c. If first visit is 3, then the 2nd visit can be 1 or 2. g(3, {1, 2})

   i) If 2nd visit is 1, then 3rd visit must be 2, then 0. So, total cost is 15.

   ii) If 2nd visit is 2, then 3rd visit must be 1, then 0. So, total cost is 20.

   So, if 1st visit is 3, then minimum cost is 15.

3. Finally, the minimum cost is 15. So, there are 2 solutions for this minimum cost. The path is 0-> 2-> 1-> 3-> 0. Or another path is 0-> 3-> 1-> 2-> 0. These 2 solution is basically refers to the same path using forward and backward travelling.