Levchenko A. Calculations' acceleration methods in problems of optimal routing

Object of research - closed routes that provide delivery of cargo, passengers, information messages and efficiently using the capabilities of transport networks. The aim of research - to develop and improve optimization methods of closed routes in transport networks to improve efficiency of transport of passengers and cargo. Research methods - the results of graph theory for finding the forest trees, articulation points, bridges, methods of constructing shortest paths in graphs, elements of the matching theory for solving of a variant of the assignment problem, which is used as a relaxation for a branch and bound methods, solution methods of integer optimization problems for comparative analysis of the developed methods, elements of algorithms complexity theory of to evaluate the complexity of constructing the closed routes. Equipment - personal computer. Theoretical and practical results of research - mathematical models of tasks and their solution methods aimed at economically reasonable search of closed routes. Scientific novelty - The exact method for solving the traveling salesman problem with total effective procedure of reduction to a set of subproblems of lower dimension; procedure inhibits growth of solution time, which caused by increasing of the input problem's volume; first developed an approximate Common Travelling Salesman Problem solution method with measured by the third degree polynomial order of the input matrix complexity, and a relative error represented by a constant. The method is designed to solve the real-time routing tasks with acceptable accuracy and high speed$ was further developed branch and bound method for solving traveling salesman problems class. Modification surpasses the performance of the method Little by quick calculation of more accurate value of the lower bound of the desired route, which is set in the result of solution of one variant of the assignment problem, and by storing extremely limited list of data in the vertexes of the enumeration tree. The results of the thesis are implemented in Novograd Volynsky area consumers' union, Zhytomyr region. The results are used in the educational process in the "Software Engineering" direction in teaching courses "Computer Discrete Mathematics", "Mathematical Methods of Operations Research", "Basic mathematical programming", in laboratory practice, the course and diploma projects. Scientific theoretical and practical results of the thesis can be used: developed software capable to solve applied problems of management of transport carriage of goods and passengers in the wild.