Flight planning software minimization algorithm

Most of the software out there will compute a flight based on the
user's route, time of departure and altitude. This is a fairly
straight forward task which could be done without a computer, as has
been the case for decades.

What I am looking for is the reverse. Given a destination, aircraft
type and a window of travel time (which could be a couple of days),
the software should come up with the best altitude, route and time of
departure. It should consider forecasted winds aloft, frontal
positions, icing potentials, turbulence and thunderstorms. The user
should be able to attach numeric weights to indicate the level of
importance to each factor. In other words, it should be a minimization
software considering a variety of decision matrix. At present I do
this by recomputing the flight for each scenario. This does get very
cumbersome, and is best done with an automated algorithm. If such a
thing exists, I would like to hear opinions.

On Feb 24, 6:59 pm, "Andrew Sarangan" wrote:
Most of the software out there will compute a flight based on the
user's route, time of departure and altitude. This is a fairly
straight forward task which could be done without a computer, as has
been the case for decades.

What I am looking for is the reverse. Given a destination, aircraft
type and a window of travel time (which could be a couple of days),
the software should come up with the best altitude, route and time of
departure. It should consider forecasted winds aloft, frontal
positions, icing potentials, turbulence and thunderstorms. The user
should be able to attach numeric weights to indicate the level of
importance to each factor. In other words, it should be a minimization
software considering a variety of decision matrix. At present I do
this by recomputing the flight for each scenario. This does get very
cumbersome, and is best done with an automated algorithm. If such a
thing exists, I would like to hear opinions.

Hi Andrew,

I have actually been considering making such an algorithm for my
shareware flight planner, AirPlan. When I get some time to delve into
it, I think I am going to work on it. The biggest challenge is
getting it to operate in a reasonable amount of time. Even on a multi-
Gigahertz speed PC, the number of permutations that have to be
investigated by the software algorithm are huge, especially for a
destination that is very far away...

Dean

On Feb 24, 7:59 pm, "Andrew Sarangan" wrote:
Most of the software out there will compute a flight based on the
user's route, time of departure and altitude. This is a fairly
straight forward task which could be done without a computer, as has
been the case for decades.

What I am looking for is the reverse. Given a destination, aircraft
type and a window of travel time (which could be a couple of days),
the software should come up with the best altitude, route and time of
departure. It should consider forecasted winds aloft, frontal
positions, icing potentials, turbulence and thunderstorms. The user
should be able to attach numeric weights to indicate the level of
importance to each factor. In other words, it should be a minimization
software considering a variety of decision matrix. At present I do
this by recomputing the flight for each scenario. This does get very
cumbersome, and is best done with an automated algorithm. If such a
thing exists, I would like to hear opinions.

Have you looked at Seattle Avionics Voyager? I don't have the full
version, but I think it will do most of the things you want. Even in
the free version (the one I have) you can easily test different
departure times and altitudes to optimize your time enroute. They
have a 30 day free trial to try out the more advanced features.

Andrew Sarangan wrote:

Most of the software out there will compute a flight based on the
user's route, time of departure and altitude. This is a fairly
straight forward task which could be done without a computer, as has
been the case for decades.

What I am looking for is the reverse. Given a destination, aircraft
type and a window of travel time (which could be a couple of days),
the software should come up with the best altitude, route and time of
departure. It should consider forecasted winds aloft, frontal
positions, icing potentials, turbulence and thunderstorms. The user
should be able to attach numeric weights to indicate the level of
importance to each factor. In other words, it should be a minimization
software considering a variety of decision matrix. At present I do
this by recomputing the flight for each scenario. This does get very
cumbersome, and is best done with an automated algorithm. If such a
thing exists, I would like to hear opinions.

There is something out there that does lots of this, but I don't think it's
available at the single user, spam-can level. Essentially, it's the
classic knapsack algorithm. You can choose to optimize for minimum
fuel or minimum time. It does routing based on weather and other factors
such as TFRs, etc. However it assumes you tell it either departure or
arrival time & location. AFAIK there's no way for the software to
provide the optimum without one of the inputs.

Andrew Sarangan wrote:
Most of the software out there will compute a flight based on the
user's route, time of departure and altitude. This is a fairly
straight forward task which could be done without a computer, as has
been the case for decades.

What I am looking for is the reverse. Given a destination, aircraft
type and a window of travel time (which could be a couple of days),
the software should come up with the best altitude, route and time of
departure. It should consider forecasted winds aloft, frontal
positions, icing potentials, turbulence and thunderstorms. The user
should be able to attach numeric weights to indicate the level of
importance to each factor. In other words, it should be a minimization
software considering a variety of decision matrix. At present I do
this by recomputing the flight for each scenario. This does get very
cumbersome, and is best done with an automated algorithm. If such a
thing exists, I would like to hear opinions.

The algorithm you are looking for is known as Djikstra's Algorithm, for
finding the optimum path through a network. You can google for it if
you're not familiar.

The network could be the nodes and airways of the airway system, but
this limits the available solutions to airways.

Winds, altitude requirements, leg lengths are relatively easily
accounted for. The trick is assigning costs to factors like frontal
penetrations, icing risk and thunderstorm risk.

Ref: "Data Structures & Algorithms", Aho, Hopcroft & Ullman, 1983
(who needs the stinkin' web when you have the books next to you?!]

begin
S:= {1};
for i := 2 to n do D[i] := C[1,i]; # initialize D
for i := 1 to n-1 do begin
choose a vertex w in V-S such that D[w] is a minimum;
add w to S;
for each vertex v in V-S do
D[v] := min(D[v],D[w]+c[w,v]);
end;
end;

computes the cost (you choose what you consider to be cost) of the
shortest path from vertex 1 to every vertex of the directed graph.
S is the set of vertices, D[] is the path

Then, of course, we can also consider the All-Pairs shortest path
problem, and I quote from AHU, "suppose we have a labeled digraph that
gives the flying time on certain routes connecting cities...."

Take a look at R.W. Floyd's for weighted digraphs.

Have fun!

Peter wrote:

"Andrew Sarangan" wrote


Most of the software out there will compute a flight based on the
user's route, time of departure and altitude. This is a fairly
straight forward task which could be done without a computer, as has
been the case for decades.

What I am looking for is the reverse. Given a destination, aircraft
type and a window of travel time (which could be a couple of days),
the software should come up with the best altitude, route and time of
departure. It should consider forecasted winds aloft, frontal
positions, icing potentials, turbulence and thunderstorms. The user
should be able to attach numeric weights to indicate the level of
importance to each factor. In other words, it should be a minimization
software considering a variety of decision matrix. At present I do
this by recomputing the flight for each scenario. This does get very
cumbersome, and is best done with an automated algorithm. If such a
thing exists, I would like to hear opinions.

Don't the airlines use this kind of tool already, for working out the
best routes?

Jeppesen do a product called Jetplanner, which I understand (from
someone working in an airline flight planning department) does this -
at least the winds aloft part of it. It is not priced for the GA
market, and my experience is that they cut off email communication
with you as soon as you ask how much it costs.

It uses the same database updates as Jeppview 3; this is evident from
the readme files on the JV3 CDs.

You need detailed performance data (versus altitude) for the aircraft;
something which is not available for most GA types.


It's called JetPlan and is the engine underneath OpsControl, which is
what you're thinking of (and what I was referring to earlier). And it
can handle all sorts of conditions. And as Peter pointed out, if you
have to ask, you can't afford it. Target market are small to medium
size carriers (large carriers usually have their own), charters
and business flight departments. There are also various military
organizations using it, or variations provided by Jepp.

Don't get too tangled up in trying to find some 'optimum'. This is
instructive: do a manual calculation of what you consider might be
three or four 'likely best' routes. When you get done cranking the
numbers, you'll likely find not an important difference in your
several results. It's that old thing when we learned calculus --
nothing very interesting happens near a maxima or minima.


If, on the other hand, you discover big differences between what you
considered to be two paths that you expected to be about the same,
(and you're sure the analysis is correct), you need to sharpen your
instincts (and that also would render moot all I've said earlier).

Blanche wrote:
Peter wrote:

"Andrew Sarangan" wrote

Most of the software out there will compute a flight based on the
user's route, time of departure and altitude. This is a fairly
straight forward task which could be done without a computer, as has
been the case for decades.

What I am looking for is the reverse. Given a destination, aircraft
type and a window of travel time (which could be a couple of days),
the software should come up with the best altitude, route and time of
departure. It should consider forecasted winds aloft, frontal
positions, icing potentials, turbulence and thunderstorms. The user
should be able to attach numeric weights to indicate the level of
importance to each factor. In other words, it should be a minimization
software considering a variety of decision matrix. At present I do
this by recomputing the flight for each scenario. This does get very
cumbersome, and is best done with an automated algorithm. If such a
thing exists, I would like to hear opinions.

Don't the airlines use this kind of tool already, for working out the
best routes?

Jeppesen do a product called Jetplanner, which I understand (from
someone working in an airline flight planning department) does this -
at least the winds aloft part of it. It is not priced for the GA
market, and my experience is that they cut off email communication
with you as soon as you ask how much it costs.

It uses the same database updates as Jeppview 3; this is evident from
the readme files on the JV3 CDs.

You need detailed performance data (versus altitude) for the aircraft;
something which is not available for most GA types.

It's called JetPlan and is the engine underneath OpsControl, which is
what you're thinking of (and what I was referring to earlier). And it
can handle all sorts of conditions. And as Peter pointed out, if you
have to ask, you can't afford it. Target market are small to medium
size carriers (large carriers usually have their own), charters
and business flight departments. There are also various military
organizations using it, or variations provided by Jepp.- Hide quoted text -

- Show quoted text -

In article .com,
"Tony" wrote:

Don't get too tangled up in trying to find some 'optimum'. This is
instructive: do a manual calculation of what you consider might be
three or four 'likely best' routes. When you get done cranking the
numbers, you'll likely find not an important difference in your
several results. It's that old thing when we learned calculus --
nothing very interesting happens near a maxima or minima.

Lots of curves have very interesting things happen at the maxima.
Coefficient of lift vs. angle of attack. Deflection vs. load factor for
the main wing spar. Leakage current vs. voltage for electrical insulation.

You're quite right when the maxima or minima happens near a
discontinunity -- I was thinking of more gentle models.


On Feb 25, 7:36 pm, Roy Smith wrote:
In article .com,

"Tony" wrote:
Don't get too tangled up in trying to find some 'optimum'. This is
instructive: do a manual calculation of what you consider might be
three or four 'likely best' routes. When you get done cranking the
numbers, you'll likely find not an important difference in your
several results. It's that old thing when we learned calculus --
nothing very interesting happens near a maxima or minima.

Lots of curves have very interesting things happen at the maxima.
Coefficient of lift vs. angle of attack. Deflection vs. load factor for
the main wing spar. Leakage current vs. voltage for electrical insulation.