AVIATIONTOOLBOX: automatic route selection

"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

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