Flight planning software minimization algorithm

[Andrew Sarangan]

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.

[[email protected]]

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

[[email protected]]

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.

[Blanche]

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.

[Dave Butler]

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.

[Blanche]

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!

[Blanche]

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.

[Tony]

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 -

[Roy Smith]

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.

[Tony]

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.

[Andrew Sarangan]

On Feb 25, 7:28 pm, "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.
>


I normally do this stuff manually (using a computer nevertheless, but
manually entering the altitudes and ETDs), and it is a very cumbersome
process. The results are, like you say, are not dramatically
different, but I have found situations where moving the departure time
by a few hours, or planning a different fuel stop can shave off 30
minutes of flight time from a 500 mile trip. When the airplane cost is
$100/hr that could be an important consideration.

Also, in most flight planning situations we use a single cruising
altitude for the entire flight. Adjusting the cruising altitude on a
continuous basis is not handled by any software that I know of. If the
software can come up an ideal altitude profile, route profile and the
best time of departure, the pilot can then use this baseline
information from which to modify parameters to fit his specific
needs.

[Blanche]

Andrew Sarangan > wrote:
>Also, in most flight planning situations we use a single cruising
>altitude for the entire flight. Adjusting the cruising altitude on a
>continuous basis is not handled by any software that I know of. If the
>software can come up an ideal altitude profile, route profile and the
>best time of departure, the pilot can then use this baseline
>information from which to modify parameters to fit his specific
>needs.

Destination Direct (destroyed, then killed by SAIC) had an option
where you could enter the winds and temps at various altitudes and
depending on the altitudes generated by the planner or altered by
the user, the flight plan was recomputed appropriately.

Jepp's low-end FliteStar can use winds but since I won't open my
firewall to allow it to access the Jepp weather server, I don't
know how well it works. But it also uses a variation of the
Djikstra algorithm - easy to identify it when you watch it attempt
to generate a flight path given certain conditions.

Kinda fun, too.