The paper studies the statistical characteristics of methods for constructing a suboptimal flight route for an unmanned aerial vehicle (UAV) that performs the task of eliminating the consequences of an emergency. The task can be classified as a traveling salesman problem (TSP). The paper explores the features of the procedure for finding and refining a reference route. For the effective use of limited computing resources in field conditions, preference is given to quickly obtaining a suboptimal solution. For this, at the first stage, a reference solution is obtained using the greedy nearest neighbor algorithm, which is then improved using a stack of iterative methods. The order of methods in the stack (moving one point, exchanging two points, and eliminating intersections of route sections) may vary depending on the conditions of the problem statement and the features of the location of route points. The route quality criterion is the route length. The method allows using other indicators as a quality criterion. During numerical simulation, it was determined that the dependence of the route length on the number of iterations can be approximated by a decreasing exponent. The indicator of the gain of the route length on the iteration number at which it was achieved was determined to be more informative. This dependence can be approximated by an increasing exponent in the saturation zone (approach to the asymptote). During numerical experiments, from 30 to 3000 tests were performed, which showed that the random values of the gain and the iteration number at which it was achieved obey the normal distribution law. The gain value lies in the range from 0 to 41%, the mathematical expectation of the gain is 16%, and the standard deviation is 8%. The number of iterations required to obtain the best solution ranges from 1 to 25, the mathematical expectation is 9.7, the standard deviation is 4. The Pearson correlation coefficient of the specified random variables is Cor = 0.5009, which indicates their moderate relationship. The modeling was performed in the algorithmic language MatLab.
2,† , and Viktor
The traveling salesman problem (TSP) requires visiting each location exactly once and returning to the point of origin. The route must be built in such a way as to minimize its cost. The cost of the route depends on its length, duration in time, the cost spent on overcoming it, etc. Today, the scope of the traveling salesman problem is expanding and the relevance of the problem is increasing. In this study, the traveling salesman problem is solved for the route of an unmanned aerial vehicle (UAV), which is used to eliminate the consequences of emergency situations.
This study considered the following methods for solving the traveling salesman problem.
Brute Force method [1, 2, 3, 4]. Ordered search method based on the discrete dynamic programming method (Held-Karp algorithm). The disadvantage of the methods is the high requirements for computational resources, which limits the maximum number of route points to 25.
In applied problems with real objects, the solution must be obtained, first of all, in time. Therefore, preference should be given to fast methods, even if they are somewhat inferior in accuracy. At the first stage, we find a reference solution using fast but inaccurate greedy algorithms [5, 6]. Then we refine the reference solution using other methods. A promising direction for improving reference solutions is the use of neural networks, [6, 7, 8, 9, 10]. The prospects of such an approach are promising. The disadvantage is the lack of visibility of the intermediate results of the reference solution improvement procedure. This effectively eliminates the possibility of the operator interfering in the optimization process for atypical sets of route points. Another promising direction is the use of quantum computing [11, 12, 13]. Unfortunately, the corresponding technical means are still capable of providing a solution to the traveling salesman problem for the same number of points as the direct search methods.
More effective in our practical problems are genetic algorithms [6, 14] and local optimization methods such as 2-opt, 3-opt (permutation of segments). Unfortunately, existing approaches to the use of local optimization methods do not pay enough attention to their combination [15]. This is where the potential for rapid improvement of the reference solution lies.
In addition, the combination of methods (stack of methods) forms computational processes, the numerical and qualitative characteristics of which may differ significantly from the characteristics of the individual methods included in the stack of methods. An open question remains the statistical characteristics of the methods, which could help predict the effectiveness of the methods and contribute to the improvement of their characteristics.
The aim of the article is to determine the statistical characteristics of the stack of iterative methods used to improve the reference route. Determining the statistical characteristics is necessary to predict the effectiveness of the methods in terms of the magnitude of the improvement of the reference solution and the number of iterations required for such improvement.
The criterion for route optimization is finding the route with the minimum cost. In our case, cost is the length of the route, which is equal to the sum of the distances between all pairs of points on a particular route.
=
! , − 1 . !(, − 1) = !"#$%&%$,!!!,!
!
! − !!! ! + ! − !"!! ,
(
The iterative methods used in this study to obtain and improve the reference route will be denoted as follows:
NPM - Nearest Point Method allows you to quickly obtain a reference route. 1PM - 1-Point Moving Method improves the reference route by moving individual points. 2PE - 2-Point Exchange Method improves the reference route by exchanging the places of two route points.
DC - Delete Crossing Method improves the reference route by recognizing and eliminating crossings of individual route sections.
If the cycle of methods for improving the optimal route is repeated R times, then the possible scenarios for obtaining and improving the reference route can be presented as follows. + (2 + 1 + ) ∗ . + ( + 2 + 1) ∗ . + (1 + + 2) ∗ . + (2 + + 1) ∗ . + (1 + 2 + ) ∗ .
+ ( + 1 + 2) ∗ .
The most promising scenario for improving the reference solution is scenario (
If certain features of the set of route points are identified, other scenarios may be recognized as
more effective. For example, if the reference trajectory has many intersections of segments, then
scenarios (
The use of each of the methods changes the topological characteristics of the route. The identification of such characteristics may be the basis for choosing a particular method of improving the reference route.
Consider the results of searching for the optimal route for 50 intermediate route points. The results obtained at different iterations at the level of individual methods are presented in Figure 1-3. The reference route, which was found at the beginning of the simulation using the nearest neighbor method, is colored blue. The route, which is improved at the current iteration, is colored red. The starting and ending points of the route coincide (the UAV base) and are marked with two red concentric circles. The last section of the route (return to the base) is represented by a dashed line.
Each of the iterative methods was used until the improvement of the result (reduction of the route length) stopped. Then the cycle of methods was repeated. The general iterative procedure was stopped if no improvement of the result was obtained during the cycle. The dependence of the route cost on the iteration number at the method level has a character that can be approximated by a decreasing exponent (Figure 5).
The route costs that were provided at different iterations are denoted by !, where i –
iteration number, or using an index corresponding to a specific method
( !", !!", !!", !")
(
The corresponding protocol for obtaining and improving the reference route is presented in
To assess the effectiveness of the iterative procedure, the dependence of the gain obtained at each iteration step was used (Figure 6).
= 100% !" − ! / !".
This dependence can be approximated by an exponential that grows and enters the saturation zone. The blue triangle and the red circle mark the beginning and end of the section where the improvement of the iteration results stops. (9)
For other sets of waypoints, the numerical results were different, but had similar qualitative characteristics. For example, consider the procedure for improving the reference route for the set of waypoints presented in Figure 7-8.
The route cost and the gain in terms of route cost depending on the iteration number at the method level also retain an exponential character (Figure 9, 10). The gain in this case exceeded 30%, unlike the previous case (less than 7%).
The location of the route points in the model was chosen randomly using the built-in MatLab rand() function, which produces random numbers according to a uniform distribution law. The results of 30 tests are presented in Figure 11.
As we can see, the largest number of win values lies in the range of 10-20%. The maximum win value is slightly more than 34%. The density pattern of the graphs leads to the idea of the possibility of a normal distribution of the results of modeling the win value for uniformly distributed random sets of route points. For high-quality planning of experiments in the future and more accurate prediction of the results of searching for the best routes, it would be advisable to determine the statistical characteristics of the values that characterize the results of modeling and searching for optimal routes.
For 30 trials, we will plot the distribution of points of the results of the search for optimal solutions in the coordinates of the gain value (ordinate) depending on the iteration number (abscissa) at which this gain was achieved (Figure 12). The search results for each trial are marked with a point. The red segments show the values of the standard deviations for both coordinates. The intersection of the segments corresponds to the mathematical expectations. The blue line is the diagonal of the rectangle, which indicates the area covered by the two standard deviations for both coordinates. = !!!!(! − )(! − ) ,
The Pearson correlation coefficient (Cor = 0.5879) indicates a noticeable, rather strong relationship between the gain value and the number of iterations , which were needed to obtain such a win.
! !
Where – sample number, – number of elements in the sample, !, ! - value of quantities , for a specific sample element, , - mathematical expectations, !, ! - standard deviations of values , .
The corresponding distribution laws of random variables F(x) and the dependence of their probability densities f(x) are presented in Figure 13. With such a small sample, the distribution law of the random variable does not seem to be clearly understandable. The sample must be increased. (10)
The magnitudes of the gain in terms of the route cost depending on the iteration number for 3000 trials are presented in Figure 14. The corresponding distribution laws of random variables F(x) and the dependences of their probability densities f(x) are presented in Figure 15. The dependences visually correspond to the normal distribution law of random variables.
The Pearson correlation coefficient (Cor = 0.5009) in contrast to the smaller sample size is closer to moderate. We cannot increase the quality of the solution by increasing the number of iterations because the number of iterations is not a controlling factor. The number of iterations depends on the features of the location of the route points on the terrain and, accordingly, on the features of the reference trajectory. The iterative procedure is stopped after the quality of the result has stopped improving, and not on the desire of the researcher. Therefore, this value of the Pearson correlation coefficient can be interpreted as follows: if the features of the reference trajectory allow you to get a better quality of the result (a shorter route length), then with a certain probability this will require a larger number of iterations. The size of the gain is in the range from 0 to 41%, the mathematical expectation of the gain is 16%, the standard deviation is 8%. The number of iterations required to obtain the best solution ranges from 1 to 25, the mathematical expectation is 9.7, and the standard deviation is 4. The found indicators allow predicting the results of constructing and improving the UAV reference route for the selected quality criterion.
In this study, the route length was chosen as the route quality criterion. In other problem statements, time, cost, danger, etc. can be chosen as the quality criterion. Also, combinations of the above and other indicators can be chosen as criteria, for example, in the form of a scalar convolution [16, 17].
The paper investigates the features of the procedure for finding and refining the reference route in the traveling salesman problem for a UAV involved in the elimination of the consequences of an emergency.
For the effective use of limited computing resources in field conditions, preference is given to quickly obtaining a suboptimal solution using a greedy algorithm, which is then improved using a stack of iterative methods.
The order of the methods in the stack (moving one point, exchanging two points, and deleting intersections of route sections) can change depending on the conditions of the problem formulation and the features of the location of the route points.
The route quality criterion is the route length. The method allows using other indicators as a quality criterion.
During numerical modeling, it was determined that the dependence of the route length on the number of iterations can be approximated by a decreasing exponent.
The indicator of the gain of the route length from the iteration number at which it was achieved was determined to be more informative. This dependence can be approximated by an increasing exponent in the saturation zone (approaching the asymptote).
During numerical experiments, from 30 to 3000 trials were performed, which showed that the random variables of the win and the iteration number at which it was achieved obey the normal distribution law.
The win value lies in the range from 0 to 41%, the mathematical expectation of the win is 16%, the standard deviation is 8%.
The number of iterations required to obtain the best solution lies in the range from 1 to 25, the mathematical expectation is 9.7, the standard deviation is 4.
The Pearson correlation coefficient of the specified random variables is Cor = 0.5009, which indicates their moderate relationship.
The author(s) have not employed any Generative AI tools.