DETERMINATION OF THE OPTIMAL CIRCULAR ROUTE PASSING THROUGH THE GIVEN SET OF POINTS ON THE MAP

Abstract

The subject of research is the methods and information technologies of transport logistics. The goal is to reduce costs and time for delivery of goods by road through the development and implementation of effective methods and algorithms for finding the optimal route for delivering goods. The article deals with the task of finding the optimal ring route for the delivery of goods from the warehouse, passing through a given set of points on the map. Methods and algorithms of discrete mathematics are used to solve the problem. The following results were obtained. The analysis of the problem and the existing methods of discrete mathematics for its solution were carried out. The disadvantages of these methods are determined. A heuristic algorithm for solving the problem that implements the proposed solution method has been developed. The solution of the considered problem is reduced to the problem of finding a Hamiltonian cycle on a new graph of smaller dimension. The new graph is constructed from the initial graph describing the map, and consists of the vertices of a given set of points on the map, through which the route must pass. Each arc in a new graph connects a pair of vertices if there is a path between those vertices in the initial graph. The arc is weighted by a number that determines the minimum distance between the vertices in the initial graph it connects. Dijkstra's algorithm is used to construct the graph. Conclusions: the proposed method for solving the considered problem performs its reducibility to the classical problem of discrete mathematics of search for a Hamiltonian cycle on a graph. Testing of the developed program showed the efficiency of the proposed method and algorithm for solving the problem. The developed method makes it possible to reduce the dimension of the problem to be solved, since the solution is sought on a new graph of smaller dimension in contrast to the graph describing the original map. The factor of dimension reduction significantly reduces the cost of finding a solution and increases the chances of finding the best route for the delivery of goods.