![]() |
If this is your first visit, be sure to check out the FAQ by clicking the link above. You may have to register before you can post: click the register link above to proceed. To start viewing messages, select the forum that you want to visit from the selection below. |
|
|
Thread Tools | Display Modes |
|
#1
|
|||
|
|||
![]()
"Ben Jackson" wrote in message
news:tCmbd.121529$He1.75934@attbi_s01... I keep meaning to apply Dijkstra's algorithm to airway routing. The key will be choosing edge costs. I tried something similar for Western Europe. Thinking aloud... My algorithm was basically: a) load the entire airway network as a graph using distances as costs b) link airports to the network using SIDs and STARs (important in Europe, probably less so in US) c) add preferred routes using the a cost of start_to_end_great_circle_distance * factor, where factor is just less than 1. d) run Dijkstra's algorithm (I was doing this in Perl so I just used the Graph module from CPAN) for a departure airport e) store the least cost routing from the departure airport to everywhere else in a database Repeat for other departure airports of interest. Processing time for one departure airport for my network was about 30s on a fairly typical desktop machine. YMMV, literally. ;-) Provided your airway network only changes every 28 days (can't speak for the US but that's what happens in the rest of the world for aeronautical data), you've then got "static" routes valid for a month which means that to run this for 100 airports or so, it should be a case of "do the calculation once and store the results". You can do this all with appropriate costs assigned to the routes and transitions that you want. The tricky part is weighting thoses costs properly against whatever you consider to be overriding factors (eg forecast winds, icing, aircraft performance, distance, available nav equipment, ...) Adding dynamic issues is not only difficult from a "what cost factor do I use?" point of view, but actually affects the entire strategy. Calculating weighted factors based on winds means that you have to do a calculation for the entire network (you may be able to preload the network, but you still have to run a weighting factor calc for each edge) which is likely to be very time consuming. You then have to run Dijkstra's algorithm to get the least-cost routes. But now we're doing that for *every* flight, which means that we wait for both steps of the processing (edge costs + Dijkstra) instead of doing a database lookup on stuff that's run once a month. I wondered about a middle ground. If you could store the 10 or even 100 least-cost routes for a particular airport-pair, then running those routes for a single flight would be relatively quick (either individually or doing Dijkstra on the much reduced network). But Dijkstra doesn't produce the runners up, only the winner, so how do we find the set of 10 or 100 routes to consider? Do you knock out legs and run the algorithm again? If so, which ones? Reducing the network to waypoints within x miles of the great circle for a particular flight (a little like Paul Tomblin's suggestion) is one possibility, but, at least in Europe, x would have to be pretty big. On a 3 hour trip to Germany from my home base in the UK, I basically have the choice between an initial route that goes east over Holland, or south and then south east over Belgium. For a 450 mile route, I have to consider a band of possibilities at least 150 miles wide. Anyway, just sharing some thinking. Julian Scarfe |
#2
|
|||
|
|||
![]()
"Julian Scarfe" writes:
"Ben Jackson" wrote in message news:tCmbd.121529$He1.75934@attbi_s01... I keep meaning to apply Dijkstra's algorithm to airway routing. That was my first thought...'course it's about all I remember about network theory... The key will be choosing edge costs. What's the difficulty here? The airway file contains distances. Are we not treating airways as the network edges? I tried something similar for Western Europe. Thinking aloud... My algorithm was basically: a) load the entire airway network as a graph using distances as costs b) link airports to the network using SIDs and STARs (important in Europe, probably less so in US) c) add preferred routes using the a cost of start_to_end_great_circle_distance * factor, where factor is just less than 1. Hmmmm...I like that. It would allow for lots of tweaking too. d) run Dijkstra's algorithm (I was doing this in Perl so I just used the Graph module from CPAN) for a departure airport e) store the least cost routing from the departure airport to everywhere else in a database Repeat for other departure airports of interest. Processing time for one departure airport for my network was about 30s on a fairly typical desktop machine. YMMV, literally. ;-) I wasn't planning to do a lot of precomputation. When we get into altitude restrictions it just gets too complicated. The shortest path for me from Indiana to California is going to be much different than for someone who is going to stay below 8,000'. Besides altitude restrictions, I can imagine wanting to specify avoidance of MOAs, long overwater segments, busy airspace, etc. Adding dynamic issues is not only difficult from a "what cost factor do I use?" point of view, but actually affects the entire strategy. Calculating weighted factors based on winds means that you have to do a calculation for the entire network Oh, yeah...winds too. (you may be able to preload the network, but you still have to run a weighting factor calc for each edge) which is likely to be very time consuming. You then have to run Dijkstra's algorithm to get the least-cost routes. But now we're doing that for *every* flight, which means that we wait for both steps of the processing (edge costs + Dijkstra) instead of doing a database lookup on stuff that's run once a month. It's not clear to me that this is a terrible burden. A student sitting in front of enroute charts can figure out reasonable solutions so I assume I can program a computer to do the same in short order. I think that learning to disregard edges that aren't of interest is the key. This seems fairly simple at first but in mountainous regions with low altitude restrictions it could get difficult because you might need to go far away from a direct route. Reducing the network to waypoints within x miles of the great circle for a particular flight (a little like Paul Tomblin's suggestion) is one possibility, but, at least in Europe, x would have to be pretty big. On a 3 hour trip to Germany from my home base in the UK, I basically have the choice between an initial route that goes east over Holland, or south and then south east over Belgium. For a 450 mile route, I have to consider a band of possibilities at least 150 miles wide. This doesn't sound so bad to me. I don't have a grasp on the power required to solve it though. Anyway, just sharing some thinking. Indeed! I appreciate the thoughts! --kyler |
#3
|
|||
|
|||
![]()
Kyler Laird wrote:
It's not clear to me that this is a terrible burden. A student sitting in front of enroute charts can figure out reasonable solutions so I assume I can program a computer to do the same in short order. I always got stuck at trying to find a reasonable choice for the node at which the enroute structure should be entered and exited. Once you pick the end points (where to enter and leave) the choice of routes is just an OR optimization problem, as others have noted. I think that learning to disregard edges that aren't of interest is the key. This seems fairly simple at first but in mountainous regions with low altitude restrictions it could get difficult because you might need to go far away from a direct route. Perhaps altitude requirements need to be included in the costs. Dave |
#4
|
|||
|
|||
![]() I like the idea of running the script once a month, but for 20.00 airports this would be a quite database. Another idea is when we have found preferred routes, also store use routes (routes that user knows he/she will get from atc after filin different route)... mainly for busy areas NY etc... atc's ow prefferred routing as previously mentioned. We will be using mapserver with this project and use mysql for db. Php or cgi script for this would be nice http://www.v1rotate.com View this thread: http://www.v1rotate.com/portal/forum...?threadid=9334 |
#5
|
|||
|
|||
![]()
In article ,
Julian Scarfe wrote: Repeat for other departure airports of interest. Processing time for one departure airport for my network was about 30s on a fairly typical desktop machine. YMMV, literally. ;-) I think you can do better than that by ordering your edges better. You know more than just edge costs, you also have coordinates for each node. You can choose to explore edges that move you closer to the destination first. IIRC, the key to making Dijkstra fast is to find a solution as early as possible. That establishes a baseline cost that allows massive pruning of the search space. least-cost routes. But now we're doing that for *every* flight, which means that we wait for both steps of the processing (edge costs + Dijkstra) instead of doing a database lookup on stuff that's run once a month. Right. But if I'm going to do the work then I want it to calculate all of the factors that I would, given infinite time and patience on my part. -- Ben Jackson http://www.ben.com/ |
#6
|
|||
|
|||
![]()
In article ,
Julian Scarfe wrote: Repeat for other departure airports of interest. Processing time for one departure airport for my network was about 30s on a fairly typical desktop machine. YMMV, literally. ;-) "Ben Jackson" wrote in message news:rTzbd.249118$D%.142632@attbi_s51... I think you can do better than that by ordering your edges better. You know more than just edge costs, you also have coordinates for each node. You can choose to explore edges that move you closer to the destination first. IIRC, the key to making Dijkstra fast is to find a solution as early as possible. That establishes a baseline cost that allows massive pruning of the search space. That may be the case. I should have said that what I was trying to do was create a server-based system for large numbers of users with different dep-dest pairs. In that case, I'm looking at all potential destinations in parallel. The strategy for a client-based system starting from scratch for every single flight might be rather different. Julian |
#7
|
|||
|
|||
![]()
"Julian Scarfe" wrote in message ...
"Ben Jackson" wrote in message news:tCmbd.121529$He1.75934@attbi_s01... I keep meaning to apply Dijkstra's algorithm to airway routing. The key will be choosing edge costs. I tried something similar for Western Europe. Thinking aloud... My algorithm was basically: a) load the entire airway network as a graph using distances as costs *** I would modify that to use a combination of distance and MEA as the cost. I've found that in my personal flight planning, lower MEAs often translate into a better flight, even if they involve a bit of a dogleg. - Jerry Kaidor ( ) |
Thread Tools | |
Display Modes | |
|
|
![]() |
||||
Thread | Thread Starter | Forum | Replies | Last Post |
IFR route BOS - IAD? | Peter MacPherson | Instrument Flight Rules | 2 | September 4th 04 05:46 AM |
NAS and associated computer system | Newps | Instrument Flight Rules | 8 | August 12th 04 05:12 AM |
filing IFR plan for VFR flight conditions | Paul Safran | Instrument Flight Rules | 53 | May 11th 04 03:07 AM |
Route planning question | Paul Tomblin | Instrument Flight Rules | 3 | April 4th 04 02:40 PM |
My route to the 3rd annual ParasolAirplanes Fly In | Scott | Home Built | 1 | July 18th 03 07:28 PM |