The work develops 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 UAV must sequentially fly around a certain number of route points. Each point must be visited only once. The UAV returns to the same point from which it started. This task can be classified as a traveling salesman problem (TSP). At the beginning of the work, an analysis of existing research on solving the traveling salesman problem was performed. Methods of complete direct search, the method of ordered search based on a discrete dynamic programming procedure (Held-Karp method), integer linear programming methods, greedy algorithms, and local optimization methods were considered. A conclusion was made regarding the feasibility of solving the problem of constructing an optimal route using a combination of greedy algorithms and iterative methods for improving the solution. The resulting solution is not guaranteed to be optimal, but is close to optimal, that is, suboptimal. At the first stage of calculations, a reference trajectory is obtained using the greedy nearest neighbor algorithm. Then, local optimization methods are used to improve the reference trajectory. The methods of moving one point, exchanging two points, and deleting intersections of route sections are used as local optimization methods. During the search computational procedure, individual methods of improving the reference solution can enter local optimum, from which they cannot then escape. A combination of different methods allows you to leave local optimum, bypass ravine areas, and approach the global optimum. The use of iteration methods in the stack loop allows you to quickly find optimal UAV trajectories. The speed of the algorithms allows you to calculate the optimal route not only before the flight, but also to recalculate it during the flight, in case of a change in the task or the conditions for its execution. The performance of the proposed approach was tested by creating a model in the MatLab environment.
The problems of constructing optimal routes have appeared a long time ago: the problems of delivering goods by transport, delivering mail by postmen, delivering goods by traveling salesmen, etc. According to the last type of delivery, the problem was called Traveling Salesman Problem (TSP). These problems require routes that save time, money, etc. At the same time, the traveling salesman had to visit each point only once, and also finish at the point from which he started. The relevance of the problem has not decreased over the years. On the contrary, it has increased. Therefore, the relevance of methods for solving the problem is only growing. In this study, the TSP is solved to form the optimal route of an unmanned aerial vehicle (UAV), which is used to eliminate the consequences of an emergency.
Let us consider the main methods for solving the TSP for a route with n points to be visited.
The Brute Force method has a computational complexity of (n-1)! (for the symmetric case, the
cost of a route section is (n-1)!/2) [
Linear programming methods can be considered classical. They have a clear mathematical
formalization of the problem statement in the form of an integer linear programming problem.
Unfortunately, they also require a lot of computational resources and can lose even to direct
bruteforce methods. These methods can be effective in the case of a certain set of constraints of a special
type, which can lead to a decrease in the order of the problem (branch-and-bound method) [
Let us clarify the features of the statement of the applied TSP: 1. 2.
The solution does not necessarily have to be perfectly accurate. It can be close to accurate, that is, not optimal, but suboptimal.
But the solution must be timely, even if you have to pay for it with accuracy.
Conclusion: you need to use methods or a combination of methods that provide an acceptable solution in an acceptable time. To do this, at the first stage it is necessary to quickly find a reference solution, which can then be refined using other methods.
Greedy algorithms are fast, but inaccurate [
In [
Analysis of existing studies allowed us to draw the following conclusions: 1. For a large number of route points (more than 20-30), methods of direct enumeration of all options and even methods of ordered enumeration of options such as the discrete Bellman procedure consume too much computational resources. 2. Greedy algorithms (Nearest Point Method) are the most economical in terms of machine resources, but inefficient in terms of solution quality. 3. It seems advisable to quickly build a reference solution using greedy algorithms with further improvement of the reference solution using special iterative methods. 4. The method of improving the reference trajectory by sequentially moving individual route points to new places in the sequence of route points cannot be considered sufficient. Therefore, it would be advisable to supplement (combine) it with other methods of improving the reference solution.
The aim of the article is to improve the quality of route construction by quickly building a reference solution and its further improvement by cyclic application of a stack of special iterative methods. The task is to develop or adapt existing methods, as well as to determine the scheme of their joint (sequential) use and to determine the criteria for stopping the iterative process.
A reference route is one that is constructed using simplified and, accordingly, fast methods. For example, greedy algorithms (NPM, Nearest Point Method) are such. In the future, the reference solution must be refined using other methods that do not require a large amount of computing resources. To find the distance between two points, we use the Euclidean measure !(, ) = ! − ! !
! + ! − ! , where , j - point numbers; , - coordinates of points.
In general, instead of distance, the cost of passing a route section should be used (1) (2) (3) (4) (5) (6) =
! , − 1 .
!"#$%&%$,!!!,! The procedure for finding the route length is the same for the reference and improved routes.
, = ! , .
The cost of passing a route section may include: distance, energy consumption, UAV resource
use, probability of damage or destruction of the UAV, probability of other incidents, probability of
failure to complete the task, etc. The cost can also be found as a certain aggregation of a certain set
of factors (listed or others). For this, scalar convolutions can be used, for example, additive,
multiplicative, others or a combination thereof [
In the study, we distinguish the following sets of route points:
LocationSet. An unordered set of route point numbers that are assigned to certain locations in a list sequentially or in random order
= {1, 2,3, … . . }.
RouteSet. An ordered set of route points (tuple) that consists of the same points, but now arranged in an order that corresponds to a specific route.
= (3,7,1, … . .4, , 10, … ).
The cost of such a route is equal to the sum of the costs of passing all sections between neighboring points.
=
, − 1 .
!"#$%&%$,!!!,!
In this study, we assume that the cost of a route is equal to its length, as the sum of the distances between neighboring sections.
Improvement of the reference route can be performed using various methods. Let's analyze those used in this study.
We have already considered the 1PM method above when analyzing the publication [
But previous shuffling can make certain successful solutions unavailable for the procedure of subsequent shuffling. By analogy with gradient search procedures, we can say that the search can enter a local optimum, which is separated from the global optimum by a ravine. The way out of this situation is to shake (shuffle) the route tuple using other methods that allow you to bypass or jump over the ravine.
This is exactly what the 2PE method may be in many cases, analyzing the feasibility of exchanging two points in a tuple describing a route. This procedure analyzes the exchange of points for all possible pairs of points. The procedure can be repeated several times. The disadvantage of the method is that it can create new intersections of route sections (segments), which immediately indicates its non-optimality. Such a newly formed intersection can appear with the participation of points that have already been analyzed and therefore do not fall into repeated checks. It would be desirable to have a separate method that eliminates only intersections of route sections and does not touch other points that are not related to the intersection.
The DC method is aimed at eliminating intersections of route sections (Figure 1, 2). The method can be considered a special case of the 2PE method. The advantage of the method is that it purposefully eliminates only intersections. There remains a small probability that the elimination of one intersection will form a new intersection. But this probability is significantly less than in the 2PE method.
Even based on visual analysis, it can be concluded that the exchange of points i2, i3 should lead to a reduction in the length of the route (Figure 1, 2). Since the elimination of one intersection can form another intersection, the result of each replacement is checked for a reduction in the length of the route. Let us consider the calculated dependencies. The equations of the lines passing through the corresponding pairs of points before the elimination of the intersection have the form (7) (8) (9) (10) (11) (15) (16) == !!"" ++ !!"".
Substitute the coordinates of the node points ! = !"! + !" ; ! = !"! + !" We find the coefficients ! = !"! + !".
! = !"! + !" ! − ! !" =
! − ! ! − ! We write the equation for the intersection point p5.
; !" = ! − !"!; !" = ! − ! ; !" = ! − !"!.
Subtract the upper equation from the lower one.
0 = ! !" − !" + (!" − !").
Convert. Find the coordinates of the intersection point !! == !!""!! ++ !!"". (12) ! = − !" − !" ; ! = !"! + !".
!" − !"
Next, we need to make sure that the intersection point really lies on the segments, and not on their imaginary extension. To do this, we find the minimum and maximum abscissas and ordinates for each pair of points (for each segment) !"!"# = !, ! ; !"!"# = !, ! ; !"!"# = !, ! ; !"!"# = !, ! ; !"!"# = !, ! ; !"!"# = !, ! ; !"!"# = !, ! ; !"!"# = !, ! .
A sign that the intersection point lies on the segments is the simultaneous fulfillment of the following conditions (13) !"!"# ≤ !; !"!"# ≤ !; !"!"# ≥ !; !"!"# ≥ !; (14) !"!"# ≤ !; !"!"# ≤ !; !"!"# ≥ !; !"!"# ≥ !.
Analysis of Figure 1 shows that it is sufficient to perform the check on only one coordinate. This will significantly reduce the computational load.
!"!"# ≤ !; !"!"# ≤ !; !"!"# ≥ !; !"!"# ≥ !.
Reducing the computational load can also be achieved by replacing conditions (13), (14) with checking the distances between points along one coordinate.
! − ! ≥ ! − ! ; ! − ! ≥ ! − ! ; |! − !| ≥ |! − !|; |! − !| ≥ |! − !|.
If conditions (13), (14) or (13), (15) or (16) are met, then points i2 and i3 are swapped. It is clear that such a modification of the route may not be final. The method can be applied repeatedly until the condition for stopping the iterative procedure is met.
Let us pay attention to the fact that the proposed approach to improving the reference solution provides for several levels of iterative procedures:
Level 1. Iterations at the level of route points (within the method). All possible route change options are reviewed with an analysis of possible changes for all points or all pairs of route points.
Level 2. Iterations at the level of individual methods. One iteration includes a single application of a separate method for all points or all pairs of route points (one of the methods: 1PM, 2PE, DC). And such iterations at the level of one method can be repeated.
Level 3. Iterations at the level of a set of different methods. One iteration includes the sequential execution of components of a certain set of methods, represented by a tuple (2PE, 1PM, DC). If the sequence of methods can be repeated R times, then the scenario for creating and refining the reference solution can be represented by the following chain of methods
+ (2 + 1 + ) ∗ .
The order of the 1PM, 2PE, DC methods may vary depending on the specifics of the route and the experience of the researcher. It can also be changed in different iterations at the level of the set of methods. (17)
The stopping conditions of the reference route refinement procedure are used only for Iterations at the level of individual methods and for iterations at the level of a set of methods.
The condition for stopping the iterative procedure at level 2 (of a separate method) is the equality of the results of two consecutive iterations of this method.
() = ( − 1).
After that, the transition to the next method in the tuple occurs (2PE, 1PM, DC).
The condition for stopping the iterative procedure at level 3 (set of methods) is the equality of the results of all methods within the current iteration at level 3
2() = 1() = ().
The proposed approach was tested in the MatLab software environment. Let us consider the results of the simulation by iterations at level 2 (separate methods) for a route including 50 points (Figure 3-6). The red circle indicates the location of the base from which the UAV takes off and returns to. The blue line indicates the reference route that was built using the greedy algorithm, the red line is the route obtained as a result of improving the reference route at this iteration at level 2.
Figure 7 shows the results of the numerical experiment. To the left of the equal sign is the abbreviated name of the method used. To the right of the equal sign are the route lengths that were achieved using this method at each iteration of level 2. The protocol of using the reference route improvement methods (Figure 7) shows that the 2PE method reached its potential already at the second iteration of level 2, the 1PM method implemented 4 successful iterations, and the DC method successfully worked only once. In the next iteration cycle of level 3 (multiple methods), the 2PE method was unable to add any improvements to the solution in the iterations of level 2. But after that, the 1PM method successfully implemented two iterations of the reference route improvement at level 2. Further repetitions of using the methods did not bring any improvements. (18) (19)
The numerical experiment allows us to draw the following conclusions: 1. Changing methods can improve the result. 2. In some cases, the result can be improved by a method that seemed to have already done everything it could in the previous iteration (for example, 1PM. Otherwise, it may be another method).
The paper presents approaches to solving the TSP for constructing a UAV route involved in eliminating the consequences of emergency situations.
The resulting solution is not guaranteed to be optimal, but is close to optimal, i.e. suboptimal.
At the first stage of calculations, a reference trajectory is obtained using a greedy nearest neighbor algorithm.
Then, local optimization methods are used to improve the reference trajectory.
The methods of moving one point, exchanging two points, and eliminating intersections of route sections are used as local optimization methods.
During the computational procedure, individual methods of improving the reference solution may enter local optimum, from which they cannot then escape. A combination of different methods allows you to exit local optimum, bypass ravine areas, and approach the global optimum.
Using a stack of iteration methods in a loop allows you to quickly find suboptimal UAV trajectories.
The speed of the algorithms allows you to calculate the optimal route not only before the flight, but also to recalculate it during the flight, in case the task or the conditions for its execution change.
The author(s) have not employed any Generative AI tools.