I have written a few lines of code that solves the problem would be easy to extend to solve for the shortest time rather than shortest distance, I could just use a TAS and wind to get an average groundspeed for each track. The code solves the shortest distance matrix, it does not know what the weights are in the matrix, they can be time or distance, or fuel.
# read the CSV with waypoints
waypoints=df.read_csv("sweden.csv")
# extract the colums with lat and long
latlon= waypoints[['Latitude','Longitude']].values
# number of waypoints
points=latlon.shape[0]
# create an empty square matrix to hold the distances between each waypoint
dist_matrix = np.zeros((points,points))
# calculate the great circle distance between all waypoints in nautical miles
for i in range(0, points):
for j in range(0, points):
dist_matrix[i,j]=great_circle(latlon[i],latlon[j]).nautical
# solve the shortest path through the waypoints
path = solve_tsp(dist_matrix,endpoints = (0,0))
It is robust enough to calculate all the shortest path for 1916 Swedish cities in this CSV,
https://github.com/sphrak/svenska-st...ska-stader.csv. It also outputs the route in PNG, KML, GPX, and CSV format
Full code here, its written in Python 3.8, it will run on a Mac, PC, or Unix Machine.
import pandas as df
import numpy as np
import matplotlib.pyplot as plt
from geopy.distance import great_circle
from mpl_toolkits.basemap import Basemap
from tsp_solver.greedy import solve_tsp
import simplekml, gpxpy, gpxpy.gpx, csv
# read the CSV with waypoints
waypoints=df.read_csv("sweden.csv")
# extract the colums with lat and long
latlon= waypoints[['Latitude','Longitude']].values
# number of waypoints
points=latlon.shape[0]
# create an empty square matrix to hold the distances between each waypoint
dist_matrix = np.zeros((points,points))
# calculate the great circle distance between all waypoints in nautical miles
for i in range(0, points):
for j in range(0, points):
dist_matrix[i,j]=great_circle(latlon[i],latlon[j]).nautical
# solve the shortest path through the waypoints
path = solve_tsp(dist_matrix,endpoints = (0,0))
#
# Plot the result
#
fig = plt.figure(figsize=(300, 300), edgecolor='w')
plt.plot( latlon[path,1], latlon[path,0], 'k-' )
plt.show()
m = Basemap(projection='tmerc',
lon_0=16., lat_0=62.,
resolution='l',
llcrnrlon=10, llcrnrlat=55, # LL = lower left
urcrnrlon=23, urcrnrlat=67) #UR = upper right
m.shadedrelief()
m.drawcoastlines()
m.drawcountries()
m.drawstates()
m.etopo(scale=0.5, alpha=0.5)
#
# Draw the tracks
#
for i in range(0,len(path)-1):
m.drawgreatcircle(latlon[path[i],1],
latlon[path[i],0],
latlon[path[i+1],1],
latlon[path[i+1],0]
,color='r')
plt.savefig('output.png')
#
# Write GPX File
#
gpx = gpxpy.gpx.GPX()
gpx_track = gpxpy.gpx.GPXTrack()
gpx.tracks.append(gpx_track)
gpx_segment = gpxpy.gpx.GPXTrackSegment()
gpx_track.segments.append(gpx_segment)
for i in range(0,len(path)-1):
gpx_segment.points.append(gpxpy.gpx.GPXTrackPoint(latlon[path[i],0], latlon[path[i],1]))
with open('output.gpx', 'w') as f:
f.write(gpx.to_xml())
#
# Write KML File
#
kml = simplekml.Kml()
for i in range(0,len(path)-1):
kml.newpoint(name=str(i), coords=[(latlon[path[i],1], latlon[path[i],0])])
for i in range(0, points-1):
linestring = kml.newlinestring(name="Sector "+str(i))
linestring.coords = [
(latlon[path[i],1], latlon[path[i],0],50),
(latlon[path[i+1],1], latlon[path[i+1],0],50)]
linestring.altitudemode = simplekml.AltitudeMode.relativetoground
kml.save("output.kml")
#
# Write CSV File
#
with open('output.csv', 'w', newline='') as file:
writer = csv.writer(file)
writer.writerow(["Track", "from_Lat","from_long", "to_Lat", "to_Long"])
for i in range(0,len(path)-1):
writer.writerow([i, latlon[path
,0], latlon[path,1],latlon[path[i+1],0], latlon[path[i+1],1]])