# Route optimization

Thread Starter

Join Date: Sep 2020

Location: Stockholm

Posts: 3

**Route optimization**

Does anyone know of a good computor program for route optimazation?

I would like to import a lot of coordinates into the computer that can optimize the route to the shortest legnth, then export it as an KML and/or GPX- file.

I would like to import a lot of coordinates into the computer that can optimize the route to the shortest legnth, then export it as an KML and/or GPX- file.

Join Date: Dec 2006

Location: yes

Posts: 257

You are asking to solve a well-known problem in computer science referred to as the “travelling salesman”, or the “shortest path algorithm”. It’s complicated to say the least, as books have been written about it. Most software programs available optimize the results using road-routing (for delivery trucks), which I assume you don’t want. The backend programming access to Goggle Maps can solve this also, but AFAIK, only programmatically. Try searching for an Excel spreadsheet that performs shortest path. I found a few links that looked promising. However, the spreadsheet probably won’t use the lat/long but will rather need the distances between all points.

Join Date: Sep 2003

Location: Redding CA, or on a fire somewhere

Posts: 1,795

Join Date: Jun 2010

Location: Nanaimo, B.C.

Age: 63

Posts: 44

The problem here is that one quickly realizes that often the minimum time route is not the same as the minimum fuel route. Computing minimum fuel routes requires the input of aircraft performance. Having worked on algorithms to do this back in the 80's for airlines I can assure you that it is not trivial.

An example: what if the minimum distance route requires a climb to 10000' over a mountain? Would you want to choose that route over a longer distance valley route?

Still, there are many cases where the minimum distance route (usually but not always the minimum time route as well) is good enough.

An example: what if the minimum distance route requires a climb to 10000' over a mountain? Would you want to choose that route over a longer distance valley route?

Still, there are many cases where the minimum distance route (usually but not always the minimum time route as well) is good enough.

Join Date: Mar 2005

Location: N/A

Posts: 3,459

what if the minimum distance route requires a climb to 10000' over a mountain

Thread Starter

Join Date: Sep 2020

Location: Stockholm

Posts: 3

A comon thing here were i work and fly is that our customers who wants to fly and inspect forest (government people who inspect that the land owners have cut the forest in the correct way) might send me a bunch of objects (gps positions) they want to go to. It's usually a cluster of positions that could have a couple of hundred of meters between them and sometimes kilometers between them. Today we have a system for optimization, but it's old, verry slow and complicated.

Join Date: Dec 2006

Location: yes

Posts: 257

*Last edited by JimEli; 2nd Oct 2020 at 22:11.*

Join Date: Oct 2020

Location: USA

Posts: 3

I've thrown together some code to do this, enter a list of lat/long and it will find the shortest route. It is only really effective for less than 6 locations as it is using a brute force algorithm and the number of possible routes gets very large. Let me know if you are interested in checking it out.

**Eidolon**

Join Date: May 2001

Location: Some hole

Posts: 1,984

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

# 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]])*Join Date: Dec 2006

Location: yes

Posts: 257

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.

...

...

**Eidolon**

Join Date: May 2001

Location: Some hole

Posts: 1,984

I never claimed to have invented python, or its multitude of libraries, or the compiled libraries, the compilers, assembler language, operating system, or even the computer itself. The greedy.py solver is less than 200 lines of code (not including spaces or comments). It is not a complicated algorithm, nor is 2 -opt. I could write a 2-opt solver (https://en.wikipedia.org/wiki/2-opt) in less than 20 lines (which would be better solver for larger datasets). You made a very silly comment, like saying someone didn't write stdio.h math.h numpy or pandas or their associated compiled libraries so that any code that uses them is invalid. Everyone can see the libraries used.

You are basically accusing me of plagiarism, would you like to enlighten us all where such a start to end solution has been presented before for everyone to see ?

What did you actually do apart from pontificate and preach how difficult a problem it is ?

BTW, This is my solution to the US 48 states problem using the same code (starting and ending in Washington), you know the one you said had "6,206,957,796,268,036,335,431,144,523,686,687,519,260,743,1 7 7,338,880,000,000,000 possible tours (~6.2 novemdecillion)" which I solved in under 10 seconds.

Did you really come up with that number of tours, or did you just lift if off another web page to make yourself sound intelligent ?

*Last edited by swh; 7th Oct 2020 at 16:22.*

Join Date: Dec 2006

Location: yes

Posts: 257

Prone to flying off the handle? Because you just went all Fox-One on me. Try switching to 100% Ox before total GLOC. Nobody’s claiming plagiarism. I just pointed out that you called an imported, specialized library to do all the heavy lifting and create the TSP solution. Sort of like claiming you can multiply, but then using a calculator. You're the one that boasted. You also should have noted, that the imported algorithm, “does not guarantee to find the optimal solution.” I’ll ignore the remainder of your pointless drivel, however reference your comment about my post, you could have followed my link to the source of the comment. I did that so anyone but a disgruntled pelican could clearly see it wasn’t mine. And regarding enlightening, “us all where such a start to end solution has been presented before for everyone to see?” A few progenitors are,

https://jupyter.brynmawr.edu/service...15/TSPv3.ipynb

and,

Travelling Salesman Problem · Ross Scrivener

and the Concorde TSP Solver, widely regarded as the fastest true TSP solver in existence (BTW, its also an iPhone app),

https://en.wikipedia.org/wiki/Concorde_TSP_Solver

https://jupyter.brynmawr.edu/service...15/TSPv3.ipynb

and,

Travelling Salesman Problem · Ross Scrivener

and the Concorde TSP Solver, widely regarded as the fastest true TSP solver in existence (BTW, its also an iPhone app),

https://en.wikipedia.org/wiki/Concorde_TSP_Solver

**Eidolon**

Join Date: May 2001

Location: Some hole

Posts: 1,984

There is a big difference between the optimal solution and an optimised route, one is an academic exercise, the other a practical exercise. The OP was after a way to read a series of waypoints, determine an optimized route, and generate GPX and/or KLM files, which is exactly what my code does. The greedy algorithm is actually the best choice for this practical problem due to its speed and it optimises from the start of the trip, which means during the sortie they can pull off from the optimised route and do a fuel stop or crew swap and it will then recommence an optimised route again. Other algorithms optimize the entire route, and if you deviate from that route it needs to recalculate it all over again.

And regarding enlightening, “us all where such a start to end solution has been presented before for everyone to see?” A few progenitors are,

https://jupyter.brynmawr.edu/service...15/TSPv3.ipynb

and,

Travelling Salesman Problem · Ross Scrivener

and the Concorde TSP Solver, widely regarded as the fastest true TSP solver in existence (BTW, its also an iPhone app),

https://en.wikipedia.org/wiki/Concorde_TSP_Solver

https://jupyter.brynmawr.edu/service...15/TSPv3.ipynb

and,

Travelling Salesman Problem · Ross Scrivener

and the Concorde TSP Solver, widely regarded as the fastest true TSP solver in existence (BTW, its also an iPhone app),

https://en.wikipedia.org/wiki/Concorde_TSP_Solver

Join Date: Apr 2010

Location: USA

Posts: 595

Join Date: Jun 2010

Location: Nanaimo, B.C.

Age: 63

Posts: 44