COMPUTER SCIENCE

The choice of algorithms for solving a multi-agent routing problem based on solving related problems

M. G. Kozlova, V. A. Lukyanenko, O. O. Makarov

V. I. Vernadsky Crimean Federal University, prospekt Akademika Vernadskogo, 4, Simferopol, 295007, Russia

Abstract: The paper considers the problem of reducing the complexity of $NP$-hard problems by using related problems for which an optimal or acceptable solution is already known. For multi-agent routing tasks, a technique is used based on network clustering consistent with traveling salesman routes on each cluster and constructing routes that take into account the limitation of delivery time windows. A mathematical model is presented that corresponds to a block of pseudo-Boolean conditional optimization with constraints in the form of disjunctive normal forms that allows polynomial solvability and a block of time constraints. The results of choosing metaheuristics based on related problems are used in a program for the delivery of goods by many agents to consumers located at the vertices of the regional infrastructure road network.

Keywords: multi-agent traveling salesman problem, time windows, metaheuristics, applied routing problem

UDC: 004.89, 519.157, 519.161

MSC: 90C27

Received: 16.07.2024
Accepted: 10.08.2024

DOI: 10.35634/vm240309

Bibliographic databases:

•