Numerical Optimization of Non-Conflict Aircraft Flow Merging ? Arseniy A. Spiridonov[0000−0002−8453−6368] and Sergey S. Kumkov[0000−0002−2690−5380] Krasovskii Institute of Mathematics and Mechanics, UrB RAS, Yekaterinburg, Russia spiridonov.arseniy@gmail.com, sskumk@gmail.com Abstract. Nowadays, aircraft move along routes consisting of horizon- tal tunnels and vertical flight levels. With that, the routes can split or join. At the point of route joining, a problem of aircraft flows merging appears. Such a problem is highly important near airports, where the air traffic is very dense. The main demand for aircraft flows 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 first of them is control of the aircraft veloc- ity, 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 flows merge. In the paper, a formal- ization is set forth for the problem of optimal formation of aircraft arrival schedule under the present delay scheme system as a finite-dimensional optimization problem. Also, the authors consider applicability of differ- ent methods for search of multivariable function extrema to this problem. Results of numerical computations are discussed. Keywords: Aircraft flows merging · Arrival instant variation · Safety interval · Discrete optimization · Piecewise-linear criteria · Non-linear criteria · Linear programming · Breadth-first search · Gradient descent · Newton method · Hooke-Jeeves algorithm · Successive linear program- ming method 1 Problem Statement The problem of non-conflict aircraft flows merging is considered. We are given the following input data: – an ascending ordered nominal arrival times collection {tnom i }N i=1 ; ? Copyright c 2020 for this paper by its authors. Use permitted under Creative Com- mons License Attribution 4.0 International (CC BY 4.0). Optimization of non-conflict aircraft flow merging 209 – a variation interval tnom i → [tnom i − tacc nom i , ti + tdec i ] for each aircraft in the acc dec queue. The values ti , ti show how long the ith aircraft can be accelerated or decelerated according to its specifications and the delay schemes allocated along the airway of this aircraft; safe – a minimal safe time interval τi,j between the arrival instants with the indices i, j in the merged queue. The objective is to obtain a new collection {ti } of instants of aircraft arrival to the merge point such that ti ∈ [tnom i − tacc i , ti nom + tdec i ]. The new collection safe should obey the safety demands: ∀ 1 ≤ i, j ≤ N , tj − ti ≥ τi,j (assuming that the ith aircraft arrives earlier than  the jth one). With that, one should minimize some criterion F {ti }, {tnom i } , which describes the optimality of the obtained schedule from the point of view of air-traffic control dispatchers and airport services. Thus, the following optimization problem arises: N  X F {ti }, {tnom i } = f (ti , tnom i ) → min i=1 subject to (1) ti ∈ [tnom i − tacc nom i , ti + tdec i ], safe ∀ 1 ≤ i, j ≤ N (tj > ti ⇒ tj − ti ≥ τi,j ). 2 Aircraft with the Same Type 2.1 Convex Piecewise-Linear Criteria Simplest Criterion. Let us consider the simplest convex piecewise-linear penalty criterion of the following form: N N N  X X X F {ti }, {tnom i } = (ti − tnom i ) = ti − tnom i (2) i=1 i=1 i=1 If to take into account that the values tnom i 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 accel- eration and deceleration maneuvers (fuel consumption, for example): N  X F {ti }, {tnom i } = |ti − tnom i |. (3) i=1 It punishes both delays and accelerations of aircraft with respect to their nominal arrival instants. 210 A. A. Spiridonov, S. S. Kumkov Two-Zone Asymmetric Piecewise-Linear Criterion. N  X F {ti }, {tnom i } = K · (ti − tnom i ), (4) i=1 ( K+ , ti > tnom i , K= nom −K− , ti < ti . Consideration of such a criterion is stipulated by potentially different expendi- tures 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 δ defines the maximal delay value, which can 1 2 be achieved by decreasing velocity only. The coefficients K− , K+ , K+ describe the values of specific fine 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 tnomi + δ is questionable, but we assume it, because we need it to pass to a linear programming problem. Fig. 1. Three-zone piecewise-linear criterion. 1 2 On the basis of the values δ, K− , K+ , K+ and continuity of the function f , one can compute coefficients a, b, c, d of the following representation of f : f (ti , tnom i ) = a|t − tnom i | + b ti − (tnom i + δ) + cti + d, N  X (5) F {ti }, {tnom i } = f (ti , tnom i ). i=1 Optimization of non-conflict aircraft flow merging 211 Minimization of all convex piecewise-linear criteria described above can be represented as a problem of linear programming by introducing additional vari- ables denoting the absolute values involved in the criteria. To solve the linear programming problem we have used the simplex-method fulfilled in the computer library GLPK [4]. 2.2 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 dif- ferent magnitudes are penalized in different 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: N  X F {ti }, {tnom i } = (ti − tnom i )2 . (6) i=1 Large deviations are punished quadratically larger than small ones. 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 fine function has been proposed for deviations of the assigned arrival instant of air- craft 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). Fig. 2. Criterion with a restriction on the minimum variation value. The function depends on the deviation of the assigned arrival time from the nominal (that is, on the absolute value of the difference of these instants) and 212 A. A. Spiridonov, S. S. Kumkov 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 numeri- cal studying nonlinear extreme problems with constraints is to pass to uncondi- tional minimization of a function obtained from the original one by adding some terms reflecting the constraints. Unconditional minimization is carried out by means one or another variant of the gradient descent (see, for example, [2]) if the obtained function is differentiable or by a direct search method if the differ- entiability is absent. As the initial point for the method, one should find a point, which strictly obeys all constraints of the original problem. Due to this, methods of this family are often called internal point methods (see, for example, [1, 2]). In the problem under consideration, we have two series of constraints. The first of them are the constraints for the maximal accelerations/decelerations of aircraft: ti ∈ [tnom i − tacc , tnom i + tdec ]. Note that for these constraints the point nom {ti } 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 N  X  −α · ln ti − (tnom i − tacc ) + ln (tnom i + tdec ) − ti . i=1 i=1 QN Inside the parallelepiped i=1 [tnom i − tacc , tnom i + tdec ], the arguments of the logarithms are positive, at the boundary and outside it they are non-positive and, therefore, these terms are defined only inside the parallelepiped. With approach to the boundary from inside due to the sign minus, the value of these terms tends to +∞, 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 coefficient α 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: safe |ti − tj | ≥ τi,j , 1 ≤ i, j ≤ N . Taking into account the keeping the order of safe aircraft, one can reduce number of constraints: ti+1 − ti ≥ τi,j , i = 1, N − 1. nom Unfortunately, the point {ti }, generally speaking, does not obey these con- straints (otherwise, the problem itself would be absent). So, we tested two ways to take into account them. The first 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 − (τi,j safe 2  ) . Optimization of non-conflict aircraft flow merging 213 The difference 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 coefficient α regulates the severity of the constraints. In this case, the minimized function has the following form: F({ti }, {tnom }) = F {ti }, {tnom  i i } (7) N X  −α ln(ti − tnom i + tacc ) + ln(−ti − tnom i + tdec ) i=1 N X −1 N X ln (ti − tj )2 − (τi,j safe 2  −α ) . i=1 j=i+1 However, we need some initial point for the algorithm of gradient descent, which obeys the strict constraints t0i+1 − t0i > τi,i+1 safe . It has been performed in the fol- lowing way. At first, the greedy algorithm (see Section 2.1) works. If it fails, then it means that the incoming flows are too dense and there is no any safe schedule for all aircraft; the entire algorithm stops in this case. If the greedy algorithm finishes successfully, then the obtained collection {tgi } is checked. Namely, if there is a number i∗ such that tgi∗ = tnom i∗ + tdec , it means that there is a group of air- craft such that the first 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 safe interval τi,j . So, such a group cannot be “slid apart” to obtain a collection of instants, for which all constraints are fulfilled 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 set {tgi } the internal point {t0i } is constructed. The “slide reserve” is computed: η = mini (tnom i + tdec − tgi ). Indeed, the computation of η is made simultaneously with the check of slide possibility: if η = 0, it just means that for some i∗ the equality tgi∗ = tnomi∗ + tdec occurs. Then the computation of the initial internal point is carried out: t0i = tgi +(i−1)·η/N . According this formula each consecutive pair of aircraft is slid apart to the initial value plus the value η/N ; with that, the boundaries of the segments [tnom i − tacc , tnom i + tdec ] are not reached. Therefore, 0 the collection {ti } 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 fine criterion is chosen in such a way that it is safe defined even for ti+1 −ti ≤ τi,i+1 in the contrast with the logarithms in the severe safe constraints. So, one needs that the function has a plateau when ti+1 > ti +τi,i+1 , safe safe which turns fast to a step when ti+1 tends to ti + τi,i+1 . When ti+1 < ti + τi,i+1 , the function should be inclined enough to “push out” the argument point to the safe area ti+1 > ti + τi,i+1 . 214 A. A. Spiridonov, S. S. Kumkov Fig. 3. Possible forms of representing the soft constraints functions connected with the minimal safe time interval between the arrival instants; on the left: coincidence of the arrival instants tj and tj is allowed; on the right: coincidence of the arrival instants tj and tj is not allowed. Two types of the soft constraints s(ti , tj ) were considered. The first 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 infinity when the values ti and tj come closer and is undefined 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({ti }, {tnom }) = F {ti }, {tnom  i i } (8) N X  −α ln(ti − tnom i + tacc ) + ln(−ti − tnom i + tdec ) i=1 N X −1 N X + s(ti , tj ). i=1 j=i+1 The sense of the last term is that it iterates over all pairs of aircraft and fines 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 {tnom i } is taken with groups of coincid- ing 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 fine function is non-convex there and the Newton method is not applicable. Optimization of non-conflict aircraft flow merging 215 Unfortunately, optimization was successful only for the convex quadratic fine function (6). But substantially non-linear fine  function (see Fig. 2) generates a multiextrema total criterion F {ti }, {tnom i } 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 Succes- sive Linear Programming [3]. 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. References 1. Boyd, S., Vandenberghe, L.: Convex optimization. Cambridge University Press, New York, NY, USA (2004) 2. Leader, J.J.: Numerical analysis and scientific computation. Addison Wesley, Boston (2004) 3. Still, C., Westerlund, T.: A linear programming-based optimization algorithm for solving nonlinear programming problems. European Journal of Operational Re- search 200(3), 658–670 (2010) 4. GLPK (GNU Linear Programming Kit), https://www.gnu.org/software/glpk/