Nowadays, aircraft move along routes consisting of horizontal tunnels and vertical ight levels. With that, the routes can split or join. At the point of route joining, a problem of aircraft ows merging appears. Such a problem is highly important near airports, where the air tra c is very dense. The main demand for aircraft ows merge is the presence of the minimal safe time interval between arrival instants at the merge point. There are two main tools for changing arrival instant of an aircraft to a checkpoint. The rst of them is control of the aircraft velocity, which allows to obtain relatively small changes of the arrival instant both to earlier or later times. To get larger delays one uses the second tool, delay schemes. As a result of designing system of delay schemes for a certain airport, one has information about possible acceleration and deceleration of aircraft moving along each route. Further on the basis of this information, it is necessary to study capabilities of the constructed system for formation of safe aircraft ows merge. In the paper, a formalization is set forth for the problem of optimal formation of aircraft arrival schedule under the present delay scheme system as a nite-dimensional optimization problem. Also, the authors consider applicability of di erent methods for search of multivariable function extrema to this problem. Results of numerical computations are discussed.
The problem of non-con ict aircraft ows merging is considered. We are given the following input data: { an ascending ordered nominal arrival times collection ftinomgiN=1; ? Copyright c 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). { a variation interval tinom ! [tinom tiacc; tinom + tidec] for each aircraft in the queue. The values tiacc, tidec show how long the ith aircraft can be accelerated or decelerated according to its speci cations and the delay schemes allocated along the airway of this aircraft; { a minimal safe time interval is;ajfe between the arrival instants with the indices i, j in the merged queue.
The objective is to obtain a new collection ftig of instants of aircraft arrival to the merge point such that ti 2 [tinom tiacc; tinom + tidec]. The new collection should obey the safety demands: 8 1 i; j N , tj ti is;ajfe (assuming that the ith aircraft arrives earlier than the jth one). With that, one should minimize some criterion F ftig; ftinomg , which describes the optimality of the obtained schedule from the point of view of air-tra c control dispatchers and airport services.
Thus, the following optimization problem arises: Simplest Criterion. Let us consider the simplest convex piecewise-linear penalty criterion of the following form: i=1 i=1 i=1 If to take into account that the values tinom are constant, then the subtrahend in the right-hand of the equality is constant too. Therefore, this criterion minimizes the sum of actual instants of aircraft arrivals to the merging point, or minimizes the instants themselves. Its sense is \to let an aircraft pass as earlier as possible". Therefore, it is enough to apply the greedy algorithm for minimization of this criterion, which assigns the earliest possible arrival instant for each aircraft. Two-Zone Symmetric Piecewise-Linear Criterion. Next criterion allows to penalize both accelerations and decelerations due to existing costs on acceleration and deceleration maneuvers (fuel consumption, for example): N F ftig; ftinomg = X jti
tinomj: i=1 It punishes both delays and accelerations of aircraft with respect to their nominal arrival instants. (1) (2) (3) Two-Zone Asymmetric Piecewise-Linear Criterion.
N F ftig; ftinomg = X K (ti tnom); i K =
i=1 (K+;
ti > tinom;
K ; ti < tinom: Consideration of such a criterion is stipulated by potentially di erent expenditures for accelerating and delaying an aircraft. Two cases are evident: K < K+ when to accelerate an aircraft is cheaper than to delay it, and the opposite case K > K+.
Three-Zone Piecewise-Linear Criterion. Criterion (4) can be made more precise. Namely, there are two variants of an aircraft delay: when the aircraft decreases its velocity or when it moves along some delay schemes with normal velocity. Fuel expenditures are greater in the second variant, therefore, long delays should be punished more than short ones.
In this situation, one can choose the optimality criterion for one aircraft as it is shown in Fig. 1. The parameter de nes the maximal delay value, which can be achieved by decreasing velocity only. The coe cients K , K+1, K+2 describe the values of speci c ne for each of the motion regimes: acceleration, delay with decreasing velocity only, delay with usage of delay schemes. The continuity of the function f at the point tinom + is questionable, but we assume it, because we need it to pass to a linear programming problem.
On the basis of the values , K , K+1, K+2 and continuity of the function f , one can compute coe cients a, b, c, d of the following representation of f : f (ti; tinom) = ajt tnomj + b ti i
(tinom + ) + cti + d; F ftig; ftinomg =
N X f (ti; tinom): i=1 (4) (5)
Minimization of all convex piecewise-linear criteria described above can be
represented as a problem of linear programming by introducing additional
variables denoting the absolute values involved in the criteria. To solve the linear
programming problem we have used the simplex-method ful lled in the computer
library GLPK [
Non-Linear Criteria All the objective functions considered above are linear in the sense that the penalty for a deviation from the nominal arriving time grew in proportion to the deviation. Also it would be reasonable to use criteria, in which deviations of different magnitudes are penalized in di erent ways (non-proportionally). Studying of such a situation naturally leads to nonlinear penalty functions. Quadratic Criterion. The simplest non-linear criterion is the quadratic one: Criterion with a Restriction on the Minimum Variation Value. The need to use non-linear criteria was due to avoiding of small variations of aircraft arrival time at the merge point, which are not technological. The following ne function has been proposed for deviations of the assigned arrival instant of aircraft from the nominal instant, which has minimums at zero (no variation) and at some value , which corresponds to the minimum feasible non-zero variation of the arrival instant (see Fig. 2).
The function depends on the deviation of the assigned arrival time from the
nominal (that is, on the absolute value of the di erence of these instants) and
is determined by four parameters: the value of variation that can be neglected
(3-5 seconds), the minimum value of nonzero variation (30-40 seconds), the
parameter of the depth of the ravine, the parameter of the ratio of the
values of the auxiliary minimum and the intermediate maximum.
Non-Linear Optimization Approaches. A typical approach during
numerical studying nonlinear extreme problems with constraints is to pass to
unconditional minimization of a function obtained from the original one by adding some
terms re ecting the constraints. Unconditional minimization is carried out by
means one or another variant of the gradient descent (see, for example, [
In the problem under consideration, we have two series of constraints. The rst of them are the constraints for the maximal accelerations/decelerations of aircraft: ti 2 [tinom tacc; tinom + tdec]. Note that for these constraints the point ftinomg is internal and can be taken as the initial one. Therefore, these constraints have been taken into account in a standard way, by terms with logarithms: N X ln ti i=1 (tinom tacc) +
N X ln (tinom + tdec) i=1 ti : Inside the parallelepiped QiN=1[tinom tacc; tinom + tdec], the arguments of the logarithms are positive, at the boundary and outside it they are non-positive and, therefore, these terms are de ned only inside the parallelepiped. With approach to the boundary from inside due to the sign minus, the value of these terms tends to +1, what under application of a gradient descent prevents leaving the parallelepiped. Often, constraints taken into account through terms of such a type are called severe: they principally prevents violating the corresponding constraints of the original problem. The coe cient regulates the severity of the constraints: the less it is, the closer point can go to the boundary of the parallelepiped.
The second group of constraints is connected explicitly to the objective of the original problem, to the safe intervals between aircraft at the merge point: jti tj j is;ajfe, 1 i; j N . Taking into account the keeping the order of aircraft, one can reduce number of constraints: ti+1 ti is;ajfe, i = 1; N 1.
tnomg, generally speaking, does not obey these conUnfortunately, the point f i straints (otherwise, the problem itself would be absent). So, we tested two ways to take into account them.
The rst way is the way of consideration of them as strict. That is to the function to be minimized we add the following terms: ln (ti tj )2
( is;ajfe)2 : The di erence of the instants ti and tj is powered by 2, because, in the general case (not for the quadratic criterion), there is no guarantee that the initial order of the nominal instants would be kept. The coe cient regulates the severity of the constraints.
In this case, the minimized function has the following form: However, we need some initial point for the algorithm of gradient descent, which obeys the strict constraints ti0+1 ti0 > is;ai+fe1. It has been performed in the following way. At rst, the greedy algorithm (see Section 2.1) works. If it fails, then it means that the incoming ows are too dense and there is no any safe schedule for all aircraft; the entire algorithm stops in this case. If the greedy algorithm g nishes successfully, then the obtained collection fti g is checked. Namely, if there is a number i such that tig = tinom + tdec, it means that there is a group of aircraft such that the rst aircraft in the group is accelerated maximally, the last aircraft (with the number i ) in the group is delayed maximally, and between each two neighboring aircraft in the the group there is exactly the minimal safe interval is;ajfe. So, such a group cannot be \slid apart" to obtain a collection of instants, for which all constraints are ful lled strictly. That is one cannot obtain the internal initial point for the chosen non-linear optimization method. In this situation, the algorithm ceases too.
Finally, if the check is passed successfully, then on the basis of the obtained g 0 set fti g the internal point fti g is constructed. The \slide reserve" is computed: = mini(tinom + tdec tig). Indeed, the computation of is made simultaneously with the check of slide possibility: if = 0, it just means that for some i the epqouinatliitsycatigrri=ed toinuotm: t+i0 =tdetcig +oc(ciur1s.) T=hNen. Athcecocrodminpgutthaitsiofonrmofultaheeaicnhitciaolnsinecteurtnivael pair of aircraft is slid apart to the initial value plus the value =N ; with that, the boundaries of the segments [tinom tacc; tinom + tdec] are not reached. Therefore, 0 the collection fti g computed in the shown way indeed is an internal point.
After that, the chosen non-linear optimization method is started from the computed point.
The second way for taking into account these constraints is in representing them as soft constraints : the ne criterion is chosen in such a way that it is de ned even for ti+1 ti is;ai+fe1 in the contrast with the logarithms in the severe constraints. So, one needs that the function has a plateau when ti+1 > ti + is;ai+fe1, which turns fast to a step when ti+1 tends to ti + is;ai+fe1. When ti+1 < ti + is;ai+fe1, the function should be inclined enough to \push out" the argument point to the area ti+1 > ti + is;ai+fe1.
Two types of the soft constraints s(ti; tj ) were considered. The rst type of soft constraints (see Fig. 3, on the left) potentially allows the coincidence of the current arrival instants ti and tj , particularly, the coincidence of the nominal arrival instants. The constraint function s(ti; tj ) of the second type (see Fig. 3, on the right) tends to in nity when the values ti and tj come closer and is unde ned when ti and tj are equal. In this situation, it is necessary to slide apart slightly each group of coinciding nominal arrival instants. Now, the function to be minimized looks like
F (ftig; ftinomg) = F ftig; ftinomg (8) N X ln(ti
The sense of the last term is that it iterates over all pairs of aircraft and nes the result if the minimal safe time interval is not maintained between this pair of aircraft.
As the initial point for minimization method in the case of soft constraints, the collection of the nominal instants ftinomg is taken with groups of coinciding instants slightly slid apart. After that, the chosen minimization method is started.
To optimize the criteria with soft and strict constraints, the Newton method and the Hooke { Jeeves direct search method have been used. It is worthy to note that Newton method is changed to the gradient descent method when the point is inside the unsafety area, because the ne function is non-convex there and the Newton method is not applicable.
Unfortunately, optimization was successful only for the convex quadratic ne function (6). But substantially non-linear ne function (see Fig. 2) generates a multiextrema total criterion F ftig; ftinomg and, therefore, criteria (7) and (8). Of course, multiextrema criteria almost can not be successfully minimized, and neither Newton, nor Hooke { Jeeves methods give anything similar to the desired minimum.
There is another approach to minimizing nonlinear functions with constraints
such as equalities / inequalities using linear programming methods called
Successive Linear Programming [
The main idea of the SLP method is that the nonlinear problem (7) and its constraints are locally linearized. The linearized target function together with constraints, which are already linear, gives a linear programming problem, which is solved by means of linear programming methods.
SLP successfully works in more situations than Newton and Hooke { Jeeves methods, nevertheless, quite often does not reach the minimum point.