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. |
Yeah, choppers have such a huge range that we need to fly great circles instead of Rhumb lines.
|
Thank you for the reply, that really helped me a lot!!
|
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.
|
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. |
Originally Posted by babbaz
(Post 10895296)
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. AirNav: Fuel Stop Planner |
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. |
what if the minimum distance route requires a climb to 10000' over a mountain |
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.
|
Mark the positions on a map and eyeball it? Or is that just too old-school?:)
|
ForeFlight, Garmin Pilot and SkyDemon can all do that.
|
Originally Posted by swh
(Post 10895684)
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. |
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.
|
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 https://i.ibb.co/BcS5LgR/sweeden-tsm.png 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]]) |
Originally Posted by swh
(Post 10899796)
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.
... |
Originally Posted by JimEli
(Post 10899851)
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 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 ? https://i.ibb.co/932tgLF/Figure-2020-10-07-235147.png |
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 |
Originally Posted by JimEli
(Post 10900207)
Prone to flying off the handle? Because you just went all Fox-One on me. Try switching to 100% Ox before total GLOC.
Originally Posted by JimEli
(Post 10900207)
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.
Originally Posted by JimEli
(Post 10900207)
Sort of like claiming you can multiply, but then using a calculator. You're the one that boasted.
Originally Posted by JimEli
(Post 10900207)
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.
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.
Originally Posted by Jimsli
(Post 10900207)
I did that so anyone but a disgruntled pelican could clearly see it wasn’t mine.
Originally Posted by Jimsli
(Post 10900207)
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 |
|
|
All times are GMT. The time now is 09:50. |
Copyright © 2024 MH Sub I, LLC dba Internet Brands. All rights reserved. Use of this site indicates your consent to the Terms of Use.