Determination of the optimal set of methods for iterative improvement of the reference route

Abstract

The article solves the problem of a traveling salesman for planning a flight of an unmanned aerial vehicle in the conditions of eliminating the consequences of an emergency. An approach is considered that uses a combination of the nearest point method to create a reference solution and a number of methods of local variations of route points to improve the reference solution. The following methods are included in the reference solution improvement scenario: 1. 1PM - moving 1 point, 2. 2PE - exchanging places of 2 points and 3. DC - eliminating intersections of route segments. When improving the reference solution, the best result is obtained by combining several methods. The quality of route improvement depends on the type of route and the scenario (the set and sequence of methods included in the scenario). The results of the analysis of different scenarios of using reference solution improvement methods are summarized in the form of ordinary graphs and heat diagrams. Route maps are constructed for different scenarios of improving the reference solution. The most effective combinations of methods in the scenarios were 1-3, 3-1, 1-1. The worst combinations: 2-2 and complete repetitions of other methods 1-1-1, 2-2-2, 3-3-3. The magnitude of the gain in improving the quality of the route varied in the range from 1 to 28%, in most cases from 6 to 19%. This required from 2 to 24 iterations, in most cases from 20 to 24 iterations. The Euclidean distance, the hazard coefficient and the Euclidean distance with a multiplier in the form of a logistic function of the hazard coefficient were considered as the cost of the route. The method is designed for the limited computational capabilities of conventional business computers. When iteratively refining the solution, the methodological approach allows you to control the computational procedure in real time and complete it either upon reaching the specified accuracy or when time runs out. The model is created in the algorithmic language Matlab.

Prombles in programming 2025; 3: 19-28