Matsyi O. Mathematical modeling and optimization methods of closed routes in transport type problems

The object of research – closed routes in tasks of transport type. The purpose of the work is to develop and modify mathematical methods for finding optimal closed routes in transport type tasks. Research methods – the elements of the graph theory were used to construct a routing model and improve the methods for solving the problem of assignment, the problem of finding the 2-factor of minimum weight and individual cases of Vehicle Routing Problem (VRP), combinatorial optimization methods for developing Littl's algorithm modification, the basics of complex theory to assess the complexity of the developed methods. Practical results - developed models and methods of optimization focused on improving the organization of transportation in real time and in real conditions of traffic. The scientific novelty of the obtained results is as follows: for the first time, the recurrent method of solving the problem of appointment, which contains fast-by-time parameters of the procedure for constructing the shortest increment path in the weighted graph of the transport network, is first proposed, which is achieved in the speed of computing before other methods of optimization of the closed routes; the recurrent method of constructing weighted pair combinations is improved, on the basis of which a 2-factor of minimum weight is constructed with the least temporal complexity at the present time as a result of the reduction of the 2-factor to a limited task of appointment; For the first time, the modification of Little's algorithm, aimed at reducing the time for solving transport-type problems, is proposed for the first time. It contains one of the individual cases of finding the 2-factor of minimum weight for the rapid calculation of more accurate estimates of the limits of the desired optimum. The research of this thesis work was carried out within the frame of scientific and technological work of the Kharkov National Automobile and Highway University. The research findings, on which this thesis work is based, have been obtained during realization of scheduled budget programs and projects of Kharkov National Automobile and Highway University. The results of the research have been implemented in the educational process of the Department of Computer Technologies and Mechatronics of Kharkov National Automobile and Highway University in curriculum modules "System Analysis" and "Operations research". Also, the results obtained are implemented in the development of Karsis Npp Tov (Kharkiv).