Garashchenko I. Modeling and development of methods of cyclic processes optimization on transport networks

This dissertation shows algorithmic features of Symmetric Traveling Salesman Problem (STSP) and Hamilton's Traveling Salesman Problem (HTSP) which need further study: the property of symmetry essentially impacts the time and precision of approximate solution of STSP, while HTSP is not solvable every time. High precision of STSP solution is provided by algorithm structure which consists of two phases. Laboriousness of the approximate solution of STSP depends on algorithmic properties of relaxation and the method of transformation of it. There is proposed two-stage algorithm of HTSP solution, which starts with checking conditions of transport network being not-Hamiltonian, based upon it's structural characteristics. If none of them are positive then branch-and-bound-like algorithm cuts off non-Hamiltonian cycles. For lower estimations calculation there is proposed modified method of assignment problem solution, which determines non-solvability of HTSP at vertexes of tree of branching. The computing experiment and analysis of the got data is conducted.