Travelling Salesman Problem — Dynamic Programming Approach

The Travelling Salesman Problem describes a salesman who must travel between N cities. The order in which he does is something he does not care about and as long as he visits each city during his trip, finishes where he was at first.

This problem can be solved using different methods like Dynamic Programming, Genetic Algorithm implementation, Ant Colony Optimization etc. But ultimately the algorithm has to return the minimum distance needed to cover all the cities and get back to the source city.

Photo by Emran Yousof on Unsplash

Dynamic Programming approach

Dynamic Programming is a method of solving problems that represent a specific structure where a problem can be broken down into subproblems which are again similar to the original problem. Hence we make use recursive function calling. However, it is not necessary to always use recursive methods for solving Dynamic Programing problems.

Let’s consider dummy cities like [1, 2, 3, 4] , we can have a distance or cost matrix that shows the distance or cost from each city to every other city. We can achieve this by assigning random values.

Random distance matrix

The diagonal values are 0 as the distance from the source to the source will always be 0. The below function sets the distance/cost matrix for the required number of cities that is passed as an argument.

def SetCostMatrix(num):
    cmatrix = {}
    for i in range(1, num + 1):
        for j in range(1, num + 1):
            if i == j:
                cmatrix[(i, j)] = 0
            else:
                cmatrix[(i, j)] = random.randint(10, 50)
    return cmatrix

For this problem, I have taken only 10 cities. The above function returns a dictionary having {(row, col) : distance} .

total_num = 10
num_cities = SetCostMatrix(total_num)

Now that we have a distance matrix, we should be able to retrieve the actual distance pertaining to the source and target . In order to do this, we need a helper function that actually check the dictionary keys and return the distance values.

def GetCostVal(row, col, source):
    if col == 0:
        col = source
        return num_cities[(row, col)]
    return num_cities[(row, col)]

It looks like everything is set. Trust me it’s not. The ultimate goal of this algorithm is to get the minimal distance by an iterative process. We need a recursive function in order to achieve the task.

iterative_process = []
def TSPGetMinDistance(main_source, source, cities):
    if len(cities) == 1:
        minDis = GetCostVal(source, cities[0], main_source) + GetCostVal(cities[0], 0, main_source)
        return minDis
    else:
        Dist = []
        for city in cities:
            dcities = cities[:]
            dcities.remove(city)
            Dist.append(GetCostVal(source, city, source) + TSPGetMinDistance(main_source, city, dcities))
        iterative_process.append(Dist)
        return min(Dist)

The above function when executed successfully returns the minimum distance that traveller finds to cover all the cities and finally reach the source. The list iterative_process shows the step by step result how the algorithm is performing. It shows the result starting from the second step as the result of the 1st step will be needed in the following steps. The last index (iterative_process[-1]) shows the total distances, but we want the minimal distance. Hence the Iterative Process.

>>> TSPGetMinDistance(1, 1, [2, 3, 4, 5, 6, 7, 8, 9, 10])
>>> iterative_process[-1]
[207, 176, 184, 188, 209, 195, 189, 186, 200]

If we visualize the above values, we see a decreasing order that clearly shows the performance of the algorithm.

import matplotlib.pyplot as plt
plt.figure(figsize=(12, 8))
final_costs = sorted(iterative_process[-1])
final_costs = final_costs[::-1]
plt.scatter(list(range(2, len(final_costs) + 2)), final_costs, color='red')
plt.plot(list(range(2, len(final_costs) + 2)), final_costs)
plt.show()

TSP algorithm performance

The result will be the same for the cities if changed the source city value. The minimum distance that is obtained is 176 for the source city 1 .

Challenges

The above is a recursive way of solving, as we increase the value of n , the function consumes much time and memory to solve the problem.

1. We can implement the same using Genetic Algorithm techniques which require very less computation to solve the same.
2. Ant Colony Optimization is another different perspective which is purely probabilistic in nature. This technique is based on how real ants able to find the shortest path to reach the destination.