SYSTEMS AND METHODS FOR PROVIDING EN ROUTE REROUTING

PRIORITY

The present application claims priority to U.S. Provisional Patent Application No. 62/714,345, filed August 3, 2018, the disclosure of which is hereby incorporated by reference in its entirety.

BACKGROUND

In the United States, the National Airspace System (NAS) serves several tens of thousands of civil transport flights each day, transporting several millions of passengers and significant volumes of cargo. Given the large number of flights, and considerable cost of fuel and time involved, even seemingly minor improvements in flight time and efficiency can yield substantial economic savings.

One source of inefficiency, and opportunity for savings, is the routes used by civil transport flights. Civil transport routes are subject to several complicating factors and constraints, including: weather, airspace availability and procedures, traffic, and aircraft performance. These complicating factors and constraints often impose route inefficiencies. For example, flight plans are required to be formulated and filed 1-2 hours prior to gate departure, and are required to route conservatively around forecasted convective weather.

Because routing is both economically important and technically challenging, there remains a need, therefore, for a more efficient air traffic re-routing system.

SUMMARY

In accordance with an embodiment, the invention provides a system for providing rerouting information based, in part, on a probability of route acceptance.

In accordance with another embodiment, the invention provides a method for providing rerouting information. The method includes the steps of determining a probability of route acceptance, and providing the rerouting information base, in part, on the probability of route acceptance.

In accordance with further embodiments, the invention provides a system for providing rerouting information based, in part, on decision tree analyses involving decisions to request and decisions to not request a reroute.

BRIEF DESCRIPTION OF THE DRAWINGS

The following description may be further understood with reference to the accompanying drawings in which:

Figure 1 shows an illustrative diagrammatic view of a notional diagram of types of reroutes in accordance with an embodiment of the present invention;

Figure 2 shows an illustrative diagrammatic view of a notional diagram showing two potential reroutes in accordance with an embodiment of the present invention;

Figure 3 shows an illustrative diagrammatic graphical representation of a notional probability distribution for a single reroute acceptance metric in accordance with an embodiment of the present invention;

Figure 4A shows an illustrative diagrammatic graphical representation of candidate reroutes distributed by reroute probability and reroute savings in accordance with an embodiment of the present invention;

Figure 4B shows an illustrative diagrammatic graphical representation of a maximum expected savings (EfY)) frontier in accordance with an embodiment of the present invention;

Figure 4C shows an illustrative diagrammatic view of a notational diagram of a cost of flight delay relative a scheduled flight time in accordance with an embodiment of the present invention; Figure 4D shows an illustrative diagrammatic graphical representation of a notional diagram of a linear maximum (EfY)) frontier in accordance with an embodiment of the present invention;

Figure 5 shows an illustrative diagrammatic graphical representation of an example of optimum single reroute as a second reroute in optimum two-reroute strategy;

Figure 6 shows an illustrative diagrammatic graphical representation of an example timeline of a cluster or upcoming candidate reroutes in accordance with an embodiment of the present invention;

Figure 7 shows an illustrative diagrammatic representation of a probabilistic binary decision tree for candidate reroute in accordance with an embodiment of the present invention;

Figure 8 shows an illustrative diagrammatic representation of the probabilistic binary decision tree for candidate reroute of Figure 7 with certain candidate reroutes blocked out;

Figure 9 shows an illustrative diagrammatic view of a fully -feasible, one-sided, probabilistic binary decision tree for requesting a particular reroute (Rl) in accordance with an embodiment of the present invention;

Figure 10 shows an illustrative diagrammatic view of a fully-feasible, one-sided, probabilistic binary decision tree for not requesting a particular reroute (Rl) in accordance with an embodiment of the present invention;

Figure 11 shows an illustrative diagrammatic representation of expected cost savings calculations for decisions to request and to not request a particular reroute (Rl) in accordance with an embodiment of the present invention; and

Figure 12A - 12D show an illustrative diagrammatic representations of decision combinations to be evaluation in accordance with an embodiment of the present invention.

The drawings are shown for illustrative purposes only. DETAILED DESCRIPTION

Applicant has developed an advanced routing decision support tool for NAS operators (SmartRoutes™ routing decision support tool). The SmartRoutes™ tool is related to the NASA Dynamic Weather Routing (DWR) tool, with numerous significant additional advanced capabilities. One capability that routing tools such as DWR lack is higher-level, route optimization, decision support. Route design tools such as DWR may produce multiple routing options for a given flight, but they do not provide users with an optimization strategy for using those routes.

Tools such as DWR are capable of identifying multiple candidate reroutes for a given flight, for example, within an Air Route Traffic Control Center (ARTCC). As Figure 1 (which shows a notational diagram of types of reroutes) illustrates, the reroutes may be direct to a downstream point or they may be multi-leg, they may initiate at the same or different points, and they may rejoin, or capture, the flight plan at the same of different points. In particular, Figure 1 shows a planned route 10 with flight plan fixed locations 20, which bypasses inclement weather 12. Direct-to reroutes 14 provide direct reroutes to certain fixed locations 20, while multi-leg reroutes 16 provide routes to fixed locations 20 via auxiliary waypoints 18 as shown.

The invention provides a reroute optimizer system (SmartRoutes™) using one or more processing systems 28, which provides a new, novel, and important method for optimizing civil transport reroute technology. The concept includes six primary innovations, including a decision-making method for optimizing a flight’s rerouting strategy, a method for modeling and predicting the operational acceptability of a reroute, a method for modeling and including the true, nonlinear, user cost of delay, a method for conducting air-ground negotiations via data-link, a method for optimizing across multiple flights, and a method for deciding when and how to convert time savings to additional fuel savings in accordance with various embodiments.

Tools such as DWR are designed to select the first available reroute that exceeds a preset savings threshold. While this may be the best strategy in some scenarios, it does impose an opportunity cost, as it may preclude other downstream candidate reroutes in the ARTCC (i.e., if they temporally overlap), or more complex rerouting and negotiation strategies.

For example, if an overlapping downstream reroute has a significantly higher savings, and/or operator acceptability, compared to an immediate reroute, then the opportunity cost of selecting the first threshold-exceeding reroute may be too high. On the other hand, the upstream reroute enjoys the advantage of having the downstream reroute as a fallback plan if the first reroute is operationally rejected. In essence, it has two tries at enacting a reroute. An example of this scenario may occur when a flight is nearing an ARTCC boundary and thus will have longer reroutes available to it. What is needed is a principled, objective method for optimally selecting which reroutes to use. The following sections describe approaches of various embodiments of the invention to this problem.

Tools such as DWR produce relatively accurate estimates of the flight time savings for each candidate reroute it generates. Different reroutes, however, may have significantly different chances of operational acceptance. A candidate reroute may be rejected at the airline dispatch, flight deck, or ATC levels, for a variety of reasons. The different reasons are discussed herein in which they are modelled and used to estimate the overall probability of route acceptance. This probability allows the system to compute the expected savings for a given reroute candidate in accordance with an embodiment as:

E{S) = P _a x S_DWR (1) where P _a is the probability of acceptance, S is the flight time savings, S DWR is the flight time savings as estimated by DWR, and E(L') is the expected value of the flight time savings.

Now consider the case of two, candidate reroutes, Ri and R2, with savings Si and <¾, respectively, which cannot both be executed, as illustrated in Figure 2, which shows a two re route case, with a first reroute 22 and a second reroute 24 from the planned route 10 that includes fixed locations 20 and which bypasses inclement weather 12.

Initially consider the case of a common acceptability probability, P _a . Consider two candidate actions, Actio and Actiom, which select Ri and R2, respectively. For each action, the expected savings may be derived. For Actiom, assume that if Ri is operationally rejected, then R2 will be attempted. Therefore, the expected savings of Actiom is a linear combination of the savings of the two reroutes multiplied by the probability they are flown:

E(S_Action ₁ ) = P _a x S_DWR ₁ + (1 - P _a )P _a x S_DWR ₂ (2) where S DWRi is the flight time savings of Ri as estimated by DWR, and S DWRi is the flight time savings of R2 as estimated by DWR. From Eq.(l), the Actiom expected savings is:

E(S_Action ₂ ) = P _a x S_DWR ₂ (3)

Consider a user whose objective is to maximize the expected savings of the reroute actions. The expected value of Actiom is subtracted from that of Actiom. If this expression is positive, then Actiom is indicated (i.e., its expected value is greater than that of Actiom).

S_DWR ₁ - P _a x S_DWR ₂ > 0

S_DWR ₁ > P _a x S_DWR ₂ (4) Therefore, in the two-reroute case with a common probability of acceptance, Actio is indicated if the savings of Ri exceeds the savings or R2 multiplied by the probability of acceptance; otherwise, Actiom is indicated. Or in other words, Actiom is selected only if the savings of R2 is sufficiently higher than that of Ri to offset the advantage that Actiom has of having R2 as a fallback plan if Ri is rejected.

If the probability of acceptance is different for Ri and R2, then the decision derivation is slightly more complicated. Initially, generalize Eq. (2):

E{S_Action ₁ ) = P _al x S_DWR ₁ + (1 - P _al )P _a2 x S_DWR ₂ (5) where P _{a 1} is the probability of acceptance of Ri, and Pai is the probability of acceptance of R2. It then follows that:

E(S_Action ₁ ) - E(S_Action ₂ ) = P _al x S_DWR _t + (1 - P _ai )P _a 2 x S_DWR ₂ - P _a2 x S_DWR ₂

Again set the expression greater than zero to test for the conditions when Actiom is indicated.

P _ai ^x S_DWR ₁ + (1— P _ai )P _a 2 x S_DWR ₂ — P _a2 x S _DWR2 > 0

P ±S_DWR ₁ + (1 - P _al )S_DWR ₂ - S _DWR2 > 0

— S_DWR ₁ - P _al x S_DWR ₂ > 0

pa2

S_DWR ₁ > P _a2 x S_DWR ₂ (6)

In this case Pai becomes the critical probability. Actiom is indicated if the savings of Ri exceeds the savings or R2 multiplied by the probability of acceptance of R2. Equation (6) provides an objective decision-making criterion in this two reroute case, when the objective is to maximize the expected savings. This highlights the importance of estimating the probability of route acceptance as discussed further below. The probability of route acceptance may be determined as follows. The primary influences on route acceptance or rejection, by operators at the airline dispatch, flight deck, and Air Traffic Control (ATC) levels are discussed as follows. These influences include: Reroute complexity, Controller workload, Route historical frequency of use, and Constraint proximity.

Each of these factors may be quantitatively modeled, and used in an overall estimate of the probability of route acceptance. Field data (SmartRoutes™ field data) may be used in a machine learning approach to fine-tune the model.

Reroute complexity may be analyzed as follows. Any candidate reroute must be evaluated and communicated by the airline dispatcher, flight crew, and air traffic controller. Therefore, as the complexity of the reroute increases, the chances of rejection, at any of these stages, increases. The route complexity, RC, may be modeled as the number of fixes and/or jet routes comprising the reroute.

A key factor in ATC acceptability of a reroute request is the controller workload. Controller workload may be modelled using current or expected traffic and weather metrics, including: the traffic loading in an airspace sector relative to the nominal sector capacity; the presence of convective weather, modeled as the fraction of the sector area with Corridor Integrated Weather System (CIWS) level three or higher (Vertically Integrated Liquid (VIL)3+) and with echo tops above the sector altitude floor, traffic entry and exit events in the sector over some time period, the number of climbing or descending flights in the sector vs. the number of level flights, aircraft reroutes that clip the sector or Center comer, resulting in relatively short flight time within the sector or Center and therefore short time between hand-offs, and aircraft reroutes that run along a sector or Center boundary requiring complicated coordination between controllers. Controller workload can vary substantially, and therefore impact the reroute selection. Field data is analyzed to determine the best functional form and fit to estimate the controller workload, CW.

Another factor in the ATC acceptability of a reroute request is the historical use of the route. Reroutes using obscure or rarely used routes are less likely to be accepted than reroutes using familiar, commonly-used routes. Historical surveillance and flight plan data is mined to build a database of common routes. The route legs and combination or route legs are flown is determined, and their frequency of use, in terms of number of flights which flew each leg or combination of legs, per month of historical data.

This data is used to assign an overall route frequency metric, RF, for each candidate reroute. The metric RF is the mean frequency value of the route, taken over the legs comprising the route. Reroute tools such as DWR do not produce suggested reroutes that enter closed airspace, transit heavy convective weather, or otherwise violate known constraints. Nonetheless, reroutes may have close proximity to constraints, and these can affect the operational acceptability, particularly at the dispatch and flight deck stages.

Therefore, a constraint proximity metric, CP, is created, which is the horizontal range from the aircraft to the nearest constraint, at point of closest approach (PCA). The metric CP is a measure of the separation from constraints, including: currently closed airspace, heavy convective weather, and whether upwind or downwind from the convection, and traffic. For convective weather, the CIWS VIL3+ is used to represent heavy convective weather.

Forecasted movement of the weather and traffic is accounted for when computing the PCA. Pilots typically require greater separation when passing on the downwind side of convection, compared to the upwind side, which is accounted for in the CP metric.

The four factors described above (i.e., reroute complexity, controller workload, route frequency of use, and constraint proximity) are combined to predict the probability of acceptance, for a candidate reroute. The process begins by using field data to determine the relative frequency that a reroute is accepted. This is used as an estimate of the probability of reroute acceptance, P(A). Categories are next created (e.g., low, medium, and high) for each of the four metrics, RC, CW, RF, CP. Field data is again used to determine the relative frequencies of each category, and use these to estimate the probability distribution of each metric, as illustrated in Figure 3 (which shows Notional probability distribution for a single reroute acceptance metric). In particular, Figure 3 shows at 30 that a metric value in a medium range has a higher probability of acceptance as compared to a low range metric value (shown at 32) or a high range metric value (shown at 34).

Similarly, the conditional probabilities, P(i?G | A). P (CW \ A). P (RF \ A) and P (CR \ A) are estimated, where the subscript i denotes the categories of each metric. For example, if a metric has three categories, then three conditional probabilities are computed, indicating the probability for each category of the metric, given that the reroute is accepted. (Note that this is equivalent to re-creating the Figure 3 distribution, but basing it not on all reroutes, but only on reroutes that were accepted).

Given the probability of reroute acceptance, P (A), the probability distribution of each category, and the conditional probabilities, P(RC, | A). P (CW, | A). P (RF, | A) and P (CR, | A). the probability of acceptance, P(A) can now be updated, for a given candidate reroute. In other words, the probability of reroute acceptance from above, P (A), was computed over all reroutes in the field data. The system may now update this estimate for a given candidate reroute, given the value of its four metrics, RC, CW, RF, CP. This may be done using Bayes’ Theorem:

Where M represents the z-th category of reroute acceptance metric M. Equation (7) is repeated for each of the four reroute acceptance metric values. At each iteration, the left-hand side is used as the prior probability in the subsequent iteration. That is, the new P(A) value is set equal to P(A\M,). so P(A \M,) P(A).

When the four iterations are complete, the result is an estimate of the probability of reroute acceptance, P(A). accounting for the four metric values, for that particular reroute candidate. This is a crucial value, and this quantitative, systematic evaluation of it is a new innovation.

The above considered the canonical two-reroute case (i.e., the problem of selecting a strategy when two reroutes are available). The system may make use of those canonical results discussed above, which examine the problem of selecting single, and multiple reroutes, respectively, from a set of N candidate reroutes produced by a tool such as DWR.

As before, in these sections, it is assumed that the user objective is to maximize the expected reroute savings, EfY).

For a given candidate reroute, the expected savings E(S') is the product of the probability of the reroute, and its savings. It is useful to visualize the candidate reroutes, for a given ARTCC, in the probability-savings (P-S) space, as Figure 4A illustrates, which shows a notional diagram of the probability-savings space, with example reroutes r and q. In particular, Figure 4A shows at 40 candidate reroutes distributed by reroute probability, P, and reroute savings, S.

Because the reroute probability factors, discussed above, tend to favor shorter routes, the general trend in the P-S space is reduced savings with increasing probability, as Figure 4B discussed below illustrates. Of course high-savings reroutes, with high probability, are consistently discovered as well.

Before finding the maximum EOS') reroute, it is noted that for the maximum EOS') objective, any reroute in the P-S space which has both a lower probability and a lower savings, relative to any other reroute in the space (such as reroute q in relation to reroute r in Figure 4A), will not be used in the solution. This is because a point with higher probability and higher savings necessarily has a higher EfY).

This suggests the concept of a maximum E(L') frontier, consisting of only those points in the P-S space for which there is no other point with both higher probability and higher savings. This is illustrated in Figure 4B (which shows a notional diagram of the maximum EfY) frontier). In particular, Figure 4B shows at 42 a maximum EfY) frontier 42 that connects points 44 having both higher probability and higher savings of the candidate reroutes 40 of Figure 4A. For the single reroute case, the maximum E(L') is simply the point in the frontier with the maximum product of P and S. Before examining this solution, however, the cost of time is considered.

Thus far it has been assumed that the reroute savings, S. are directly proportional to the reroute flight time reduction. But the true value of S is typically more complicated, depending on the user business case. For example, if a flight is currently 16 minutes delayed, then the first few minutes of delay reduction are far more valuable (in order to move the ETA within the A14 threshold, which refers to the l4-minute arrival delay threshold used by the Department of Transportation to accrue on-time statistics), than additional delay reduction.

On the other hand, if the flight was delayed even more, say 25 minutes, then a large negative delay of 11 minutes would be of disproportionately greater value, than shorter delay reductions which would not reach A14. The A14 threshold is one of many cost components that contribute to the overall cost of delay borne by the operator. Figure 4C (which shows a notional diagram of the cost of flight delay relative to the scheduled flight time) illustrates several other cost components and considerations, and a resulting, notional, cost of delay profile (as a function of delay). In particular, Figure 4C shows at 46 that cost and flight time increase together due to many factors, including (and increasing both cost and delay), fuel dump or orbit, lack of gate availability, actions associated with no labor cost savings, fuel and labor costs, and time delays beyond Department of Transportation (DOT) delays considered on-time (e.g., 14 min).

In addition to the Figure 4C cost components, user business cases can include several other factors that complicate the value of negative delay. For example, the value profile of the delay cost varies substantially between a flight that is inbound to a hub in an arrival rush, and with a short gate turn around, compared to a night flight that is outbound from a hub. Another complicating factor is the number of passengers with short connections, and the presence of VIPs on board a flight.

A cost profile is created, based on scheduling and hub information for the flight. But it allow users to replace it with their own profile. Either way, the system uses the value profile of delay to transform S. of any given candidate reroute, to the user’s true savings, S’, which accounts for the various business case factors. This sometimes will have the effect of making the shorter reroutes with smaller savings more competitive, when a short savings is highly needed. For other flights a larger time savings is needed, so the longer reroutes have inflated savings. In any case, the user objective is assumed to be to maximize the expected value of the transformed savings, E(L' ).

Consider the problem of selecting a single reroute from two candidate reroutes, Ri and R2. RI has a savings of 8 minutes with acceptance probability of 0.5. R2 has a savings of 4 minutes with acceptance probability of 0.75. By Eq. (1), Ri is indicated as it has an expected time savings of 4 minutes whereas R2 has an expected time savings of only 3 minutes.

Now consider this scenario, with a flight which currently is behind schedule by 18 minutes, with a cost of delay setting of $400/minute for the first four minutes of negative delay (achieving A14), and after that $l00/minute of negative delay. Now, from Eq. (1),

E(ri”) for Ri is £(S') = P _a x S_DWR

E(S ') = .5 x (4 x $400 + 4 x $100) = $1,000

On the other hand, EfS") for R2 is

£(S') = .75 x (4 x $400) = $1,200

Therefore, R2 is indicated when the current delay and the cost of delay profile are considered. In this example the reroute with lower EfS) has the higher EfS") by virtue of the scenario specifics.

It is also worth considering the functional example where the E(S’) is linear in the P-S’ space, as illustrated in Figure 4D, which shows a notional diagram of a linear maximum E S’) frontier. In particular, Figure 4D shows at 48 the linear savings frontier regarding reroute probability, P, and reroute savings, S’. For the Figure 4D case, the linear maximum E(S’) frontier can be expressed as:

S' = mP + b (8) where m is the slope and b is the -intercept of the linear function. From Eq. (1), E(S’) is then Eq. (8) multiplied by the abscissa, P, yielding the quadratic:

E{S') = mP ² + bP (9)

To optimize the expected value of the transformed savings, the derivative of Eq. (9) is set to zero, and solved for P:

0 = 2 mP + b (10)

P =—

2m (11)

But when S’ near probability of one (right side of Figure 4D) is small, then m ~ -b, leading to a probability of one-half: 1

P

2 (12)

In other words, for the canonical case of a linear savings frontier leading to a small savings at unity probability, the reroute that maximizes the expected transformed savings has a probability of acceptance of 0.5. In practice, the expected savings may be numerically computed for each frontier point, EfS") = PS’, and the maximum may be chosen.

The above discusses single-reroute selection, but reroutes can be rejected for reasons outlined above. The possibility of rejection raises the question of follow-up reroute requests, such as in the two-reroute approach. The two-reroute approach is attractive because it provides for higher EfS") than the one-reroute approach.

Follow-up reroute requests also support future automated air-ground negotiation capabilities. Below focus on the two-reroute case (see Eq. 5), and accompanying text discusses the /V-reroute case that may occur in automated air-ground negotiation. The above presented the probability of two-route acceptance model. In the two-reroute case, the selection of the first reroute impacts the feasibility and acceptance of the second reroute, depending on the relative timing. Therefore, three time windows are defined: prior, settling and post settling. The prior time is the time prior to the initiation of the first reroute. The settling time is an operational settling time window, after the initiation time of the first reroute. This may be very short. Possibly the biggest factor is related to whether or not the same sector controller has track control of the aircraft. In other words, this is related to a “Hey, I just gave you a short cut” factor. Possibly the settling window has more to do with time to next sector hand-off The post settling time is the time after the operational settling time window.

For a given first reroute, all other reroutes that initiate in the first time window are, obviously, not feasible as candidates for the follow-up, second reroute, in case the first reroute is rejected. For the second time window, the operational settling time is defined as the time period in which a second reroute request is not operationally feasible because insufficient time has passed since the first reroute was rejected (note that the second time window may be relatively short and likely will shift at sector crossings).

Therefore, reroutes that initiate in the second time window are, also, not feasible as candidates for the follow-up, second reroute. Only reroutes that initiate in the third time window are left as feasible candidates for the second reroute. The point here is that the initiation time of the first reroute impacts the set of candidate reroutes available for the second request, if the first request is rejected. Therefore, an otherwise desirable reroute that occurs late in time, may be a sub optimal choice for the first reroute if its late timing eliminates other attractive reroutes from consideration. This raises the general question of how to select the optimal two-reroute pair, which is next considered.

In the two-reroute selection case, given a candidate for the first reroute, for the second reroute the system may immediately eliminate all reroutes that initiate in the prior and settling time windows. After eliminating these unfeasible routes, it follows from Eq. (5) that the optimal second route to select will always be that with the highest EfiV ^' ) of the remaining reroutes. Therefore, using Eq. (5), the combinations that need to be exhaustively tested are every reroute on the savings frontier as the first reroute, followed by the highest EfiV ^' ) reroute of the remaining feasible reroutes, for the second reroute.

Using Eq. (5), the maximum EfV ^' ) gives the optimal two-reroute strategy. Note that the highest EfS") reroute is not necessarily the first reroute in the optimum two-reroute strategy. But if it is not, the first reroute must be temporally prior to the highest EfV ^' ) reroute. Any temporally later reroute, taken as the first reroute of the set, cannot yield the highest expected savings, because it cannot have any superior reroutes as the second of the set, compared to what are available to the highest EfS") reroute. As an example of how the highest EfS' ^' ) reroute may be the second reroute in the optimal two-reroute strategy, consider a temporally early, competitive reroute, that occurs prior to the highest EfV ^' ) reroute, as illustrated in Figure 5, which shows an example of optimum single-reroute as second reroute in optimum two-reroute strategy. In particular, Figure 5 shows an early competitive reroute 50 as well as a maximum expected savings reroute 52 from a set of frontier points 54 of a plurality of candidate reroutes 56. If the candidate reroutes temporally later than the highest EfS") reroute are of low savings, then the optimal two-reroute strategy will consist of the earlier, competitive, reroute followed by the highest EfS") reroute.

In accordance with further embodiments, systematic use of air-ground datalinks may be employed, such as controller-pilot data link communications (CPDLC), which will enhance in-flight rerouting. This will support more complex reroutes, reduced settling time, more reroute requests, and air-ground negotiation protocols. It will allow users to optimize their multiple reroute selection, discussed in this section. At a high-level, the system optimizes the rerouting decision by first ordering the future reroutes chronologically in future time.

For the next, upcoming candidate reroute, the system computes the two expected savings values, for the decisions to request, and not to request, the reroute. If there are ties (i.e., multiple reroutes at the same start time), then the system repeats this process for all of the candidate reroutes in the tie. For each reroute, the system identifies the highest expected savings decision (i.e., which is higher, to request or not to request the reroute?). If no reroute request is indicated across all the candidate reroutes, then the decision is not to request a reroute. Otherwise, of those reroutes indicated, the system selects the highest saving reroute.

To evaluate the request/no request decision for a given candidate reroute, the system employs the following steps. First, identify all reroutes in the upcoming cluster. For the given candidate reroute, the cluster contains all reroutes that (i) initiate at a later time than the candidate reroute initiates, and (ii) overlap temporally with the candidate reroute, or overlap with any reroute in the cluster. This means that the cluster ceases at the future time point containing no reroute (i.e., a gap). Figure 6 (which shows an example timeline of cluster of upcoming candidate reroutes) illustrates the time spans of four reroutes forming a cluster. In particular, Figure 6 shows a first reroute 60 that overlaps in time with a second reroute 62 as well as a third reroute 64. The second reroute 62 overlaps in time with the third reroute 64, and the third reroute 64 overlaps in time with the fourth reroute 66.

The decision to be made is whether or not to request the Rl reroute. To compute the expected savings of these two options, the system next constructs a probabilistic binary decision tree, shown in Figure 7, which shows probabilistic binary decision tree for candidate reroute Rl.“Y” and“N” indicate reroutes that are or are not flown, respectively. In particular, Figure 7 shows at 70 a probabilistic binary decision tree for candidate reroute Rl, as binary decisions (Yes/No) may be made at consecutive levels regarding reroute R2, reroute R3 and reroute R4. The Figure 7 probabilistic binary decision tree contains every possible set of rerouting events in the upcoming cluster. The cluster contains four possible reroutes, so in the binary tree there are a total of 2 ⁴ , or 16, total reroute sequences, or paths through the tree.

Not all of the paths, however, are feasible. A path is infeasible if a reroute initiation time point overlaps into an on-going reroute. For example, from Figure 6, reroute R2 cannot be flown if reroute Rl is flown. Figure 8 (which shows probabilistic binary decision tree for candidate reroute Rl, with infeasible paths blocked out) shows the infeasible portions of the decision tree blocked out. In particular, Figure 8 shows that certain paths of the decision tree 70 of Figure 7 are not feasible options (such as shown at 80, 82, 84, 86 in Figure 8) given constraints such as timing. The blocked out portions of the Figure 8 decision tree follow directly from the Figure 6 timeline. For example, R2 overlaps with Rl, so therefore if Rl is flown, then R2 cannot be flown (as shown blocked at 80). Similarly, R3 overlaps with Rl, so if Rl is flown, then R3 also cannot be flown (as shown blocked at 84), even if R2 is not flown. By the same logic, R3 cannot be flown if R2 is flown (as shown blocked at 82), and R4 cannot be flown if R3 is flown (as shown blocked at 86). Thus the determination of which portions of the tree are infeasible is straightforward.

Given the Figure 8 designations of the infeasible portions, those portions may be removed, and the resulting nodes without a decision, leaving a fully feasible decision tree, as shown in Figure 9, which shows fully-feasible, one-sided, probabilistic binary decision tree for requesting Rl. In particular, Figure 9 shows at 90 a probabilistic binary decision tree for candidate reroutes in which all routes are possible. Note that Figure 9 lists, at the bottom, the reroute sequences, for each path.

The probability of acceptance in determined next, from above, for each candidate reroute. These probabilities may be attached to each node in the tree, thus making it a probabilistic tree. For example, if reroute Rl is requested, its probability of acceptance indicates the probability of the“Y” branch. One minus this probability gives the probability of the“N” branch. In this way, each segment in the tree has an associated probability.

The probabilities, however, are contingent on the reroute requests. That is, if a reroute is requested, then the probabilities of the“Y” and“N” branches are assigned as described in the above paragraph. But if a reroute is not requested, then the probabilities of the“Y” and“N” branches are 0.0 and 1.0, respectively. Therefore, the tree is a one-sided, probabilistic binary decision tree. For example, if it is decided not to request Rl, then the tree is reduced, as shown in Figure 10, which shows at 100 a fully feasible, one-sided, probabilistic binary decision tree for not requesting Rl. The expected savings may next be computed for the decision to request Rl, and the decision not to request Rl. This amounts to computing the expected savings for the Figure 9 and 10 trees, respectively, in the example.

In order to make these computations, the system needs to determine whether or not R2, R3, and R4 are requested, when those nodes in the tree are reached. For the final node in the tree (the R4 node in the example), the expected savings is always higher when the reroute is requested (i.e., there is no tradeoff). But for the earlier, interior, nodes (the R2 and R3 nodes in our example), the system will exhaust all the possible combinations of decisions, and find the sequence of decisions leading to the highest expected savings.

Figure 11 (which shows at 110 expected savings calculations for decisions to request, and not to request, Rl) illustrates these computations for the Rl reroute decision. The top half of Figure 11 computes the expected savings corresponding to the decision to request Rl (i.e., corresponding to the Figure 9 tree). The bottom half of Figure 11 computes the expected savings corresponding to the decision not to request Rl (i.e., corresponding to the Figure 10 tree). In this Figure 11 example calculation, it is assumed the R2 and R3 reroutes are requested when the system reaches those nodes.

In the Figure 11 calculation, for each sequence (or path), the overall probability is computed by computing the product of the respective probabilities of the branches in the pathway. This overall probability, for each sequence or path, is listed in the middle of the figure, in the“Path” column. Hypothetical probabilities and savings (in minutes, but this could be transformed to dollars without loss of generality), for each candidate reroute, are listed at the top of the figure.

The system next computes the expected savings of each pathway by summing the savings of each reroute in the pathway, and multiplying the sum by the probability of the pathway. Finally the expected savings of the decision to request is computed, and not to request, Rl, by summing the expected savings of each pathway. As Figure 11 shows, in this example scenario, with the given probabilities and savings of each branch, the expected savings for the decision to request Rl is slightly higher (9.44 minutes) than not to request it (8.74 minutes), even though the savings of Rl is significantly lower than R3 (5 compared to 12).

As noted above, these calculations are based on the assumption that the R2 and R3 reroutes are requested when the system reaches those nodes. In order to exhaust all possible decision opportunities, the system would need to compute the expected savings under all possible R2 and R3 decision combinations: (A) R2 and R3 are requested; (B) R2 is requested and R3 is not requested; (C) R2 is not requested and R3 is requested; and (D) R2 and R3 reroutes are both not requested.

In this way, all possible decision strategies are included in the Rl decision. These four decision combinations (A, B, C, and D) are illustrated in Figures 12A - 12D, which shows the four decision combinations that need to be evaluated. Figure 9, and the Figure 10 calculations, correspond to Figure 12A.

The Figure 11 calculation is repeated for the Figure 12B, 12C, and 12D decision strategies as shown at 120, 122, 124 and 126 respectively. This results in four expected savings values for the decision to request Rl, and four expected savings values for the decision not to request Rl. In order to decide whether or not to request Rl, the system compares the maximum expected savings value, from each set of four values. The highest value determines the decision.

The methods presented herein support the optimization of reroute selection for a given flight. The optimal rerouting decision strategy may involve several reroute requests, and the specific sequence of requests, in general, will depend on whether or not the requests are accepted by ATC. Therefore, the strategy evolves in real-time. Furthermore, the underlying calculations, such as the probability of reroute acceptance, evolve in real-time. Such a dynamic, real-time, decision making process is particularly well supported by the emerging air-ground datalink capability, slated for implementation in the NAS in the coming years.

One such example technology is CPDLC (controller-pilot data link communications).

CPDLC will enhance in-flight rerouting. It will support more complex reroutes, reduced settling time, more reroute requests, and air-ground negotiation protocols. It will allow users to optimize their multiple reroute selection, discussed in this section. These methods are summarized in the following list: (1) identify upcoming reroutes, including the earliest possible reroute, Rl, and (2) identify the cluster of reroutes, associated with Rl (which identifies all the reroutes that must be considered, in determining whether or not to request Rl and in determining this decision, all other, later candidate reroutes, outside of the cluster, can be disregarded without loss of opportunity), (3) construct a binary decision tree, containing 2 ^N total reroute sequences, or paths, in the decision tree, where N is the number of candidate reroutes in the cluster, (4) identify and eliminate infeasible paths, where the sequence of reroutes is not possible due to timing overlaps, (5) given the binary decision tree consisting of feasible paths, identify all combinations of reroute decisions, (6) compute the probability of acceptance of each candidate reroute, (7) for each combination of reroute decisions, construct a probabilistic binary decision tree, (8) for each probabilistic binary decision tree, identify each possible path, or sequence of reroutes, through the tree, (9) for each path, compute the probability and expected savings, (10) for each probabilistic binary decision tree, divide the possible paths into two categories: those corresponding to requesting Rl, and those corresponding to not requesting Rl, (11) for each probabilistic binary decision tree, compute the overall expected savings corresponding to requesting Rl, and

corresponding to not requesting Rl, and (12) identify the maximum savings cases corresponding to requesting Rl, and corresponding to not requesting Rl. If the higher of these two values corresponds to requesting Rl, then this is the recommended decision, regarding Rl. Otherwise, the recommended decision is not to request Rl.

Further, the reroute decision problem for users with multiple flights in an ARTCC, and the problem of the problem of savings distribution between time and fuel, may be reviewed as follows. Airlines with multiple flights in an ARTCC face a potentially more complicated rerouting decision. This is because the rerouting decisions for different flights may not be independent, but instead may affect each other. For example, the rerouting of one flight may impact the controller workload, and therefore the probability of acceptance, of a rerouting request by a second flight.

Therefore, to optimize the savings across the fleet of aircraft in an ARTCC, user organizations such as airlines need to consider all possible combinations of reroutes across multiple flights. This is done by expanding the cluster (as discussed above) to include all flights in the ARTCC. The procedure is similar to that described above, except that single reroutes from different flights can overlap (i.e., they can occur simultaneously).

As described above, the reroute decision making strategy developed here assumes the user objective is to maximize the expected reroute savings, E(L'). This, however, leaves unanswered the question of how to distribute the savings between time and fuel. That is, a reroute that nominally saves flight time (by virtue of reducing the distance flown and/or reducing the head wind) can be used to save fuel rather than time via a speed reduction. This may be desirable if the time savings are of less value than the corresponding fuel savings available. Figure 4C illustrates how the value of time savings can vary with how the ETA (estimated time of arrival) compares with the original STA (scheduled time of arrival).

Those skilled in the art will appreciate that numerous modifications and variations may be made to the above disclosed embodiments without departing from the spirit and scope of the present invention. What is claimed is: