ON THE APPLICATION OF THE MINIMAX TRAVELING SALESMAN PROBLEM IN AVIATION LOGISTICS

Abstract

We consider the problem of organizing a system of movement between the given points (cities) under conditions of resource constraints and in the presence of precedence conditions. The solvability conditions for this problem are extracted from the solution to the minimax traveling salesman problem (the bottleneck problem) without resource constraints. The solution to this extreme routing problem is determined on the basis of a broadly understood dynamic programming in its “non-additive” version. Possible applications may be related to the formation of the route of a vehicle (airplane or helicopter) in order to organize a transportation system in conditions of fuel shortage; it is assumed that in addition to the mandatory visits to all points, there are requirements for the passing movement of goods between some of the points, which creates additional restrictions (precedence conditions). To solve an auxiliary extremal problem, an optimal algorithm is constructed and implemented on a PC. © 2023 South Ural State University. All rights reserved.