Route optimization

[babbaz]

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.

[Ascend Charlie]

Yeah, choppers have such a huge range that we need to fly great circles instead of Rhumb lines.

[babbaz]

Thank you for the reply, that really helped me a lot!!

[JimEli]

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.

[swh]

Not difficult to do, could probably write that in 20 lines of code.



Many people have also implemented Dijkstra's algorithm in excel also, you could possibly find a spreadsheet for it online.

[Gordy]

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.
This works for airports:

AirNav: Fuel Stop Planner (http://www.airnav.com/plan/fuel/)

[dash34]

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.

[megan]

what if the minimum distance route requires a climb to 10000' over a mountainHad this scenario presented by the CP during a IMC test, the shortest route had a high LSALT and with the OAT given would have been unable to remain above the terrain should an engine failure occur, the only option was to follow an airway that went down a valley which added considerable track miles. Had icing been a consideration the same would have applied.

[babbaz]

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.

[[email protected]]

Mark the positions on a map and eyeball it? Or is that just too old-school?:)

[RMK]

ForeFlight, Garmin Pilot and SkyDemon can all do that.

[JimEli]

Not difficult to do, could probably write that in 20 lines of code.
Many people have also implemented Dijkstra's algorithm in excel also, you could possibly find a spreadsheet for it online.
“Travelling Salesman Problem” (TSP) is not a trivial problem. In computer science it is termed “NP-Hard (https://en.wikipedia.org/wiki/NP-hardness)”. For example, the Dantzig49 (https://stemlounge.com/animated-algorithms-for-the-traveling-salesman-problem/) variant of TSP requires a tour be constructed of 48 cities, one each in every continental US state plus Washington, DC. There are (n-1!)/2 possible tours to a TSP, so Dantzig49 has 6,206,957,796,268,036,335,431,144,523,686,687,519,260,743,17 7,338,880,000,000,000 possible tours (~6.2 novemdecillion). We'll wait here for the 20 lines (AFAIK, Dijsktra doesn't necessarily solve the problem).

[Waypoint Short]

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.

[swh]

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=great_circle(latlon,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-stader/blob/master/src/svenska-stader.csv. It also outputs the route in PNG, KML, GPX, and CSV format

https://i.ibb.co/BcS5LgR/sweeden-tsm.png (https://ibb.co/hLtJsKv)

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[i],0], latlon[path[i],1],latlon[path[i+1],0], latlon[path[i+1],1]])

[JimEli]

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.
...
Since solving the actual routing of the TSP is performed in several hundred lines of imported code, you could have at least mentioned attribution.

[swh]

Since solving the actual routing of the TSP is performed in several hundred lines of imported code, you could have at least mentioned attribution.

I wrote the python code above that reads in the waypoints from a CSV file, calculates the great circle distance between those waypoints, calculates the minimum cost through the waypoint network, and outputs that minimum cost path as PNG, CSV, KML, GPX. I used existing python libraries as the code works, however in order to know which libraries to use, I needed how to solve the problem, how to get the data in the correct format to use the libraries, and how to use the results.

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,17 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 ?

https://i.ibb.co/932tgLF/Figure-2020-10-07-235147.png (https://imgbb.com/)

[JimEli]

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/services/public/dblank/jupyter.cs/FLAIRS-2015/TSPv3.ipynb

and,

Travelling Salesman Problem · Ross Scrivener (http://rossscrivener.co.uk/blog/travelling-salesman-problem/)

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

[swh]

Prone to flying off the handle? Because you just went all Fox-One on me. Try switching to 100% Ox before total GLOC.

You are being a prat.

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.

You said I failed to attribute the code of others, what I posted is my original work. All the modules used are clearly listed at the top of the code. No different to the Concorde you mentioned, it actually uses QSOpt to do the solving, that does detract from them knowing how to use QSOpt and getting the data in a format to to use it.

Sort of like claiming you can multiply, but then using a calculator. You're the one that boasted.

All I said was "Not difficult to do, could probably write that in 20 lines of code", I never claimed I would build the computer, operating system, compilers and everything from scratch in 20 lines. I did exactly what I said I could do, produced the results, meanwhile you blew more hot air.

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.

My pointless drivel ? What have you actually contributed to this thread except from what you have copied without quoting from other websites ?

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.

I did that so anyone but a disgruntled pelican could clearly see it wasn’t mine.

Everyone can see your true colors, plagiarizing content from others and then throwing personal insults when exposed.

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/services/public/dblank/jupyter.cs/FLAIRS-2015/TSPv3.ipynb

and,

Travelling Salesman Problem · Ross Scrivener (http://rossscrivener.co.uk/blog/travelling-salesman-problem/)

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

None of those can do what my code does, i.e. read a CSV file of LAT/LON, calculate tracks on a WGS84 ellipsoid, calculate a optimised route, and output a KML/GPX/CSV file.

[aa777888]

Possibly of interest...

https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/

[dash34]

https://www.quantamagazine.org/computer-scientists-break-traveling-salesperson-record-20201008/?utm_source=Nature+Briefing&utm_campaign=721872f932-briefing-dy-20201012&utm_medium=email&utm_term=0_c9dfd39373-721872f932-45608622

[etudiant]

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/services/public/dblank/jupyter.cs/FLAIRS-2015/TSPv3.ipynb

and,

Travelling Salesman Problem · Ross Scrivener (http://rossscrivener.co.uk/blog/travelling-salesman-problem/)

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

Sorry, you don't sound competent.
Roosevelt (Teddy) pointed out :It is not the critic who counts... the credit belongs to the man who is actually in the arena
Swh has provided a useful bit of work. What have you contributed?

[JimEli]

Attached is my alternative program. Like the posted code above, it doesn’t necessarily provide the optimum (or shortest) tour through all points. As I stated above, as the number of points grow, the possible number of tours increases as a factor (n!). Therefore, the code can't search every possible path, but uses an approximating algorithm that in most cases finds a tour that is short, but not guaranteed to be the shortest. But it’s very fast. The program is a Windows executable which uses the Chrisofides algorithm (https://en.wikipedia.org/wiki/Christofides_algorithm) with 2-opt optimization (https://en.wikipedia.org/wiki/2-opt). Feed it a csv file consisting of pairs of lat/long points, and it outputs a kml file.

Here are a few examples of output displayed in Google Earth:

48 US state capitols
https://cimg2.ibsrv.net/gimg/pprune.org-vbulletin/640x337/48x640_a9e37482a1b14108ebd3f6502b6fb804d988a592.jpg
Sweden Cities (on my laptop, an 1.6GHz i5, it runs in approx. 2 seconds)
https://cimg6.ibsrv.net/gimg/pprune.org-vbulletin/640x469/sweden640_f63fb6c7d9a6384e4f8571c8775404921444c66b.jpg
It took me longer to accomplish this because I don’t live in my parent’s basement. Due to size, the C++ source code is available via pm.