Modification of the Integer Branch and Bound Method for Solving of a Two-Dimensional Routing Task of an Aircraft Group's Coordinated Flight

Abstract

Below is a solution for a direct-sales representative in case of a two-dimensional routing of a flight, which differs by formation of two initial matrixes of the distances between the points of two unlinked routes, which are analyzed in turn with a coordinated selection of the element of the minimal length in each of them. In comparison with the known branch and bound method, there is no need in an additional choice for an alternative, which is essentially new in the solved task - to which of the two routes the element should belong to. For this purpose it is necessary to know, to what route it is closer to, and for evaluation of this proximity two criteria are used: - at the first stage of calculation on each step it is the calculation of the minimal distance from an element to the center of gravity of each of the routes by using the triangular model of approximation of the flight trajectory. This allows us to part gradually step by step the centers of gravity at a certain distance, sufficient to continue the calculations; - at the second stage of calculation, the minimal distances from the element to the approximated trajectories of each route are calculated, which allows us to refuse in case of their equality in general accession of the element to any route and by that to avoid an unnecessary inclusion of the crossing points between them. Examples of the calculations proving the efficiency of the offered approach and indicating reduction of the performance of the flight of points more than twice are presented.