Abstract. A mathematical model of the applied problem of optimization of closed routes, i.e., the rural postman problem, is constructed. A two-stage method of the type of the branch-and-bound one is proposed that finds a solution or establishes the fact of the unsolvability of the problem. The first stage of the method includes the test of sufficient unsolvability conditions and a vertex-edge transformation procedure. This makes it possible to decrease the time of searching for a solution at the second stage of the method with the help of a proposed modification of the Little method. This procedure uses (for the first time) a partition of a solution set into disjoint subsets with the help of three rules of branching and computation of corresponding lower assessed values of an optimal solution. The proposed method correctly searches for an optimal solution of the Hamiltonian rural postman problem and general and Hamiltonian traveling salesman problems.

Keywords: branch and bound method, traveling salesman problem, postman problem.