The Traveling Salesman Problem – The Greedy Approach

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 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s