Chorna O. Mathematics models and optimization methods on cyclic permutations and their applications

The paper investigates models and methods of combinatorial optimization that use the properties of a set of cyclic permutations and their application for solving scientific and applied problems, including the vehicle routing problems. The properties of cyclic permutations under their mapping into Euclidean space are investigated. The polyhedral properties of permutations and cyclic permutations corresponding to the subset of vertices of the permutation polytope are 22 used. A class of adjacency transpositions is introduced for permutations of various elements, whose representatives generate permutations corresponding to adjacent vertices of the permutation polytope. The properties of adjacency and the peculiarities of changing the cyclic structure of permutations under the influence of adjacency transpositions are described. The classification of cyclic permutations is carried out depending on the influence of adjacency transpositions on their cyclic structure. The corresponding statements about the properties of adjacency transpositions are proved. Methods for solving optimization problems for linear functions on the set of cyclic permutations, in particular, with linear constraints, have been further developed. An approach based on a combination of the branch-and-bound algorithm and heuristics is proposed to solve the problem without constraints. A method is proposed for finding an approximate solution to the problem without constraints using the properties of adjacency transpositions. To solve the problem of optimization of linear functions on the set of cyclic permutations with linear constraints, a method is proposed based on random search, using adjacency transpositions to solve an auxiliary problem. The method of combinatorial optimization based on cyclic transfers has been further developed in terms of generating cyclic transfers of negative value. The method is applied to improve the solutions obtained using heuristics of transport routing problems, in particular, the Pickup and Delivery Problem. The software has been developed that implements the proposed models and methods of combinatorial optimization, to solve the problems studied in the work. The results of numerical experiments are represented, the analysis of the results is carried out, confirming the effectiveness of the proposed approaches. The results obtained can be used in computer modeling and solving problems in the fields of data archiving and cryptography, quantum computing, bioinformatics. Keywords: combinatorial optimization, cyclic permutations, transpositions, permutation polytope, adjacency transpositions, linear function, branch-and-bound algorithm, heuristics, pickup and delivery problem.