Determination of the optimal aircrafts assignment for carrying out search and rescue operations

Аuthors

Mikhnenko N. K.^1*, Vakhromeev P. V.^2**, Ktitrov S. V.^1***

1. National Research Nuclear University MEPhI (Moscow Engineering Physics Institute), 31, Kashirskoe shosse, Moscow, 115409, Russia
2. Compani «RTI», 10, 8 Marta street, Bld. 1, Moscow, 127083, Russia

*e-mail: abernod137@gmail.com
**e-mail: vpasha@inbox.ru
***e-mail: svktitrov@mephi.ru

Abstract

We consider the problem of determining the optimal assignment of aircrafts for carrying out search and rescue operations (SRO) based on the assumption that only one aircraft is allowed in the zone during the SRO. Every zone, attainable fr om given aerodromes should be taken into account [1]. The goal is to maximize the total search time by all involved aircrafts. In order to ensure compliance of both conditions, we proposed to solve the problem in two stages. The goal of the first stage is to maximize the number of aircrafts that can be assigned to the SRO zones assuming the latter are reachable fr om the given aerodromes. The goal for the second stage is to maximize the total search time.

We can assign the task of finding the maximum possible aircrafts, which can be distributed to the SRO zones in the form of matchings “type of aircraft / aerodrome” (TA), as follows:

subject to:

where m – the number of SRO zones; k – the number of different TAs;  h_i – the amount of aircrafts of i^th TA; x_ij – variable, that adopt values either 1 or 0, depending on whether the aircraft of i^th TA is assigned to j^th zone SRO or not.

We represent the assignment of the second task in the following way:

subject to:

where t_ij – search time of the i^th TA in j^th zone SRO (taking into account flight time to the zone SRO since departure and flight time to return to the aerodrome); ­— the goal value (1).

We proposed to consider two methods of solving assigned tasks:

• Simplex method;

• Methods based on algorithms for solving Boolean satisfiability problems (SAT).

It is necessary to emphasize that assigned tasks belong to the class of pseudo boolean (PB) linear programming problems (LPP). In most cases, algorithms, based on the simplex method, are applied to solve the problems of this class, as a result of the inapplicability of itself. However, due to the structure of assigned tasks, it is possible to use simplex-method without any modifications to obtain the optimum PB solution.

In recent decades, the determinants of Boolean satisfiability (SAT Solvers), based on the SAT methods, have made significant progress. The record performance of modern SAT Solvers opens up new prospects for their use in applications wh ere previously it was considered to be possible only conditionally.

However, due to the NP-completeness of the SAT-problem, there are examples, the time, required to search for the optimum solution of which, is showing the exponential growth. One of SAT approach inapplicability cases is demonstrated later in terms of assigned tasks by the example of the currently best SAT Solver in PB LPP category [2]: Nagoya Pseudo-Boolean Solver (NaPS) v. 1.02b [3].

During the analysis of the assigned tasks, the algorithm, that under certain conditions, related with input data, can reduce the dimension of the assigned tasks, was developed. It is given below:

Suppose k TA and m SRO zones are given. Furthermore, we can distinguish SRO zones, attainable only by i^th TA.

•  Z_i denotes the number of zones, attainable by i^th TA;

•  M_i denotes the number of zones, attainable only by i^th TA;

•  H_i denotes the number of i^th TA aircrafts.

Then the algorithm becomes as follows:

1.  If and then the aircrafts must be assigned to SRO zones, attainable only by i^th TA.

2.  If then the list of SRO zones, attainable by i^th TA should be considered. This list is sorted in ascending order of search time in corresponding zones. Finally, if among the last H_i elements of this list, there are SRO sones, attainable only by i^th TA, then the aircrafts must be assigned to these zones.

3. If there are such SRO zones, attainable only by i^th TA, that have remained after the 2^nd rule, then SRO zone, attainable by j^th TA, must be excluded from the list of 2^nd rule if  . Thereafter 2^nd rule is repeated.

4. 3^d rule is repeated until  or it is feasible.

Testing the effectiveness of the developed algorithm was carried out with solutions sensing method (SSM) [4]. SSM — is the method for solving PB LPP, which has exponential complexity. Consequently, it is particularly sensitive to reduction of the assigned tasks dimension. This became the reason of selecting this method. We will use the abbreviation of MSSM for SSM modification with the developed algorithm.

Figure 1 — Comparison of SSM and MSSM effectiveness growth

Based on the results (fig. 1), the following conclusions can be made:

•  Time, spent by SSM and MSSM to find the optimal solution, strongly increases with dimension increasing of the tasks assigned. This fact confirms the exponential complexity of SSM;

•  The developed algorithm, under the conditions foreseen by this algorithm, does reduce the time spent to find the optimal solution;

•  The developed algorithm, in case of conditions foreseen are not satisfied, increases the time of finding the optimal solution. Compared to the overall time spent to find the optimal solution, this increase is insignificant.

Examples, which evaluated the effectiveness of the selected approaches, can be divided into 2 groups:

1.  Gradually increasing the number of TA with the same number of aircrafts and zones SRO;

2.  Gradually increasing the number of zones SRO and with constant number of TA and number of aircrafts.

This separation is explained by the following formula:

the complexity of the solution space: ,

demonstrating the increase rate of the solution space, depending on the input data.

Figure 2 — Illustration of the Naps 1.02b results for the 1^st group of constraints

Figure 3 — Illustration of the Naps 1.02b results for the 2^nd group of constraints

Time spent to find the optimal solution of the same test examples using the simplex method in all cases did not exceed 3 ms.

According to the results of the tests (fig. 2, fig. 3), the following conclusions can be made:

•  the time spent to find an optimum solution for examples of the first group using Nagoya Pseudo-Boolean Solver (1.02b) has polynomial dependence on the input data;

•  the time spent to find an optimal solution for examples of the second group using Nagoya Pseudo-Boolean Solver (1.02b) has an exponential dependence on the input data that makes SAT approach inapplicable for the assigned tasks;

• high efficiency of simplex method for solving the assigned tasks has been demonstrated.

Based on these results it is the simplex method we proposed to use for solving such class of problems.

Keywords:

search and rescue operations, linear programming problem with boolean variables, unimodular matrices

References

1. MChS Rossii, URL: http://www.mchs.gov.ru/dop/sily/Aviacija

2. Nemudryi K.V. Trudy MAI, 2014, no. 75: http://www.mai.ru/science/trudy/published.php?ID=49715

3. About Sat4j // Sat4j — the Boolean satisfaction and optimization library in Java, URL: http://www.sat4j.org/allabout.php.

4. Pseudo-Boolean Competition 2016: satisfaction and optimization track: ranking of solvers. Centre de Recherche en Informatique de Lens, URL: http://www.cril.univ-artois.fr/PB16/results/ranking.php?idev=81

5. NaPS (Nagoya Pseudo-Boolean Solver). Sakai Lab./Seki Lab, URL: http://www.trs.cm.is.nagoya-u.ac.jp/NaPS

6. Zagrebaev A. M., Kritsyna N. A., Kulyabichev Yu. P., Shumilov Yu. Yu. Metody matematicheskogo programmirovaniya v zadachakh optimizatsii slozhnykh tekhnicheskikh sistem: uchebnoe posobie (Mathematical programming techniques in optimization problems of complex technical systems: a tutorial), Moscow, MEPhI, 2007, 332 p.

Download