Traveling Salesman Problem

Dynamic programming

• The traveling salesman problem(TSP) is an algorithmic problem tasked with finding the shortest route between a set of points and locations that must be visited.
• Dynamic programming(DP) is the most powerful technique to solve a particular class of problems.DP is an algorithmic technique for solving an optimization problem by breaking it down into simpler sub-problems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its sub-problems.
• In this problem, we approach the Bottom-Up method.

Problem Statement

A traveler needs to visit all the cities from a list, where distances between all the cities are known and each city should be visited just once. What is the shortest possible route that he visits each city exactly once and returns to the origin city?

Solution

• Let us consider a graph G = (V, E), where V is a set of cities and E is a set of weighted edges. An edge e(u, v) represents that vertices u and v are connected. Distance between vertex u and v is d(u, v), which should be non-negative.
• We have started in the city i and need to visit all the S cities once and returns to the same starting city i.So, we need to know which is the shortest path to visit all the city.
• Suppose we have started in city 1 and after visiting some cities now we are in the city k.since this will determine which cities are most convenient to visit next. We also need to know all the cities visited so far, so that we don’t repeat any of them.
• Let us define a term g(i, S) be the cost of the minimum cost path visiting each city in set S exactly once, starting at 1 and ending at i.
• We start with all subsets of size 2 and calculate g(i, S) for all subsets where S is the subset, then we calculate g(i, S) for all subsets S of size 3 and so on. Note that 1 must be present in every subset.

We need to start at 1 and end at k. We should select the next city in such a way that

g{i,S} = min{Cik + g{k,S-{k}}} where k Є S

i is a Starting point of a tour and S a subset of cities. Using this formula we are going to solve a problem. let see how to slove.

Example

Distance Matrix

Solution

g(2, Φ ) = C21
= 5
g(3, Φ ) = C31
= 6
g(4, Φ ) = C41
= 8

K = 1 , consider set of one element :

Set {2}:

g(3,{2}) = c32 + g(2, Φ )
= c32 + c21
= 13 + 5
= 18
g(4,{2}) = c42 + g(2, Φ )
= c42 + c21
= 8+ 5
= 13

Set {3} :

g(2,{3}) = c23 + g(3, Φ )
= c23 + c31
= 9 + 6
= 15
g(4,{3}) = c43 + g(3, Φ )
= c43 + c31
= 9+ 6
= 15

Set {4} :

g(2,{4}) = c24 + g(4, Φ )
= c24 + c41
= 10 + 8
= 18
g(3,{4}) = c34 + g(4, Φ )
= c34 + c41
= 12 + 8
= 20

K = 2 , consider set of two element :

Set {3,4} :

g {2,{3,4}} = min {c23 + g(3,{4}) , c24 + g(4,{3})}
= min { 9 + 20 , 10 + 15}
= min { 29, 25}
= 25

Set {2,4} :

g {3,{2,4}} = min {c32 + g(2,{4}), c34 + g(4,{2})}
= min { 13+ 18, 12 + 13}
= min { 31, 25}
= 25

Set {2,3} :

g(4,{2,3}) = min {c42 + g(2,{3}), c43 + g(3,{2})}
= min { 8 + 15 , 9 + 18}
= min { 23, 27}
= 23

Length of an optimal tour,

g { 1, {2,3,4}} = min{ c12 + g(2,{3,4}), c13 + g(3,{2,4}), c14 + g(4,{2,3})}
= min { (25 + 10 ) , (25 + 15) , (23 + 20) }
= min { ( 35), (40), (43)}
= 35

The minimum cost path is 35.

The optimal tour route is, 1 -> 2 -> 4 -> 3 -> 1 .

Now, it’s time to calculate your own optimal route.

Kishore Premkumar - iOS Developer Intern - Ivy Mobility | LinkedIn