Travelling Salesman Problem - Comparison of solutions

It's Christmas Eve! And Father Christmas is running out of time! And he has so many ore homes to visit!

What's the best way to find the shortest tour visiting each home only once?

image.png

This notebook compares the solutions for travelling salesperson problem derived by using the following algorithms:

  1. Nearest neighbour algorithm using $|N|$ number of steps
  2. Nearest neighbour algorithm using $|N|^{2}$
  3. Nearest neighbour algorithm with 2-opt heuristic
  4. Miller, Tucker and Zemlin (MTZ) method
  5. Genetic algorithm

The comparison is shown here.

Map of 15 homes

We will first create a map of the 15 homes that all the five alogirthms can use as an input.
(The colors don't mean anything -- the multi-color plot is to make it more festive! )

Nearest Neighbour algorithm using $|N|$ steps

Nearest Neighbour algorithm using $|N|^{2}$ steps

This is the same with nearest neighbour algorithm with N steps but repeating the method for all nodes as starting node.

Nearest neighbour algorithm with 2-opt heuristic

Take the shortestroute calculated from nearest neighbour with $|N|^{2}$ steps

Miller, Tucker and Zemlin (MTZ) method

Genetic algorithm

Individual outputs

Comparison of solutions