Morozov A. Improvement of methods of circular route optimization in transport network

Object of research - closed processes which provide the effective functioning of transport vehicles and networks. Research subject - mathematical models and methods for solving problems of construction of optimal circular routes, which reduced the problem of efficient functioning of transport processes and systems. The purpose of this work is to build mathematical models and methods for solving optimization problems of new circular routes for the transport network that will improve transportation of passengers and loads. The methods of research are based on graph theory - for finding the shortest routes, cutpoints and bridges; matching theory - for determining unsolvability of problems; elements of complexity theory of combinatorial problems - to evaluation the complexity of algorithmic procedures, mathematical methods of operations research - for the analysis of existing and developing new methods of solving NP-complete problems. The results of theoretical researches and developed mathematical models are implemented as a software product, which has been used to conduct a computational experiment. The scientific novelty - for the first time is formulated and constructed mathematical models of Hamiltonian Rural Postman Problem and Circular Rural Postman Problem, which complement the class problems of construction of optimal closed routes; was devoted the two-stage method which allows to find the optimal solution of Hamiltonian Rural Postman Problem and Circular Rural Postman Problem or detect that the set of plural solutions of problem is empty, the basis of the method is the algorithm of vertex-edge conversation and using the branch-and-bound method; was devoted the Litte's method to solving Hamiltonian Rural Postman Problem and Circular Rural Postman Problem in the construction of new branching rules and lower bounds for computing solution for every type of problems. Results of the thesis implemented at JSC "Agrotonprom" and Experimental and Production Base in city Brovary of OJSC "V. ShimanovskyUkrRDIsteelconstruction". Research results are used in the learning process of Zhytomyr State Technological University on "Software Engineering" in teaching subjects "Mathematical Methods of Operations Research", "Discrete Mathematics, Algorithms and data structures", in the laboratory practicum, with course and degree planning. Science and practice results of the dissertation may be used: by companies and organizations whose activities are related to the necessity of construction of circular routes; by educational institutions and organizations that conduct research on methods of combinatorial optimization; in the educational process at preparation of specialists in industry of mathematical modelling and control systems.