Exploring the Traveling Salesman Problem (TSP)

Graph theory seeks to address different situations or problems in a business application or organisational setups. TSP (Traveling Salesman Problem) is usually considered NP-hard (nondeterministic polynomial time) in solving decision problems. This is because there are more than one possible action or directions when deciding to traverse through every city or vertex in a given graph to return to the original. Taking some journey down the historical lane, the TSP problem was formulated in1800s by an Irish mathematician W.R Hamilton and his British counterpart Thomas Kirkman. 

Combinatorial Optimisation Problem

TSP belongs to a large class known as combinatorial optimisation problems. Combinatorial optimisation is aimed at discovering the best object (or city in a map situation) from a finite set of objects (or list of cities). The best solution or decision in selecting the route between objects or cities is believed to be discrete or at least reduced to discrete. Hence, the problem becomes NP-hard as the ultimate goal of most combinatorial optimisation problems seeks to find an efficient way of allocating resources such as time or money depending on the scenario. 

The difficulty of the Traveling Salesman problem in Artificial Intelligence

Solving TSP is considered to be computationally challenging even in modern times. It becomes quite challenging when a salesman desires to find the shortest route through several cities to safely return home. Regardless of the challenges, some algorithms and methods have been modified or designed to solve this problem. The popular Depth First Search (DFS) and Breadth-First Search (BFS) algorithms are two possible ways for tackling TSP. 

Common applications of the Travel Salesman Problems

1. Minimisation of travel cost: TSP can be useful in reducing the cost involved in travelling across several service stations. In this paper, TSP is utilised to ascertain the most optimal route for the service workers of ABC appliances limited. These service workers are expected to visit customers once a month to work on their air conditioners. Finding the best possible means of visiting all the locations of the customers to ensure the cost and distance between a pair of customer locations is taken into consideration. This will ensure the most efficient route is chosen considering the head office is the departure and arrival point. 

TSP as an optimisation method is believed to be relevant in applications such as logistics, planning and the manufacturing of microchips.

Code implementation of TSP

We will be using the air conditioning servicing example above in implementing TSP implementation in Python below. Let’s assume node 1 is the headquarters of ABC appliances limited and the service workers are scheduled to visit all the customers in locations 2, 3, 4 and 5 before returning to the origin. What is the most cost-effective route to take? We will ascertain this after the code implementation. 

Python implementation of the Travelling Salesman Problem (TSP)

The code implementation is inspired from this source.

from sys import maxsize
from itertools import permutations
V = 4
 
# executing the traveling Salesman Problem (TSP)
def travellingSalesmanProblem(graph, z):
 
    # all vertex are stored exclusing the source node
    vertex = []
    for i in range(V):
        if i != z:
            vertex.append(i)
 
 
    min_path = maxsize
    next_permutation=permutations(vertex)
    for i in next_permutation:
 
        # states the current Path weight(cost)
        current_pathweight = 0
 
        # execute the current path weight
        k = z
        for j in i:
            current_pathweight += graph[k][j]
            k = j
        current_pathweight += graph[k][z]
 
        # update minimum
        min_path = min(min_path, current_pathweight)
         
    return min_path
 
 
# the weight of the edges in a matrix
if __name__ == "__main__":
 
   
    graph = [[0, 12, 30, 14], [12, 0, 17, 25],
            [14, 25, 0, 11], [30, 17, 11, 0]]
    z = 0
    print(travellingSalesmanProblem(graph, z))

The TSP path weight is 62. It is the most cost efficient route for the after sales team.