Background

The problem selected for this report is the Travelling Salesperson Problem (TSP). This report will be based on the standard TSP model.

TSP is a well-known problem in the business world today with many logistics firms using the TSP model to solve various routing and distribution problems. TSP is commonly described as a scenario where a salesperson is required to visit each of his customers based in different cities in his region before returning back to his starting location. The salesperson would like to find the most optimal route that ensures that all customers based in the different cities are visited once(Rasmussen 2011).

The optimal routes can be based on factors such as distance, time, and costs. Different software can be used to solve the TSP models. In this report, the standard TSP model solved using Excel Solver’s “Simplex LP” method will be analyzed.

Model

TSP’s mathematical model is as follows,

Decision variable

Decision variable = X_ij

Where,

“i” represents the current node (salesperson’s current location)

“j” represents the subsequent node (salesperson’s next location from “i”)

X_ij = 1 if node “j” is visited immediately after node “i”

X_ij = 0 if otherwise

Objective function

n       n

min ∑∑C_ijX_ij

i=1  j≠i, j=1

Where,

C_ijrepresents the distance between nodes “i” and “j”

“n” represents the number of locations (nodes) visited

Constraints

n        n

Origin:             ∑∑(X_ijfrom origin node to subsequent nodes) = 1

i=1  j≠i, j=1

n        n

Destination:     ∑∑(X_ij from previous nodes to destination node) = 1

i=1  j≠i, j=1

n

Go-to constraint:   For “i” = 0, 1, …, n – 1,           ∑X_ij = 1

j

n

Come-from constraint:    For “j” = 0, 1, …, n – 1,           ∑X_ij =

Salesperson departure location:         The location the salesperson visited previously, must be the same location where the salesperson is departing from the subsequent node

Non-negativity:   All values ≥ 0

Binary constraint:    X_ij∈ {0,1}