Never one to give up easily, Santa decided to roll up his sleeves and put together an algorithm that could find a rough plan for the journey without waiting so long
What do you think about the results?
This notebook provides a simple implementation of the Nearest Neighbour Heuristic. The algorithm is performs much faster than our implementation of the MTZ model. The solution provided is a valid one, since it does not contain any subtours, and respects all the constraints of our TSP model.
However, as a greedy heuristic, the results leave much to be desired... Scroll down and you will see what we mean!
import numpy as np
import matplotlib
import matplotlib.pyplot as plt
from matplotlib import collections
import seaborn as sns; sns.set()
from sklearn.datasets import make_blobs
import pandas as pd
%matplotlib inline
plot_size = 16
plot_width = 10
plot_height = 5
params = {'legend.fontsize': 'large',
'figure.figsize': (plot_width,plot_height),
'axes.labelsize': plot_size,
'axes.titlesize': plot_size,
'xtick.labelsize': plot_size*0.75,
'ytick.labelsize': plot_size*0.75,
'axes.titlepad': 25}
plt.rcParams.update(params)
plt.rcParams.update(params)
num_cities = 14
cities_names = [f'Node {i}' for i in range(num_cities)]
center_box = (100, 200)
cities_coord, _ = make_blobs(n_samples=num_cities,
centers=1,
cluster_std=20,
center_box=center_box,
random_state = 10)
cities_coord_dict = {name: coord for name,coord in zip(cities_names, cities_coord)}
cities_coord[:, 0]
plt.scatter(cities_coord[:, 0],
cities_coord[:, 1],
s=plot_size*2,
cmap='viridis');
for i in range(num_cities):
plt.annotate(i+1, (cities_coord[i, 0]+1, cities_coord[i, 1]+0.5))
start_node = cities_names[6]
start_node
'Node 6'
from scipy.spatial import distance
dist_matrix = distance.cdist(cities_coord, cities_coord, 'euclidean')
dist_matrix = np.where(dist_matrix==0, np.Inf, dist_matrix)
dist_matrix.shape
(14, 14)
df = pd.DataFrame(dist_matrix, index=cities_names, columns=cities_names)
df.to_csv('nearest_neighbour.csv', index=False)
df
Node 0 | Node 1 | Node 2 | Node 3 | Node 4 | Node 5 | Node 6 | Node 7 | Node 8 | Node 9 | Node 10 | Node 11 | Node 12 | Node 13 | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Node 0 | inf | 28.856187 | 15.699552 | 7.732602 | 46.397038 | 22.144679 | 23.873272 | 28.179447 | 20.448168 | 38.646409 | 50.267460 | 37.969171 | 76.139522 | 16.703630 |
Node 1 | 28.856187 | inf | 13.181848 | 31.509097 | 31.171604 | 7.704782 | 51.458387 | 30.896988 | 31.959957 | 16.471773 | 34.701714 | 23.643818 | 50.554715 | 43.198549 |
Node 2 | 15.699552 | 13.181848 | inf | 19.232318 | 36.621664 | 6.772074 | 38.803820 | 26.570343 | 22.711135 | 24.592380 | 39.510767 | 27.999713 | 62.153336 | 30.383238 |
Node 3 | 7.732602 | 31.509097 | 19.232318 | inf | 43.277932 | 26.002709 | 20.019733 | 22.532181 | 28.178039 | 43.630036 | 56.776046 | 35.337774 | 75.316976 | 21.214200 |
Node 4 | 46.397038 | 31.171604 | 36.621664 | 43.277932 | inf | 36.293663 | 60.031842 | 23.760875 | 59.332085 | 45.612566 | 64.275853 | 8.665196 | 35.760830 | 63.086706 |
Node 5 | 22.144679 | 7.704782 | 6.772074 | 26.002709 | 36.293663 | inf | 45.528377 | 30.725986 | 24.532734 | 18.036024 | 34.048241 | 28.047317 | 58.178126 | 35.680801 |
Node 6 | 23.873272 | 51.458387 | 38.803820 | 20.019733 | 60.031842 | 45.528377 | inf | 36.640480 | 39.614060 | 62.506215 | 73.455586 | 53.025378 | 93.974081 | 22.297529 |
Node 7 | 28.179447 | 30.896988 | 26.570343 | 22.532181 | 23.760875 | 30.725986 | 36.640480 | inf | 46.357641 | 47.216233 | 64.636059 | 18.189215 | 59.016978 | 43.717685 |
Node 8 | 20.448168 | 31.959957 | 22.711135 | 28.178039 | 59.332085 | 24.532734 | 39.614060 | 46.357641 | inf | 32.029531 | 36.031763 | 50.709054 | 82.453697 | 19.593126 |
Node 9 | 38.646409 | 16.471773 | 24.592380 | 43.630036 | 45.612566 | 18.036024 | 62.506215 | 47.216233 | 32.029531 | inf | 18.703091 | 39.098604 | 55.865019 | 48.897490 |
Node 10 | 50.267460 | 34.701714 | 39.510767 | 56.776046 | 64.275853 | 34.048241 | 73.455586 | 64.636059 | 36.031763 | 18.703091 | inf | 57.780461 | 70.505610 | 55.519599 |
Node 11 | 37.969171 | 23.643818 | 27.999713 | 35.337774 | 8.665196 | 28.047317 | 53.025378 | 18.189215 | 50.709054 | 39.098604 | 57.780461 | inf | 41.164498 | 54.672800 |
Node 12 | 76.139522 | 50.554715 | 62.153336 | 75.316976 | 35.760830 | 58.178126 | 93.974081 | 59.016978 | 82.453697 | 55.865019 | 70.505610 | 41.164498 | inf | 92.277455 |
Node 13 | 16.703630 | 43.198549 | 30.383238 | 21.214200 | 63.086706 | 35.680801 | 22.297529 | 43.717685 | 19.593126 | 48.897490 | 55.519599 | 54.672800 | 92.277455 | inf |
def plot_solution(_N, _path, _cities_coord, _cities_coord_dict):
plt.scatter(_cities_coord[:, 0],
_cities_coord[:, 1],
s=plot_size*2,
cmap='viridis',
zorder = 10000);
lines = []
for p in range(len(_path) - 1):
i = _path[p]
j = _path[p+1]
colour = 'black'
if p + 1 == (len(_path) - 1):
colour = 'red'
plt.arrow(_cities_coord_dict[i][0], _cities_coord_dict[i][1],_cities_coord_dict[j][0] - _cities_coord_dict[i][0], _cities_coord_dict[j][1] - _cities_coord_dict[i][1], color=colour)
for i in range(num_cities):
plt.annotate(i+1, (cities_coord[i, 0]+1, cities_coord[i, 1]+0.5))
plt.show()
name_to_index = {i:idx for idx,i in enumerate(cities_names)}
visited = [False if start_node is not _ else True for _ in cities_names]
route = [start_node]
curr = start_node
while False in visited:
row = dist_matrix[name_to_index[curr]]
for idx in range(len(row)):
if visited[idx]:
row[idx] = np.Inf
closest = np.argmin(row)
visited[closest] = True
curr = cities_names[closest]
route.append(curr)
plot_solution(cities_names, route, cities_coord, cities_coord_dict)
route.append(start_node)
plot_solution(cities_names, route, cities_coord, cities_coord_dict)