Searching for a Sub-Optimal Solution of the Dynamic Traveling Salesman Problem Using the Monte Carlo Method

The problem of drawing up a bypass plan for targets moving rectilinearly to one point for simple movements of an interceptor (traveling salesman) is considered. A new criterion of the problem is proposed based on the initial partition of the possible intercept area, as well as an algorithm for finding a sub-optimal bypass plan based on the construction of a solution search tree by the Monte Carlo method. A numerical implementation of the algorithm has been developed, modeling has been carried out and the obtained plans for bypassing targets have been statistically analyzed.