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 or index < d) and ((index == d and x != d) or (x == d and index != d)):
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 AlgorithmThis is similar but different because this doesn’t necessarily visit all the points.
https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Categories: Code #### Shivanshu · January 11, 2020 at 12:12 pm

Hi, encountered this error…

Traceback (most recent call last):
File “C:\Program Files\Python37\world_tour\tsp.py”, line 45, in
ShortestGPSS = TSP(GPSS)
File “C:\Program Files\Python37\world_tour\tsp.py”, line 31, in TSP
dist_list = distancesFromGPSS(GPSS)
File “C:\Program Files\Python37\world_tour\tsp.py”, line 21, in distancesFromGPSS
Distance = distance((GPS[‘Lat’], GPS[‘Lon’]), (GPSS[x][‘Lat’], GPSS[x][‘Lon’])).kilometers
NameError: name ‘distance’ is not defined 