Exploring the Traveling Salesman Problem (TSP)

Graph theory seeks to address different situations or problems in 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 with the goal or returning to the original. Taking some journey down the historical lane, the TSP problem was formulated in1800s by an Irish mathematician W.R Hamiltion 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 a number of cities with an aim of safely returning back home. Regardless of the challenges, there are algorithms and methods that 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 micro chips.

Code implementation of TSP

We will be using the air conditioning servicing example above in implementing TSP implemnetattion 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.