The Traveling Salesman Problem (TSP) is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science.

**History**

TSP was defined in the 1800s by the Irish mathematician W. R. Hamilton and by the British mathematician Thomas Kirkman.

We can consider the TSP as a formulation in terms of graph theory for a complete weighted graph with objective to finding the Hamiltonian cycle with the least weight.

Hamilton had invented an interested mathematical game called Icosian Game with the objective being to find a Hamiltonian cycle along the edges of a dodecahedron such that every vertex is visited a single time, no edge is visited twice, and the ending point is the same as the starting point.

**Practical Usage**

The TSP has several applications in planning, logistics, manufacturing of microchips and some variants can be used as a sub-problem in rather complex things such as DNA sequencing.

– From the Wikipedia page

**Problem**

So our dear salesman is given a list of cities and their pairwise distances, he/she is required to follow these rules:

- The salesman must visit each place.
- The salesman cannot visit the same place twice.
- The salesman can start from any location.

Following are the assumption:

- Assume there are direct links from each place to every other place.
- Each connection between two places carry a weight or a cost.

**Objective**

Based on the above mentioned rules and assumptions, come up with the optimal solution such that the overall cost for the traveling is minimum.

**Solution**

There are various approaches to solving this problem using varying heuristics. Below is an implementation that uses Nearest Neighbor as a heuristic for solving this problem. Please note that this is a greedy algorithm and through experiments, it has been estimated that this algorithm yields paths 25% longer than the shortest path possible.

Below is a code written in C# for the algorithm that uses Parallel.For to run the algorithm in parallel. The data structure DistanceMatrix expects a csv file with comma separated distances for each city/location. Each city should have distances on a separate row. Essentially, it expects a square matrix and ignore values on the main diagonal.

```
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace TSP
{
class Algorithms
{
public static string[] GreedySearch(DistanceMatrix distances)
{
string[] returnValue = new string[distances.LocationNames.Length];
string[] shortestPath = new string[distances.LocationNames.Length];
int[] shortestPathCost = new int[distances.LocationNames.Length];
for (int i = 0; i < shortestPathCost.Length; i++)
{
shortestPathCost[i] = 0;
}
// For each location find the shortest possible route
Parallel.For(0, distances.LocationNames.Length, delegate(int i)
{
GreedySearchParallelComputePath(distances, i, ref shortestPath[i], ref shortestPathCost[i]);
});
// Find the path with minimum cost
int shortestPathByCost = Min(shortestPathCost);
for (int i = 0; i < shortestPath.Length; i++)
{
returnValue[i] = shortestPath[i] + ", Cost: " + shortestPathCost[i].ToString();
}
return returnValue;
}
private static void GreedySearchParallelComputePath(DistanceMatrix distances, int row, ref string shortestPath, ref int shortestPathCost)
{
// Initialize loop variables
List locationsExplored = new List();
shortestPath = distances.LocationNames[row];
shortestPathCost = 0;
// Add current location to explored path
locationsExplored.Add(row);
// While we haven't explored each location
while (locationsExplored.Count < distances.LocationNames.Length)
{
int minDistance = -1;
int nextLocation = -1;
for (int j = 0; j < distances.LocationNames.Length; j++)
{
// See if this is a new location
if (locationsExplored.IndexOf(j) < 0)
{
if ((minDistance < 0) || (minDistance > distances[locationsExplored[locationsExplored.Count - 1], j]))
{
minDistance = distances[locationsExplored[locationsExplored.Count - 1], j];
nextLocation = j;
}
}
}
shortestPathCost += minDistance;
shortestPath += " -> " + distances.LocationNames[nextLocation];
locationsExplored.Add(nextLocation);
}
}
private static int Min(int[] arr)
{
int min = 0;
for (int i = 1; i < arr.Length; i++)
{
if (arr[min] > arr[i])
{
min = i;
}
}
return min;
}
}
// The data structure to store distances
public class DistanceMatrix
{
#region Private Fields
private readonly int LOCATION_COUNT;
private int[,] data;
private List locationNames;
#endregion
#region Constructors
public DistanceMatrix(int numberOfLocations)
{
// Direct Input
LOCATION_COUNT = (numberOfLocations > 0 ? numberOfLocations : 1);
Initialize();
}
public DistanceMatrix(string filePath)
{
int currentRow = 0;
// Loads from File
using (StreamReader readFile = new StreamReader(filePath))
{
string line;
string[] row;
while ((line = readFile.ReadLine()) != null)
{
row = line.Split(',');
if (currentRow == 0)
{
LOCATION_COUNT = row.Length;
Initialize();
}
for (int i = 0; i < LOCATION_COUNT; i++)
{
this[currentRow, i] = int.Parse(row[i]);
}
currentRow++;
}
}
}
#endregion
#region Private Helper Methods
private void Initialize()
{
locationNames = new List();
data = new int[LOCATION_COUNT, LOCATION_COUNT];
for (int i = 0; i < LOCATION_COUNT; i++)
{
locationNames.Add("L" + i.ToString());
}
}
#endregion
#region Public Indexers
public int this[int row, int col]
{
get
{
if ((row >= LOCATION_COUNT) || (col >= LOCATION_COUNT))
{
throw new IndexOutOfRangeException();
}
return data[row, col];
}
set
{
if ((row >= LOCATION_COUNT) || (col >= LOCATION_COUNT))
{
throw new IndexOutOfRangeException();
}
data[row, col] = value;
}
}
public int this[string from, string to]
{
get
{
int row = locationNames.IndexOf(from);
int col = locationNames.IndexOf(to);
return this[row, col];
}
set
{
int row = locationNames.IndexOf(from);
int col = locationNames.IndexOf(to);
this[row, col] = value;
}
}
public int[] this[int row]
{
get
{
if (row >= LOCATION_COUNT)
{
throw new IndexOutOfRangeException();
}
int[] returnValue = new int[LOCATION_COUNT];
for (int i = 0; i < LOCATION_COUNT; i++)
{
returnValue[i] = data[row, i];
}
return returnValue;
}
set
{
if (row >= LOCATION_COUNT)
{
throw new IndexOutOfRangeException();
}
if (value.Length > LOCATION_COUNT)
{
throw new IndexOutOfRangeException();
}
for (int i = 0; i < LOCATION_COUNT; i++)
{
data[row, i] = value[i];
}
}
}
public int[] this[string location]
{
get
{
int row = locationNames.IndexOf(location);
return this[row];
}
set
{
int row = locationNames.IndexOf(location);
this[row] = value;
}
}
#endregion
#region Public Properties
public string[] LocationNames
{
get
{
return locationNames.ToArray();
}
}
#endregion
}
}
```

Please note that this could further be optimized by first creating data partitions and then running the algorithm in parallel on each data partitions.

However, xkcd has a better solution 🙂