Description:FORM 2

THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003

COMPLETE SPECIFICATION
(See Section 10 and Rule 13)

Title of invention:

OPTIMAL ASSIGNMENT OF ARRIVAL SLOTS AT AIRPORT BY MINIMIZING ENVIRONMENTAL IMPACT OF ARRIVING AIRCRAFT

Applicant

Tata Consultancy Services Limited
A company Incorporated in India under the Companies Act, 1956
Having address:
Nirmal Building, 9th floor,
Nariman point, Mumbai 400021,
Maharashtra, India

Preamble to the description:
The following specification particularly describes the invention and the manner in which it is to be performed.
TECHNICAL FIELD
The disclosure herein generally relates to the field of aircraft arrival management, and, more particularly, to optimal assignment of arrival slots at airport by minimizing environmental impact of arriving aircraft.
BACKGROUND
Minimization of carbon footprint of aviation is an active area of interest to industry and policy makers alike. A major proportion of this footprint is derived from routine operation of aircraft and can be reduced using a combination of scheduling and flight path optimization. Optimization of individual phases of a flight is an important step in that direction. Conventional methods to tactical scheduling the arrival of aircraft usually involve a combination of heuristics often based around queue-theoretic analysis or optimization techniques based on integer programming. A decision to allocate landing slots is taken by directly computing target landing times that satisfy necessary inter-aircraft separation constraints. This requires modeling and optimizing mean arrival rates in an airspace using an underlying stochastic model for arrival process, or by managing holding times for individual aircraft whose arrival into the terminal airspace is modeled as a single queue. The objective of allocation could be to either minimize a deviation from desired times of arrival or minimizes metrics such as the arrival time of last aircraft.
Traditionally, aircraft arrival scheduling is performed based on air traffic controller (ATC) allocating landing slots or arrival slots manually. While the ATC usually ensures fairness by following a first-in-first-out (FIFO) logic, same logic may not be environmentally optimal. However, an environmentally optimal allocation can be perceived as unfair, particularly to airlines that operate environmentally friendlier aircraft which might be required to hold longer than they would under a fair first-come-first-served policy. Thus, there is a need to maintain a balance between the environmentally optimal allocation and ensuring fairness.
SUMMARY
Embodiments of the present disclosure present technological improvements as solutions to one or more of the above-mentioned technical problems recognized by the inventors in conventional systems. For example, in one embodiment, a processor implemented method is provided. The processor implemented method, comprising receiving, via one or more hardware processors, a plurality of input data pertaining to an aviation system, wherein the plurality of input data comprises (i) a plurality of data pertaining to at least one aircraft from a plurality of aircraft in a holding pattern for a specific airport, (ii) a plurality of arrival slots for an arrival runway of the specified airport, and (iii) a signal from a planning trigger equipped with a timestamp; computing, via the one or more hardware processors, a set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft using the plurality of input data when the signal is received from the planning trigger; computing, via the one or more hardware processors, a value matrix for the set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft, wherein each entry of the computed value matrix is indicative of an amount of fuel consumed by a specific aircraft assigned to a specific slot; determining, via the one or more hardware processors, (i) an optimal assignment from the set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft based on the computed value matrix and (ii) an associative non-negative reward for the optimal assignment of the plurality of arrival slots for each aircraft from the plurality of aircraft; and updating, via the one or more hardware processors, the timestamp for the planning trigger based on a number of aircrafts that have been assigned an arrival slot from the plurality of arrival slots in accordance with the optimal assignment.
In another aspect, a system is provided. The system comprising a memory storing instructions; one or more communication interfaces; and one or more hardware processors coupled to the memory via the one or more communication interfaces, wherein the one or more hardware processors are configured by the instructions to: receive a plurality of input data pertaining to an aviation system, wherein the plurality of input data comprises (i) a plurality of data pertaining to at least one aircraft from a plurality of aircraft in a holding pattern for a specific airport, (ii) a plurality of arrival slots for an arrival runway of the specified airport, and (iii) a signal from a planning trigger equipped with a timestamp; compute a set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft using the plurality of input data when the signal is received from the planning trigger; compute a value matrix for the set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft, wherein each entry of the computed value matrix is indicative of an amount of fuel consumed by a specific aircraft assigned to a specific slot; determine (i) an optimal assignment from the set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft based on the computed value matrix and (ii) an associative non-negative reward for the optimal assignment of the plurality of arrival slots for each aircraft from the plurality of aircraft; and update the timestamp for the planning trigger based on a number of aircrafts that have been assigned an arrival slot from the plurality of arrival slots in accordance with the optimal assignment.
In yet another aspect, a non-transitory computer readable medium is provided. The non-transitory computer readable medium are configured by instructions for receiving, a plurality of input data pertaining to an aviation system, wherein the plurality of input data comprises (i) a plurality of data pertaining to at least one aircraft from a plurality of aircraft in a holding pattern for a specific airport, (ii) a plurality of arrival slots for an arrival runway of the specified airport, and (iii) a signal from a planning trigger equipped with a timestamp; computing, a set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft using the plurality of input data when the signal is received from the planning trigger; computing, a value matrix for the set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft, wherein each entry of the computed value matrix is indicative of an amount of fuel consumed by a specific aircraft assigned to a specific slot; determining, (i) an optimal assignment from the set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft based on the computed value matrix and (ii) an associative non-negative reward for the optimal assignment of the plurality of arrival slots for each aircraft from the plurality of aircraft; and updating, the timestamp for the planning trigger based on a number of aircrafts that have been assigned an arrival slot from the plurality of arrival slots in accordance with the optimal assignment.
In accordance with an embodiment of the present disclosure, the plurality of arrival slots are indicative of a plurality of time instants at which at most one aircraft from the plurality of aircraft in the holding pattern arrives at a predefined point at a specific distance and a specific altitude along a center line of the arrival runway of the specified airport.
In accordance with an embodiment of the present disclosure, the predefined point represents a final approach fix (FAF) for the arrival runway.
In accordance with an embodiment of the present disclosure, the optimal assignment ensures minimizing net environmental impact of the plurality of aircraft in the holding pattern.
In accordance with an embodiment of the present disclosure, the associative non-negative reward for an aircraft is determined in terms of a linear programming problem (LPP) by comparing a value indicating sum of total holding time of the aircraft and time taken by the aircraft to fly to the FAF with a baseline value.
In accordance with an embodiment of the present disclosure, the associative non-negative reward is provided to maintain a fair allocation of the plurality of arrival slots to a set of environment friendly aircraft from the plurality of aircraft in terms of at least one of (i) a reduction in airport landing fees, and (ii) an equivalent carbon credit.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed.
BRIEF DESCRIPTION OF THE DRAWINGS
The accompanying drawings, which are incorporated in and constitute a part of this disclosure, illustrate exemplary embodiments and, together with the description, serve to explain the disclosed principles:
FIG. 1 illustrates an exemplary system for optimal assignment of arrival slots at airport by minimizing environmental impact of arriving aircraft, according to some embodiments of the present disclosure.
FIG. 2 is a functional block diagram for optimal assignment of arrival slots at airport by minimizing environmental impact of arriving aircraft, using the system of FIG. 1, according to some embodiments of the present disclosure.
FIG. 3 illustrates an exemplary flow diagram illustrating a method for optimal assignment of arrival slots at airport by minimizing environmental impact of arriving aircraft, using the system of FIG. 1, in accordance with some embodiments of the present disclosure.
FIG. 4 shows a diagram illustrating arrival phases of an arriving aircraft at an airport, in accordance with some embodiments of the present disclosure.
DETAILED DESCRIPTION OF EMBODIMENTS
Exemplary embodiments are described with reference to the accompanying drawings. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. Wherever convenient, the same reference numbers are used throughout the drawings to refer to the same or like parts. While examples and features of disclosed principles are described herein, modifications, adaptations, and other implementations are possible without departing from the scope of the disclosed embodiments. It is intended that the following detailed description be considered as exemplary only, with the true scope being indicated by the following embodiments described herein.
It is well known that aviation contributes significantly to the world’s carbon footprint, accounting for 2.5-3% of the total CO2 emissions. A major proportion of this carbon footprint is derived from routine operation of aircraft and can be reduced using a combination of scheduling and flight path optimization. A typical flight can be broken down into representative segments such as climb, cruise, hold, an/or the like, each with its characteristic thrust requirement and consequent emissions profile. Of these, the environmental impact of the climb and the cruise is the greatest due to the high thrust requirement. The pre-arrival hold phase requires a relatively high thrust setting, comparable to cruise, because of low descent rates. The time spent in hold by an aircraft depends significantly on the traffic and number of runways available for handling arrivals. As a result, when the traffic is heavy and average holding times are high, it would be environmentally beneficial to manage the holding time of aircraft as a function of their environmental footprint rather than following a fair first-come-first-served policy or heuristics that directly minimize the average holding time. At the same time, a policy that appears unfair to airlines that operate environmentally friendly aircraft needs to be supported by a fair economic reward.
The present disclosure addresses the unresolved problems of the conventional approaches by determining an environmentally-optimal holding policy and an economic reward concurrently. Embodiments of the present disclosure provide a method and system for optimal assignment of arrival slots at airport by minimizing environmental impact of arriving aircraft. In other words, the present disclosure provides a tactical landing slot allocation method for minimizing the environmental impact of aircraft when they are required to hold in the terminal airspace. Net environmental impact of holds can be determined by summing over the impact of individual aircraft which depends on aircraft type, its engines, as well as its weight. As a result, if a certain number of aircraft arrive at a holding location, it is desirable to allow older, heavier aircraft with a larger environmental footprint to exit the queue before newer aircraft. This requirement conflicts with operational requirements and fairness, in the sense that airlines would prefer that their aircraft be allowed to land in their order of arrival into a terminal airspace. In order to restore fairness, the method of the present disclosure includes a calculation of an economic cost of holding, and particularly that of additional amount of time an environmentally-friendly aircraft might be required to hold. By presenting an economic reward, apparent unfairness of an environmentally optimal scheme can be mitigated, bringing its fairness on par with typical baseline schemes used by the air traffic control.
Referring now to the drawings, and more particularly to FIGS. 1 through 4, where similar reference characters denote corresponding features consistently throughout the figures, there are shown preferred embodiments and these embodiments are described in the context of the following exemplary system and/or method.
FIG. 1 illustrates an exemplary system for optimal assignment of arrival slots at airport by minimizing environmental impact of arriving aircraft according to some embodiments of the present disclosure. In an embodiment, the system 100 includes or is otherwise in communication with one or more hardware processors 104, communication interface device(s) or input/output (I/O) interface(s) 106, and one or more data storage devices or memory 102 operatively coupled to the one or more hardware processors 104. The one or more hardware processors 104, the memory 102, and the I/O interface(s) 106 may be coupled to a system bus 108 or a similar mechanism.
The I/O interface(s) 106 may include a variety of software and hardware interfaces, for example, a web interface, a graphical user interface, and the like. The I/O interface(s) 106 may include a variety of software and hardware interfaces, for example, interfaces for peripheral device(s), such as a keyboard, a mouse, an external memory, a plurality of sensor devices, a printer and the like. Further, the I/O interface(s) 106 may enable the system 100 to communicate with other devices, such as web servers and external databases.
The I/O interface(s) 106 can facilitate multiple communications within a wide variety of networks and protocol types, including wired networks, for example, local area network (LAN), cable, etc., and wireless networks, such as Wireless LAN (WLAN), cellular, or satellite. For the purpose, the I/O interface(s) 106 may include one or more ports for connecting a number of computing systems with one another or to another server computer. Further, the I/O interface(s) 106 may include one or more ports for connecting a number of devices to one another or to another server.
The one or more hardware processors 104 may be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, state machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the one or more hardware processors 104 are configured to fetch and execute computer-readable instructions stored in the memory 102. In the context of the present disclosure, the expressions ‘processors’ and ‘hardware processors’ may be used interchangeably. In an embodiment, the system 100 can be implemented in a variety of computing systems, such as laptop computers, portable computer, notebooks, hand-held devices, workstations, mainframe computers, servers, a network cloud and the like.
The memory 102 may include any computer-readable medium known in the art including, for example, volatile memory, such as static random access memory (SRAM) and dynamic random access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes. In an embodiment, the memory 102 includes a plurality of modules 102a and a repository 102b for storing data processed, received, and generated by one or more of the plurality of modules 102a. The plurality of modules 102a may include routines, programs, objects, components, data structures, and so on, which perform particular tasks or implement particular abstract data types.
The plurality of modules 102a may include programs or computer-readable instructions or coded instructions that supplement applications or functions performed by the system 100. The plurality of modules 102a may also be used as, signal processor(s), state machine(s), logic circuitries, and/or any other device or component that manipulates signals based on operational instructions. Further, the plurality of modules 102a can be used by hardware, by computer-readable instructions executed by the one or more hardware processors 104, or by a combination thereof. Further, the memory 102 may include information pertaining to input(s)/output(s) of each step performed by the processor(s) 104 of the system 100 and methods of the present disclosure.
The repository 102b may include a database or a data engine. Further, the repository 102b amongst other things, may serve as a database or includes a plurality of databases for storing the data that is processed, received, or generated as a result of the execution of the plurality of modules 102a. Although the repository 102b is shown internal to the system 100, it will be noted that, in alternate embodiments, the repository 102b can also be implemented external to the system 100, where the repository 102b may be stored within an external database (not shown in FIG. 1) communicatively coupled to the system 100. The data contained within such external database may be periodically updated. For example, new data may be added into the external database and/or existing data may be modified and/or non-useful data may be deleted from the external database. In one example, the data may be stored in an external system, such as a Lightweight Directory Access Protocol (LDAP) directory and a Relational Database Management System (RDBMS). In another embodiment, the data stored in the repository 102b may be distributed between the system 100 and the external database.
FIG. 2, with reference to FIG. 1, is a functional block diagram for optimal assignment of arrival slots at airport by minimizing environmental impact of arriving aircraft, using the system of FIG. 1, according to some embodiments of the present disclosure.
FIG. 3, with reference to FIGS. 1 and 2, illustrates an exemplary flow diagram illustrating a method for optimal assignment of arrival slots at airport by minimizing environmental impact of arriving aircraft, using the system of FIG. 1, in accordance with some embodiments of the present disclosure.
Referring to FIG. 3, in an embodiment, the system(s) 100 comprises one or more data storage devices or the memory 102 operatively coupled to the one or more hardware processors 104 and is configured to store instructions for execution of steps of the method by the one or more processors 104. The steps of the method 200 of the present disclosure will now be explained with reference to components of the system 100 of FIG. 1, the block diagram of FIG. 2, the flow diagram as depicted in FIG. 3, and one or more examples. Although steps of the method 200 including process steps, method steps, techniques or the like may be described in a sequential order, such processes, methods and techniques may be configured to work in alternate orders. In other words, any sequence or order of steps that may be described does not necessarily indicate a requirement that the steps be performed in that order. The steps of processes described herein may be performed in any practical order. Further, some steps may be performed simultaneously, or some steps may be performed alone or independently.
In an embodiment, at step 202 of the present disclosure, one or more hardware processors are configured to receive a plurality of input data pertaining to an aviation system. As shown in FIG. 2, the plurality of input data comprises (i) a plurality of data pertaining to at least one aircraft from a plurality of aircraft in a holding pattern for a specific airport, (ii) a plurality of arrival slots for an arrival runway of the specified airport, and (iii) a signal from a planning trigger equipped with a timestamp. In the context of present disclosure, the expressions ‘aircraft’, and ‘flight’ can be interchangeably used throughout the description. Similarly, the expressions ‘arrival slots’ and ‘landing slots’, and ‘slots’ can be interchangeably used. The holding pattern involves flying one or more circuits around well-defined individual way points while holding or reducing altitude in prescribed steps. The plurality of data pertaining to the at least one aircraft from the plurality of aircraft in the holding pattern for the specific airport may include but not limited to scheduled time of arrival of the plurality of aircraft which is prior known to the ATC at the time of the aircraft’s departure, information on aircraft manufacturing (e.g., engine type) which is relayed to the arrival ATC at the time of the aircraft’s departure and also broadcast by the Automatic Dependent Surveillance–Broadcast (ADS-B), weight of aircraft which is provided to the ATC by aircraft pilot at the time of arrival, one or more arrival constraints, Lift-to-drag ratio and Thrust-specific fuel consumption (TSFC) of the engine. The one or more arrival constraints may include but not limited to emergency, speed constraints, or latest arrival time without incurring late arrival cost. The one or more arrival constraints are advised by the aircraft pilot upon entry into an arriving airport’s airspace. The Lift-to-drag ratio and Thrust-specific fuel consumption (TSFC) of the engine are obtained from original equipment manufacturer (OEM) data. In an embodiment, the plurality of arrival slots are indicative of a plurality of time instants at which at most one aircraft from the plurality of aircraft in the holding pattern arrives at a predefined point at a specific distance and a specific altitude along a center line of the arrival runway of the specified airport. The predefined point represents a final approach fix (FAF) for the arrival runway. In other words, the arrival slot refers to a time window of a specified duration about a specified instant in time, or a specific instant of time. The plurality of arrival slots are either provided by the air traffic control or the system 100 defines them arbitrarily via time stamps of a form hh:mm:ss (i.e., each slot is a minute apart). In an embodiment, there are two sets of planning triggers including an internal trigger used typically after fixed intervals of time and external triggers including (i) unforeseen events; (ii) a new aircraft entering an empty holding pattern, and a (iii) manual trigger by the ATC.
FIG. 4 shows a diagram illustrating arrival phases of an arriving aircraft at an airport, in accordance with some embodiments of the present disclosure. As shown in FIG. 4, the arrival of an aircraft consists of four phases including descent from cruising altitude, pre-approach hold (if applicable), final approach, and touchdown. When traffic is sparse, it is possible to bypass the pre-approach hold altogether and proceed to the final approach which starts at the final approach fix (FAF). The number of aircraft that can enter the final approach corridor during a given time window is constrained by a necessity to ensure appropriate inter-aircraft separation (IAS). Minimum permissible inter-aircraft separation depends on the relative size of two aircraft, weather, visibility on the ground, and ground movement constraints at the specific airport. The pre-approach hold is used to regulate the flow of aircraft into the final approach corridor when the number of aircraft arriving in the terminal airspace exceeds the rate at which aircraft can enter the final approach. A holding area also referred to as a holding stack (also referred as stack) is shown in FIG.4. Each holding stack consists of a series of closed paths separated by constant altitude. Each aircraft in the holing stack is allocated a fixed altitude. There are multiple such stacks that service any given arrival runway. There are two types of path from any given stack to the FAF. A direct path is a shortest path from the stack to the FAF, and involves a steep descent with the minimal thrust setting. An alternative is a longer waypoint (WP) path, wherein the aircraft flies over a series of prescribed waypoints or through a prescribed combination of distances, turns, and bearings. The waypoint indicates a geographical point on the ground with a prescribed latitude and longitude. Since the aircraft’s descent rate is relatively smaller in magnitude along the waypoint path, the thrust required to fly the waypoint path is higher than the direct path.
At step 204 of the present disclosure, the one or more hardware processors are configured to compute a set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft using the plurality of input data when the signal is received from the planning trigger. The set of feasible assignments refers to an assignment of each aircraft from the plurality of aircraft, where each aircraft is assigned to at most one feasible arrival slot from the plurality of arrival slots, and no arrival slot from the plurality of arrival slots is assigned to more than one aircraft from the plurality of aircrafts. Further, at step 206 of the present disclosure, the one or more hardware processors are configured to compute a value matrix for the set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft. Each entry of the computed value matrix is indicative of an amount of fuel consumed by a specific aircraft assigned to a specific slot.
In an embodiment, the amount of fuel consumption or rate of fuel consumption of a jet aircraft is given by equation (1) below as:
(m_f ) ?=?_T T (1)
Here, ?_T is called the thrust-specific fuel consumption (TSFC) and T is the net thrust produced by the engines. The TSFC is engine-specific while T depends on the weight W and the flight profile of the aircraft as provide in equation (2) below:
T = W(sin? + C_D/C_L cos ?) (2)
Here, C_D/C_L is the lift-to-drag ratio, a measure of the aerodynamic efficiency of the airframe, and ? is a flight path angle defined as ?=tan^(-1)??dz/dl?, where z is the altitude of the aircraft and l denotes a path coordinate in horizontal plane. Combining the equations (1) and (2), the rate of fuel consumption of the jet aircraft is given by equation (3) below as:
(m_f ) ?=?_T W(sin? + C_D/C_L cos ?) (3)
Assuming that the carbon footprint of an aircraft is proportional to (m_f ) ?, it is clear that the carbon footprint is decided by characteristics of the airframe and the engine via C_D/C_L and ?_T, respectively. Aircraft typically hold and approach at speeds between 70% and 90% of the minimum-drag flight speed, so that the corresponding value of C_D/C_L is approximately 0.9(C_D/C_L )_max. Table 1 provides a few examples that illustrate typical values of C_D/C_L , TSFC, and the ratio (m_f ) ?/W calculated using (3) with ? = -0.02 rad (approximately -1.2 deg). MLW stands for maximum landing weight.
Aircraft Maiden flight [year] Typical # passengers (L/D)_max ?_T
[Kg/s] (m_f ) ?/W
[106 N] MLW
[106 N] (m_f ) ? at MLW
[Kg/s]
Airbus A320-200 1987 160 16.3 9.4 0.407 0.66 0.269
Boeing 747-400 1988 380 15.5 9.4 0.437 2.7 1.18
Airbus A330-300 1992 280 18.1 9.0 0.335 1.93 0.627
Boeing 777-200ER 1996 300 19.3 8.16 0.276 2.13 0.588
Boeing 787-9 2013 270 20.5 7.95 0.244 1.93 0.472
Table 1
In an embodiment, queuing dynamics in the holding stack is described. To understand the queuing dynamics in the holding stack, an airport which is served by N holding areas (or stacks) h_1,...,h_N is considered. Let q_i [k] denote the number of aircraft that would enter the stack at time instant k. For each aircraft j in the stack, states are associated as shown in equation (4) below:
s_j [k] = (id,t_j^h [k],z_j [k],u_j [k],v_j [k]) (4)
Here, id refers to a unique identifier assigned to the aircraft, z_j [k] denotes the aircraft’s altitude, and t_j^h [k] denotes total time spent in the holding stack until time k. The governing equations for t_j^h and z_j are given by equation (5) below:
t_j^h [k+1]={¦(t_j^h [k]+1 aircraft in hold@t_j^h [k] aircraft released from hold)¦
z_j [k+1]={¦(z_j [k] holding stack at z_j [k]-?z unavailable and? u?_j [k]= v_j [k]=0 @z_j [k]-?z aircraft released from hold)¦
u_j [k]={¦( 1 aircraft released from hold via WP path at k@0 otherwise)¦ (5)
v_j [k]={¦( 1 aircraft released from hold via direct path at k@0 otherwise)¦
Here, ?z denotes a difference between successive altitude levels in the holding stack. Furthermore, there typically exist altitude thresholds z^u and z^v such that u_j [k]=0 necessarily if z_j [k]> z^u and likewise for v_j [k]. Let x_i [k] denote the number of aircraft in stack h_i at time k. Then, equation (6) below shows:
0=x_i [k+1]=x_i [k]+q_i [k]-?_(j?h_i)¦(u_j [k]+v_j [k]) (6)
Let t_i^c and t_i^w denote the time to reach the FAF from the holding area i along direct and WP paths, respectively. To ensure that at most one aircraft can arrive at the FAF at an instant k, equation (7) below shows:
?_(h_i)¦?_(j?h_i)¦(u_j [k-t_i^c ]+v_j [k-t_i^w]) =1 (7)
Equations (5), (6) and (7) completely describe the dynamics of the queue in the holding stack. the number of aircraft entering the stack at time k. For the purpose of simulation in the present disclosure, q_i [k], the number of aircraft entering the stack at time k is prescribed as shown in equation (8) below:
q_i [k]~ Poisson(?[i,k]) (8)
Here, the arrival rate ? is time-varying and not identical for all stacks.
The objective of the air traffic control policy for managing the queues is as follows:
1. Minimize the total amount of fuel burned by the aircraft during the time that it holds in the stack and then when it flies to the FAF. it is noted that an aircraft may have two routing options between the stack and the FAF.
2. Minimize net time spent by the aircraft between a point of entry into the stack and arrival at the FAF. The net holding time represents routine operational metrics (e.g., on-time arrival statistics or time available for passengers transferring to onward flights) rather than fuel burn.
It is evident from Table 1 how these two objectives can be contrary to each other. As an example, a case is considered where a fully loaded Boeing 747 arrives at a stack just after a fully loaded Boeing 777. While a fair holding policy would prioritize the Boeing 777, an emissions-minimizing policy would prioritize the Boeing 747 since its fuel burn rate is just over twice as that of the Boeing 777.
As shown in equation (4), t_j^h [k] denotes a cumulative time for which an aircraft j has been in hold in a stack at a time instant k. Let f_j^h [k] denote the cost of holding an aircraft j for another instant (i.e., up to time k +1), calculated using (3) in terms of the fuel consumption. Let f_j^f [k] denote the cost of flying the aircraft to the FAF if it were released at time instant k, also calculated using (3). It is noted that the cost would depend on whether the aircraft opts for a CDA or a WPF path. For completeness, it is observed that an operational cost of holding, independent of the fuel consumption and dependent on the cumulative delay, can be defined as f_j^o [k]?f^0 (t_j^h [k] ). For brevity, let u[0: T] denote the vector [u_1 [0],...,u_h [0],u_1 [1],...,u_h [1],...,u_1 [T],...,u_h [T]], and likewise for v[0: T]. The optimal control problem (OCP) of interest is provided in equation (9) below:
min-(u[0:T],v[0:T] )??_(k=0)^T¦?_j¦(f_j^h [k]+f_j^f [k]+f_j^o [k]) (9)
subject to the dynamics (5), (6) and (7). Here T is the terminal time. It is noted that the set of aircraft is not fixed at time t = 0; rather, it time-varying. Thus, ?_j needs to be carried out over all aircraft that arrive at the holding areas during the time window [0,T].
Referring to FIG. 2, at step 208 of the present disclosure, the one or more hardware processors are configured to determine (i) an optimal assignment from the set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft based on the computed value matrix and (ii) an associative non-negative reward for the optimal assignment of the plurality of arrival slots for each aircraft from the plurality of aircraft. The optimal assignment ensures minimizing net environmental impact of the plurality of aircraft in the holding pattern.
The steps 202 through 208 are further better understood by way of following description provided as an exemplary explanation.
In a general assignment algorithm, an ordered set O of m > 0 objects is considered and these object are supposed to be allocated to n individuals in a set I such that every individual gets at most one object. Since O is ordered, elements of O are labeled as 1,...m, where magnitude of label is consistent with an underlying order. Let a = [a_1,...,a_m]? ?N ?_Ø^m?(N?{Ø})^m denote vector of assignments; i.e., a_j= i implies that j ? O has been assigned to i?I , and a_j=Ø implies that the object is unassigned. For each individual i, let the set of feasible assignments (i,j) be captured by a vector F_i? R^m, where F_ij=1 if (i,j) is feasible and F_ij=0. With each individual i ? I , a variable (property) t_i^lim> 0 (possibly infinite) is associated. Likewise, for each object j ? O, a variable t_j^stamp> 0 is associated which satisfies, additionally, t_j^stamp> t_k^stamp if j > k. In the context of the present disclosure, these variables stand for, an upper limit on an aircraft’s holding time and time stamp of an arrival slot measured at the FAF respectively.
There is an assumption necessary for the assignment problem, defined presently, to be well-posed which says that for all j=m, cardinality card{i | t_i^lim= t_j^stamp }= j. For assignment, an individual i?I associates a value of V_ij?R with every object j?O. Furthermore, V_ij= -8 if F_ij= 0. In an embodiment, the general assignment problem is stated as follows: determine the assignment a^*??N ?_Ø^m such that the following objectives are met:
Feasibility: a_j^*=i only if F_ij=1
Mandatory assignment requirements (MARs) are met: for each i^'?I satisfying t_(i^')^lim=t_m^stamp , there exists a unique j^'satisfying F_(i^' j^' ) = 1, t_(j^')^stamp=t_(i^')^lim, and a_(j^' )=i^'.
Reward maximization: a^* = arg?max?_a ?_j¦V_(a_j,j)
It is noted that the mandatory assignment requirement (MAR) can be combined with feasibility by setting F_ik = 0 if t_i^lim< t_k^stamp (with a strict inequality). However, MARs are technically soft requirements unlike hard feasibility constraints such as the time required to reach the FAF from a holding area. The assignment problem can be solved efficiently using an auction algorithm which has added benefit of calculating an optimal price for each object. In the context of the present disclosure, the optimal price translates into an associative non-negative (also referred as economic reward) given to airlines. The auction algorithm, modified to account for the fact that m?n (i.e., number of objects does not equal number of individuals), is described in an assignment algorithm called using a function Assignment. The assignment algorithm is further better understood by way of following pseudocode provided as example:
Require: set of individuals I and the set of objects O
Require: value matrix V, feasibility vectors {F_i }_I , and initial price vector p = 0 Initialize: for all i?I , j?O,? F?_ij= 0 if t_i^lim< t_j^stamp
Initialize: U ? I , V ? O
Initialize: for all j, a_j=Ø
{Step 1: assign objects with tight feasibility constraints}
while ?min?_(i?U) ?_j¦?F_ij=1? do
k = arg?min?_(i?U) ?_j¦?F_ij=1?
j_k= ?arg?_j (F_kj= 1)
Assignment: a_(j_k )= k,p_k= 0
Update: U ? U \{k}, V ? V \{ j_k}
Remove k^th row and j_k^th column from V: V ? V((-k),(-j_k ))
end while
{Step 2: call auction algorithm if more than one individual is unassigned}
if card(U ) > 1 then
(a,p) = Auction(U ,V ,V,p) {known in the art auction algorithm}
else
i?U,j_i= arg?max?_j V_ij,a_(j_i )= i
end if
The above assignment algorithm is extended to a case where the feasibility is not just intrinsic (i.e., dependent on individual-object pair) but also a function of the assignment of the other objects. In particular, the mandatory assignment requirement captured by the variable t_(i? I)^lim is recalled. Given the assignment a, a simulator function is defined which computes for each i?a, a variable t_i^act> 0 (in the context of landing slot allocation, the actual time of arrival of an aircraft at the FAF, given all slot assignments). If t_i^act>t_i^lim (with some user-specified tolerance), then the assignment a_j=i is deemed infeasible. Considering the assignment defined by the vector a?N_Ø^m. For each a_j?Ø, the simulator function calculates a variable t_(a_j)^act which depends on a (i.e., in general, all of the assignments). The assignment is feasible if and only if t_i^act=t_i^lim+ da for all a_j?Ø, where da = 0 is a user-defined tolerance.
An iterative auction algorithm is described in an iterative assignment algorithm called using a function IterativeAssignment. The iterative assignment algorithm is further better understood by way of following pseudocode provided as example:
Require: The set of individuals I and the set of objects O
Require: Mandatory limits {t_i^lim }_(i?I), nominal values of t_(j?O)^stamp
Require: value matrix V, feasibility vectors F_(i?I), and initial price vector p = 0 Initialize: converged = 0
while converged == 0 do
Run Assignment Algorithm: (a,p) = Assignment(V,p,F,{t_i^lim }_(i?I),t_(j?O)^stamp Calculatet_(j?O)^act= Simulator(a), converged = 1
for j?O do
if a_j?Ø and t_(a_j)^act>t_(a_j)^lim+ da then
converged = 0 {don’t exit the for loop without checking all assignments}
V_(a_j,j)= -8, F_(a_j,j)= 0
end if
end for
end while
Output: assignment and price
At step 210, the one or more hardware processors are configured to update the timestamp for the planning trigger based on a number of aircrafts that have been assigned an arrival slot from the plurality of arrival slots in accordance with the optimal assignment. The entire method of the present disclosure is further better understood by the way of following description provided as an exemplary explanation
In the present disclosure, a problem of releasing n aircraft holding in h stacks is considered, with n_i aircraft in stack i. A fair solution to release the aircraft is a first-come-first-served (FCFS) scheme. It is noted that time required to fly from a holding area to a final approach fix (FAF) is not identical for all holding areas and each holding area may have a different number of aircraft in hold at any given moment. As a result, a precise definition of FCFS is indicated by defining “served” in FCFS in the sense of being offered a choice. In the context of the present disclosure, a baseline FCFS is defined, where a scheme to allocating FAF slots is said to be FCFS if and only if it ensures the following condition for any two aircraft, where the condition is: suppose that the two aircraft arrive at times t_1 and t_2>t_1 in either same or different holding stacks. Let T_b^h {1} denote the time for which aircraft 1 holds in its stack, and T_(b,i)^h {1} the time for which it would have had to hold had aircraft 2 not arrived at all. Then, T_b^h {1}=T_(b,i)^h {1}. The choice made by the aircraft that enters earlier is strictly honored, except in the event of an emergency, and regardless of its implications for aircraft that enter the holding stacks thereafter. It is observed that FCFS guarantees neither that any given aircraft spends a shorter time in hold nor that it arrives sooner at the FAF than aircraft arriving at a holding stack after it. It may be alternatively defined as a scheme for allocating the plurality of arrival slots (alternatively referred as FAF slots) that minimizes net holding time of aircraft. Either of these cases can be considered as a baseline against which the environmentally-optimal scheme of the is evaluated. Due to non-stationary nature of the problem, a receding-horizon approach is used for solving the optimal problem in the present disclosure. The receding-horizon approach takes the following form:
1. Starting with the current time, the optimal control problem (OCP) is solved over a time interval of duration T_p > 0, where T_p is called a planning horizon. This is referred to as short-term OCP (ST-OCP).
2. Implement the solution for time T_h< T_p or until an external signal for replanning is triggered (e.g., an emergency involving an aircraft or an interrupt), and return to step 1 after updating the current time.
As per the ST-OCP, at time t = 0 (without loss of generality), a decision on which aircraft will be released during time [0,T_p] is taken, such that:
1. The arrival time of individual aircraft at the FAF ensures a desired inter-aircraft separation.
2. The net environmental impact of the hold is minimized, in the sense of optimal control problem (OCP) stated in equation (9).
3. Constraints on the arrival time of individual aircraft at the FAF are satisfied.
The receding-horizon approach is further better understood by way of following pseudocode provided as example:
Require: at least one aircraft in the holding pattern
Initialize: time t = t_0 = clock time; planning and replanning horizons T_p,T_h {in minutes}
Update_Flag = 1, Interrupt = 0 {Interrupt is an external signal}
while Update_Flag == 1 do
Determine I {the set of aircraft}
Determine O and t stamp j?O {the set of all available FAF slots} Determine t_(i?I )^lim= Baseline(I ,O) +d_B {Definition of baseline FCFS, with d_B user defined}
For each aircraft i ? I , compute F_i, the set of all feasible assignments Compute V, the value matrix for each (aircraft, feasible slot) pair Assignment: (a,p) = IterativeAssignment()
Calculate n^'= card({ j: a_j?Ø }) {the number of allocated slots} Compute replanning period: T_h= min{T_p/2,n^'/2 }
while t 0 (13)
The constant a can be chosen to equal the fuel burn rate or the rate of emission of the specific aircraft. The actual mechanism for transferring the reward could be monetary or even in the form of carbon credits.
SIMULATION RESULTS:
In the present disclosure, a few illustrative simulation results are discussed. Costs are computed using the data in Table 1. For simplicity, the requirement of aircraft-dependent inter-aircraft separation is not imposed.
Case 1: two stacks, similar paths to FAF:
A case is considered where there are two holding stacks, and time of flight from each stack to the FAF has been 5 min. Aircraft were introduced in each stack every minute with a probability of 50%. An aircraft was released from the stack only if its altitude was less than or equal to 9000 ft. Statistics of policies that minimize fuel consumption and holding time, respectively were compared. The assignment was carried out using the auction algorithm. Results representing 20 simulations of each policy, each of which was carried out over 40 minutes, are summarized in Table 2. The replanning horizon was set to 5 minutes.
Policy
Statistic/variable Holding time
Environmental cost
Total holding time Env cost Total holding time Env cost
Average 114 3858.8 124 3136
Std deviation 21 1068 27 840
Table 2
From Table 2, a trade-off between the two policies is evident. When the minimum-fuel policy is employed, the total holding time goes up by 9% (normalized over all aircraft) while the environmental cost reduces by over 20%.
The written description describes the subject matter herein to enable any person skilled in the art to make and use the embodiments. The scope of the subject matter embodiments is defined herein and may include other modifications that occur to those skilled in the art. Such other modifications are intended to be within the scope of the present disclosure if they have similar elements that do not differ from the literal language of the embodiments or if they include equivalent elements with insubstantial differences from the literal language of the embodiments described herein.
It is to be understood that the scope of the protection is extended to such a program and in addition to a computer-readable means having a message therein; such computer-readable storage means contain program-code means for implementation of one or more steps of the method, when the program runs on a server or mobile device or any suitable programmable device. The hardware device can be any kind of device which can be programmed including e.g., any kind of computer like a server or a personal computer, or the like, or any combination thereof. The device may also include means which could be e.g., hardware means like e.g., an application-specific integrated circuit (ASIC), a field-programmable gate array (FPGA), or a combination of hardware and software means, e.g., an ASIC and an FPGA, or at least one microprocessor and at least one memory with software processing components located therein. Thus, the means can include both hardware means and software means. The method embodiments described herein could be implemented in hardware and software. The device may also include software means. Alternatively, the embodiments may be implemented on different hardware devices, e.g., using a plurality of CPUs.
The embodiments herein can comprise hardware and software elements. The embodiments that are implemented in software include but are not limited to, firmware, resident software, microcode, etc. The functions performed by various components described herein may be implemented in other components or combinations of other components. For the purposes of this description, a computer-usable or computer readable medium can be any apparatus that can comprise, store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device.
The illustrated steps are set out to explain the exemplary embodiments shown, and it should be anticipated that ongoing technological development will change the manner in which particular functions are performed. These examples are presented herein for purposes of illustration, and not limitation. Further, the boundaries of the functional building blocks have been arbitrarily defined herein for the convenience of the description. Alternative boundaries can be defined so long as the specified functions and relationships thereof are appropriately performed. Alternatives (including equivalents, extensions, variations, deviations, etc., of those described herein) will be apparent to persons skilled in the relevant art(s) based on the teachings contained herein. Such alternatives fall within the scope of the disclosed embodiments. Also, the words “comprising,” “having,” “containing,” and “including,” and other similar forms are intended to be equivalent in meaning and be open ended in that an item or items following any one of these words is not meant to be an exhaustive listing of such item or items, or meant to be limited to only the listed item or items. It must also be noted that as used herein, the singular forms “a,” “an,” and “the” include plural references unless the context clearly dictates otherwise.
Furthermore, one or more computer-readable storage media may be utilized in implementing embodiments consistent with the present disclosure. A computer-readable storage medium refers to any type of physical memory on which information or data readable by a processor may be stored. Thus, a computer-readable storage medium may store instructions for execution by one or more processors, including instructions for causing the processor(s) to perform steps or stages consistent with the embodiments described herein. The term “computer-readable medium” should be understood to include tangible items and exclude carrier waves and transient signals, i.e., be non-transitory. Examples include random access memory (RAM), read-only memory (ROM), volatile memory, nonvolatile memory, hard drives, CD ROMs, DVDs, flash drives, disks, and any other known physical storage media.
It is intended that the disclosure and examples be considered as exemplary only, with a true scope of disclosed embodiments being indicated herein by the following claims.
, Claims:We Claim:
1. A processor implemented method (200), comprising:
receiving (202), via one or more hardware processors, a plurality of input data pertaining to an aviation system, wherein the plurality of input data comprises (i) a plurality of data pertaining to at least one aircraft from a plurality of aircraft in a holding pattern for a specific airport, (ii) a plurality of arrival slots for an arrival runway of the specified airport, and (iii) a signal from a planning trigger equipped with a timestamp;
computing (204), via the one or more hardware processors, a set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft using the plurality of input data when the signal is received from the planning trigger;
computing (206), via the one or more hardware processors, a value matrix for the set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft, wherein each entry of the computed value matrix is indicative of an amount of fuel consumed by a specific aircraft assigned to a specific slot;
determining (208), via the one or more hardware processors, (i) an optimal assignment from the set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft based on the computed value matrix and (ii) an associative non-negative reward for the optimal assignment of the plurality of arrival slots for each aircraft from the plurality of aircraft; and
updating (210), via the one or more hardware processors, the timestamp for the planning trigger based on a number of aircrafts that have been assigned an arrival slot from the plurality of arrival slots in accordance with the optimal assignment.

2. The processor implemented method as claimed in claim 1, wherein the plurality of arrival slots are indicative of a plurality of time instants at which at most one aircraft from the plurality of aircraft in the holding pattern arrives at a predefined point at a specific distance and a specific altitude along a center line of the arrival runway of the specified airport.

3. The processor implemented method as claimed in claim 1, wherein the predefined point represents a final approach fix (FAF) for the arrival runway.

4. The processor implemented method as claimed in claim 1, wherein the optimal assignment ensures minimizing net environmental impact of the plurality of aircraft in the holding pattern.

5. The processor implemented method as claimed in claim 1, wherein the associative non-negative reward for an aircraft is determined in terms of a linear programming problem (LPP) by comparing a value indicating sum of total holding time of the aircraft and time taken by the aircraft to fly to the FAF with a baseline value.

6. The method as claimed in claim 5, wherein the associative non-negative reward is provided to maintain a fair allocation of the plurality of arrival slots to a set of environment friendly aircraft from the plurality of aircraft in terms of at least one of (i) a reduction in airport landing fees, and (ii) an equivalent carbon credit.

7. A system (100), comprising:
a memory (102) storing instructions;
one or more communication interfaces (106); and
one or more hardware processors (104) coupled to the memory (102) via the one or more communication interfaces (106), wherein the one or more hardware processors (104) are configured by the instructions to:
receive a plurality of input data pertaining to an aviation system, wherein the plurality of input data comprises (i) a plurality of data pertaining to at least one aircraft from a plurality of aircraft in a holding pattern for a specific airport, (ii) a plurality of arrival slots for an arrival runway of the specified airport, and (iii) a signal from a planning trigger equipped with a timestamp;
compute a set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft using the plurality of input data when the signal is received from the planning trigger;
compute a value matrix for the set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft, wherein each entry of the computed value matrix is indicative of an amount of fuel consumed by a specific aircraft assigned to a specific slot;
determine (i) an optimal assignment from the set of feasible assignments of the plurality of arrival slots for each aircraft from the plurality of aircraft based on the computed value matrix and (ii) an associative non-negative reward for the optimal assignment of the plurality of arrival slots for each aircraft from the plurality of aircraft; and
update the timestamp for the planning trigger based on a number of aircrafts that have been assigned an arrival slot from the plurality of arrival slots in accordance with the optimal assignment.

8. The system as claimed in claim 7, wherein the plurality of arrival slots are indicative of a plurality of time instants at which at most one aircraft from the plurality of aircraft in the holding pattern arrives at a predefined point at a specific distance and a specific altitude along a center line of the arrival runway of the specified airport.

9. The system as claimed in claim 7, wherein the predefined point represents a final approach fix (FAF) for the arrival runway.

10. The system as claimed in claim 7, wherein the optimal assignment ensures minimizing net environmental impact of the plurality of aircraft in the holding pattern.

11. The system as claimed in claim 7, wherein the associative non-negative reward for an aircraft is determined in terms of a linear programming problem (LPP) by comparing a value indicating sum of total holding time of the aircraft and time taken by the aircraft to fly to the FAF with a baseline value.

12. The system as claimed in claim 11, wherein the associative non-negative reward is provided to maintain a fair allocation of the plurality of arrival slots to a set of environment friendly aircraft from the plurality of aircraft in terms of at least one of (i) a reduction in airport landing fees, and (ii) an equivalent carbon credit.

Dated this 7th Day of July 2023

Tata Consultancy Services Limited
By their Agent & Attorney

(Adheesh Nargolkar)
of Khaitan & Co
Reg No IN-PA-1086