Find the Shortest Distance/Route between a set/array of GPS Coordinates (Travelling salesman problem) – Python

Here is an example of a set of GPS coordinates:

GPSS = [{"Lat":40.641099,"Lon": -73.917094},{"Lat":40.60442,"Lon": -74.054873},{"Lat":40.779582,"Lon": -73.920213},{"Lat":40.651616,"Lon": -73.89097},{"Lat":40.755183,"Lon": -73.846248}]

This is python code I wrote to work out the distances from from each of the points without duplicating.

import geopy
from geopy import distance #Forgot to add.
def distancesFromGPSS(GPSS):
	Distances = []
	for index, GPS in enumerate(GPSS):
		for x in range(0, len(GPSS)):
			if index != x:
				if Distances:
					for d in Distances:
						NotFound = False
						if (index < d[0] or index < d[1]) and ((index == d[0] and x != d[0]) or (x == d[1] and index != d[1])):
							NotFound = True
							break
					if NotFound:
						Distance = distance((GPS['Lat'], GPS['Lon']), (GPSS[x]['Lat'], GPSS[x]['Lon'])).kilometers
						Distances.append((index, x, Distance))
				else:
					Distance = distance((GPS['Lat'], GPS['Lon']), (GPSS[x]['Lat'], GPSS[x]['Lon'])).kilometers
					Distances.append((index, x, Distance))
	return Distances

You should then get something like this:

dist_list = [(0, 1, 12.34895151892164), (0, 2, 15.380561959360797), (0, 3, 2.499303143635897), (0, 4, 14.012560598709298), (1, 2, 22.53687775052488), (1, 3, 14.824576927209662), (1, 4, 24.318038568441654), (2, 3, 14.423642658224264), (2, 4, 6.807346029310139), (3, 4, 12.106031672624894)]

We then feed this array of distances into this function:

import mlrose
import numpy as np
def TSP(GPSS):
	dist_list = distancesFromGPSS(GPSS)
	print(dist_list)

	fitness_dists = mlrose.TravellingSales(distances = dist_list)
	problem_fit = mlrose.TSPOpt(length = len(GPSS), fitness_fn = fitness_dists, maximize=False)
	best_state, best_fitness = mlrose.genetic_alg(problem_fit, mutation_prob = 0.2, max_attempts = 100, random_state = 2)
	print('The best state found is: ', best_state)
	print('The fitness at the best state is: ', best_fitness)

	ShortestGPSS = []
	for b in best_state:
		ShortestGPSS.append(GPSS[b])
	return ShortestGPSS

ShortestGPSS = TSP(GPSS)

Outcome:

[{'Lat': 40.755183, 'Lon': -73.846248}, {'Lat': 40.651616, 'Lon': -73.89097}, {'Lat': 40.641099, 'Lon': -73.917094}, {'Lat': 40.60442, 'Lon': -74.054873}, {'Lat': 40.779582, 'Lon': -73.920213}]

References:

Solving Travelling Salesperson Problems with Python

https://towardsdatascience.com/solving-travelling-salesperson-problems-with-python-5de7e883d847

Example 4: Example 4: Travelling Salesperson Using Distance-Defined Fitness Function

https://github.com/gkhayes/mlrose/blob/master/tutorial_examples.ipynb

Travelling Salesman Problem
https://en.wikipedia.org/wiki/Travelling_salesman_problem

Dijkstra’s Algorithm – This is similar but different because this doesn’t necessarily visit all the points.
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm