Search

Search Results

• DEVELOPMENT OF A METHOD FOR SOLVING THE PROBLEM OF TASK ALLOCATION IN A MULTI-AGENT SYSTEM

  V.А. Kostyukov , F.А. Houssein

  144-155

  2025-10-01

  Abstract ▼

  This paper considers the problem of task distribution within a multi-agent system, where each agent is an autonomous robot, and each task corresponds to a point in a two-dimensional environment that one of the agents must visit. This problem is essentially similar to a multi-agent version of the classical traveling salesman problem, where several agents are involved instead of one participant. Each of them must go through a unique route covering a certain set of points. In this regard, a study of the multi-agent traveling salesman problem is conducted as one of the formats for setting the problem of distributing goals among agents. This problem is of great importance in the field of routing and optimal task distribution. Its solution includes two closely related subproblems: determining the set of points assigned to each agent and constructing the optimal route for visiting them. There are three main approaches to solving this problem in the scientific literature: Optimization approach, where both subproblems are solved jointly; Cluster-First, Route-Second model, where tasks are first distributed among agents, and then routes are built;
  The Route-First, Cluster-Second model assumes initial optimization of the route for all points with its subsequent division between agents without changing the order of visits. In this paper, a hybrid method is proposed that combines elements of the Cluster-First, Route-Second and Route-First, Cluster-Second approaches. The goal is to combine the strengths of both concepts and minimize their drawbacks. To test the effectiveness of the developed method, a comparative study was conducted. The evaluation was carried out according to three main metrics: the time spent on constructing a solution, the total length of all routes, and the maximum route length among all agents. The experimental results showed that the use of the proposed method allows for a reduction in the maximum route length (thereby reducing the load imbalance between agents) by an average of 26%.

• HYBRID METHOD FOR SOLVING THE MULTI-AGENT TRAVELING SALESMAN PROBLEM

  V.А. Kostyukov, F.А. Houssein

  2025-04-27

  Abstract ▼

  In this research work, the problem of task allocation in a multi-agent system is considered, where
  each agent is a robot, and each task is represented by a position, which should be visited by one agent.
  This problem is very similar to the multi-agent traveling salesman problem, which, unlike the famous traveling
  salesman problem, involves several traveling salesmen who visit a given number of cities exactly
  once and return to the starting position with minimal travel costs. Therefore, the multi-agent traveling
  salesman problem is analyzed as a representative of the task allocation problem. The multi-traveling
  salesman problem is important for the field of route optimization and task allocation between several
  agents. It includes two different, but interrelated subproblems: distribute cities among agents and determine
  the order in which each agent visits cities. In the literature, there are 3 concepts for solving this
  problem with respect to solving its two constituent subproblems: the optimization concept, where both
  subproblems are solved simultaneously; The Cluster-First, Route-Second concept is where the question of
  which tasks to assign to which salesman is first decided, and then the question of the order in which each
  salesman solves his tasks is decided; The Route-First, Cluster-Second concept is where the question of the
  order in which tasks should be visited is first decided, and then this cycle is divided between agents without
  changing the order of visits in order to answer the question of which tasks each agent takes on. This
  paper proposes a hybrid approach to solving the multiple traveling salesman problem (mTSP), which
  combines the ideas of two well-known concepts: "First clustering, then routing" and "First routing, then
  clustering" in order to obtain their positive aspects and get rid of their weaknesses. To evaluate the effectiveness
  of the developed method, a comparative study was conducted using the classical method for solving
  the multi-traveling salesman problem. The results were evaluated based on three key criteria: the
  computational time to obtain a solution to the multi-travelling salesman problem, the total length of the
  routes travelled by the salesmen, and the maximum route length among them. The analysis of the experimental
  data showed that when using the proposed method, the maximum path length among the routes
  travelled by the agents (load imbalance) is reduced by an average of 26%.

• DEVELOPMENT AND STUDY OF A CENTRALIZED TASK ALLOCATION METHOD IN MULTI-AGENT SYSTEMS

  F. А. Houssein

  2024-10-08

  Abstract ▼

  This study provides a comprehensive analysis of the multi-traveling salesman problem, which is an
  extended version of the classical traveling salesman problem. In contrast to the latter, the multi-traveling
  salesman problem involves the participation of several traveling salesmen, each of whom must visit a certain
  number of cities exactly once and return to the starting point, while minimizing travel costs. The multi-traveling salesman problem is of significant interest in the field of route optimization and task distribution
  among multiple agents. The main goal of the research is to develop an effective method for solving
  this problem, which will reduce execution time and optimize the use of resources. As part of the study, an
  innovative method was developed, which is based on reducing the dimension of the solution space. This
  method allows you to more effectively distribute the load and manage resources, which ultimately helps
  reduce the overall time to complete tasks. One of the key features of the proposed method is its versatility
  and adaptability to various scenarios, including situations with varying numbers of tasks and traveling
  salespeople. A detailed study of the proposed method was also carried out from the point of view of the
  influence of its hyperparameters (pheromone evaporation coefficient, number of iterations, number of
  ants) on the quality of the solution and calculation time. To evaluate the effectiveness of the new method, a
  comparative study was conducted using the classical method for solving the multi-traveling salesman
  problem. The results were assessed according to three main criteria: the computation time for solving the
  multi-traveling salesman problem, the total length of the routes traveled, and the maximum route length
  among all traveling salesmen. Analysis of experimental data showed that the developed method significantly
  exceeds the classical one in all key indicators. These results confirm the high efficiency of the proposed
  method and its promise for practical application in various fields that require optimizing routes and
  distributing tasks among several performers. Thus, the study demonstrates that the developed method has
  significant potential for improving routing and resource allocation processes. Its application can significantly
  increase efficiency in various areas where coordination of the work of several agents is necessary,
  such as logistics, transport systems and other areas related to route optimization.

• A METHOD FOR SOLVING THE MULTI-TRAVELING SALESMAN PROBLEM IN AN ENVIRONMENT WITHOUT OBSTACLES BASED ON REDUCING THE SIZE OF THE SOLUTION SPACE

  V.А. Kostyukov, F. А. Houssein, I.D. Evdokimov

  2024-04-15

  Abstract ▼

  This research paper analyzes the multi traveling salesman problem, which, unlike the famous
  traveling salesman problem, involves several traveling salesmen who visit a given number of cities exactly
  once and return to their original position with minimal travel costs. The multi-traveling salesman
  problem is an important problem in the field of route optimization and task distribution among multiple
  agents. The main goal of the study is to develop an effective method for solving this problem, which will
  reduce task completion time and optimize the use of resources. During the study, an innovative method
  was created based on reducing the dimension of the solution space. This method allows you to more
  efficiently manage workload and resources, which in turn helps to minimize the overall execution time of
  tasks. A special feature of the method is its versatility and applicability in various scenarios, including
  situations with different numbers of tasks and traveling salespeople. This approach provides broader
  coverage and allows the applicability of the method to be assessed in different contexts, which is an
  important strength of this study. To evaluate the effectiveness of the developed method, a comparative study was conducted using the classical method for solving the multi-traveling salesman problem. The
  results were evaluated based on three key criteria: the calculation time for solving the multi-traveling
  salesman problem, the total length of the routes traveled by the traveling salesmen, and the maximum
  route length among them. Analysis of experimental data showed that the developed method significantly
  exceeds the classical approach in all considered criteria in most experiments, since when using the
  proposed method, the average time for calculating a solution to the multi-traveling salesman problem is
  reduced by 56%, while the average sum of the lengths of routes traveled by traveling salesmen is reduced
  by 12%. In addition, the maximum path length among the routes traveled by agents (load imbalance)
  is reduced by 8%, which confirms the high efficiency of the proposed method and its promise for
  practical application in various fields where optimization of routes and distribution of tasks among
  several executors is required