This article is cited in 1 paper

Optimization, System Analysis, and Operations Research

Searching for a sub-optimal solution of the dynamic traveling salesman problem using the Monte Carlo method

A. A. Galyaev, E. A. Ryabushev

V. A. Trapeznikov Institute of Control Sciences of Russian Academy of Sciences, Moscow

Abstract: 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.

Keywords: moving targets traveling salesman problem, combinatorial optimization, interception in simple motions, Monte Carlo algorithm.

Presented by the member of Editorial Board: A. A. Lazarev

Received: 05.10.2023
Revised: 04.12.2023
Accepted: 21.12.2023

DOI: 10.31857/S0005231024020065

 English version: Automation and Remote Control, 2024, 85:2, 162–173