Travelling Salesman

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?






Touch the canvas in order to add a point. You cannot add points when solution is being calculated.


Trivia

This problem is classified as NP-hard since it's time complexity is \( \mathcal{O} (n!) \) (Along with a space complexity of \( \mathcal{O} (n) \)). The only assured way of obtaining the shortest path is via brute-force search, which involves looking at all possible paths and keeping track of the shortest ones encountered. However, the number of possible paths grows factorially with number of nodes (which is asymptotically faster than even exponential growth). Hence, there are several ways through which we can get 'shorter' but not the 'shortest' path:

  1. Nearest Neighbour:
    Start at a particular node. Travel to the nearest node. Repeat. This algorithm is very simple to implement.
  2. Greedy Heuristic:
    Form the initial path with shorter edges, and connect them.
  3. Simulated Annealing:
    Inspired by the way crystals cool, this method tries to converge to a local minima while implementing a cooling schedule. In every step, two nodes from the path are switched, and the resulting path is accepted or rejected using Metropolis algorithm (please find intricate details here).
  4. Genetic Algorithm:
    A poplation of entities whose genes comprise of paths, and whose fitness is based on how short the paths are. Fitter entities have greater chance of their genes making it into the offspring. Also uses mutation (to explore prospectively better avenues) and recombination (to combine the best of two genes).
  5. Ant Colony Optimization:
    Initially, a population of ants randomly traverse the graph. By gauging the shortness of each edge, they leave more pheromones along that edge. In the next iteration, at every node, the ants choose the edge on a probabilistic manner, weighted by pheromone strength. Both, genetic algorithm and ant colony optimization are called metaheuristic methods because they solve the problem at hand by working at a higher level, instead of directly tackling the problem.
  6. Christofides' Algorithm
    Considered the gold standard of solving the Travelling Salesman Problem, this algorithm utilizes insights from an easily solvable problem in graph theory (constructing a minimal spanning tree from a given graph) and manipulates it to arrive at (on average) comparatively shorter paths.


Note:
  1. I will try to make simulations of the optimized algorithms above, if time permits.
  2. When there are 8+ points, then an initial lag is expected before the solving process starts
  3. With 10 points, an average time of 49 minutes was required to find the solution to the route
  4. Simulation may lag on lower-end computers and phones
  5. Related: Ant Colony Optimization

Developed by ChanRT | Fork me at GitHub