Travelling Sales Person Model (TSP) (Analysis)

1
TRAVELLING SALES PERSON MODEL (TSP) (ANALYSIS
By
Name
Professor’s Name
Course Number
College/University Name
Street
Date

2
Travelling Sales Person Model (TSP)
Background Information
TSP model is a operations research analysis of determining the shortest routes a delivery sales
person can use to supply his/her commodities to the customers located at different locations with
interconnecting routes (Matai, Singh, & Mittal, 2010). By elimination, this model provides an
interconnected order of routes that the sales person uses so that the shortest and most economic
route is used from the distribution store, across to all customers and then back to the store.
The shortest route is the optimal solution for the distributor that will enable him/her to maximize
the output of goods delivered to customers while minimizing the cost of travelling to those
customers.
Typical Mathematical Model of TSP
The mathematical model of Traveling Salesperson Problem is represented by a list a points
possibly cities called nodes. These are the locations where the supplies are to be made to be
made. i and j notations are used to assign the departure and destinations for the given nodes
where i is the departure point at a given city and j is the destination point at the next city. In
addition, the distances or the time taken to travel from one point to another must also be known
for this model to work out.
To formulate a complete operations research model, we first need to identify three basic aspects
of the problem in question i.e. the objective function, the decision variable and the constraints of
the decision variables. For example; if we have 5 cities that a salesperson need to supply his
products from the warehouse (city 1), the aspects that must be considered to develop a model

3
that represents this problem mathematically and solve to provide an optimal solution i.e. the
shortest route that the salesperson need to travel in all the cities and back to the warehouse, are;-
1. The objective function is to minimize the distance a salesperson can travel for the
available 5 cities so that the cost of travel is not so much expensive. The start and end
point which is the warehouse is represented by City 1. The cities and their order of tour
are used to determine the routes and therefore are the decision variables.
2. The cities are the decision variables that need to be solved to give the minimal distance
3. The distances of between the cities have a finite value, non negative, not similar and are
all interconnected. These are the model constraints.
Application of Travelling Sales Person Model by Solving an Example
Consider the example of city networks in Table 1 below. Find the optimal routes that the
salesperson need to travel in order to deliver the commodities to all the cities and back to the
warehouse. The table represents the distances in kilometers from one city to the next where there
exists a route that can be followed.
Table 1: Distances between 8 cities
city 1 city 2 city 3 city 4 city 5 city 6 city 7 city 8
city 1 0 11 7 19 9 2 7 12
city 2 11 0 6 4 18 8 3 2
city 3 7 6 0 5 7 9 9 11
city 4 19 4 5 0 13 16 3 5
city 5 9 18 7 13 0 21 2 11
city 6 2 8 9 16 21 0 6 8