"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