DEVELOPMENT AND STUDY OF A CENTRALIZED TASK ALLOCATION METHOD IN MULTI-AGENT SYSTEMS
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.
References
Trends Applied Intelligent System. Springer, 2010, pp. 721-730.
2. Han-Lim C., Brunet L., How J. Consensus-based decentralized auctions for robust task allocation,
IEEE Transactions on Robotics, 2009, pp. 912-926.
3. Ping-an G., Zi-xing C., Ling-liY. Evolutionary computation approach to decentralized multi- robot task
allocation, International Conference on Natural Computation (ICNC), 2009, pp. 415-419
4. Khamis A.M., Elmogy A.M., Karray F.O. Complex task allocation in mobile surveillance systems,
J. Intell. Robot. Syst., 2011, 64, pp. 33-55.
5. Gutin G., Punnen A.P. The Traveling Salesman Problem and its Variations. – Springer, Boston, 2007.
6. Braekers K., Ramaekers K. Nieuwenhuyse I. The vehicle routing problem: State of the art classification
and review, Comput. Ind. Eng., 99.
7. Oncan T. A survey of the generalized assignment problem and its applications, Infor, 2007, 45,
pp. 123-141.
8. Van Buer M.G., Woodru D.L., Olson R.T. Solving the medium newspaper production/distribution
problem, European Journal of Operational Research, 1999, 115, pp. 237-253.
9. Carter A.E., Ragsdale C.T. Scheduling pre-printed newspaper advertising inserts using genetic algorithms,
Omega, 2002, pp. 415-421.
10. Kewei Huang, Dingwei Wang. Multiple traveling salesman problem and its application to hot rolling
planning, Application Research of Computers, July 2007, 24 (7), pp. 43-46.
11. Tang L., Liu J., Ronga А., Yang Z. A multiple traveling salesman problem model for hot rolling schedule
in Shanghai Baoshan Iron and Steel Complex, European Journal of Operational Research, 2000,
124 (2), pp. 267-282.
12. Kim K.H., Park Y.M. A crane scheduling method for port container terminals, European Journal of
Operational Research, 2004, 156, pp. 752-768.
13. Sheldon H. Jacobson, Laura A. McLay, Shane N. Hall, Darrall Henderson, Diane E. Vaughan. Optimal
search strategies using simultaneous generalized hill climbing algorithms, Mathematical and
Computer Modelling, 2006, 43, pp. 1061-1073.
14. Evelyn C. Brown, Cliff T. Ragsdale, Arthur E. Carter. A grouping genetic algorithm for the multiple
traveling salesperson problem, International Journal of Information Technology & Decision Making,
2007, Vol. 6, No. 2, pp. 333-347.
15. Harrath Y., Salman A.F., Alqaddoumi A., Hasan H., Radhi A. A novel hybrid approach for solving the
multiple traveling salesmen problem, Arab. J. Basic Appl. Sci., 2019, pp. 103-112.
16. Gomes D.E., Iglésias M.I.D., Proença A.P., Lima T.M., Gaspar P.D. Applying a Genetic Algorithm to
a m-TSP: Case Study of a Decision Support System for Optimizing a Beverage Logistics Vehicles
Routing Problem. Electronics, 2021.
17. Akbay M.A., Kalayci C.B. A Variable Neighborhood Search Algorithm for Cost-Balanced Travelling
Salesman Problem, Proceedings of the Metaheuristics Summer School, Taormina, Italy, 2018.
18. Muñoz-Herrera S.; Suchan K. Constrained Fitness Landscape Analysis of Capacitated Vehicle Routing
Problems, Entropy, 2022, pp. 53.
19. Xu H.L., Zhang C.M. The research about balanced route MTSP based on hybrid algorithm, Proceedings
of the 2009 International Conference on Communication Software and Networks, Chengdu, China,
2009, pp. 533-536.
20. Khoufi I., Laouiti A., Adjih C. A Survey of Recent Extended Variants of the Traveling Salesman and
Vehicle Routing Problems for Unmanned Aerial Vehicles, Drones, 2019, pp. 66.
21. de Castro Pereira S., Solteiro Pires E.J., de Moura Oliveira P.B. A Hybrid Approach GABC–LS to
Solve MTSP, Proceedings of the Optimization, Learning Algorithms and Applications. Springer International
Publishing: Cham, Switzerland, 2022, pp. 520-532.
22. Dorigo M., Birattari M., Stutzle T. Ant colony optimization, IEEE Comput. Intell. Mag., 2006, pp. 28-39.
23. Zhan S.C., Xu J., Wu J. The optimal selection on the parameters of the ant colony algorithm, Bull. Sci.
Technol, 2003, pp. 381-386.
24. Dorigo M. Optimization, Learning and Natural Algorithms. Ph.D. Thesis, Politecnico di Milano, Milano,
Italy, 1992.
25. Gambardella L.M., Dorigo M. Ant-Q: A reinforcement learning approach to the traveling salesman problem,
Machine Learning Proceedings 1995. Elsevier: Amsterdam, The Netherlands, 1995, pp. 252-260.
26. Dorigo M., Gambardella L.M. Ant colonies for the travelling salesman problem, Biosystems, 1997,
pp. 73-81.
27. Bullnheimer B., Hartl R., Strauss C. A New Rank Based Version of the Ant System—A Computational
Study, Cent. Eur. J. Oper. Res., 1999, pp. 25-38.
28. Guntsch M., Middendorf M. A population based approach for ACO, Proceedings of the Workshops on
Applications of Evolutionary Computation, Kinsale, Ireland, 3–4 April 2002. Springer: Berlin/
Heidelberg, Germany, 2002, pp. 72-81.
29. Lah Ivo. A new kind of numbers and its application in the actuarial mathematics, Boletim do Instituto
dos Actuários Portugueses, 1954, pp. 7-15.
30. de Castro Pereira S., Solteiro Pires E.J., de Moura Oliveira P.B. Ant-Balanced Multiple Traveling
Salesmen: ACO-BMTSP, Algorithms, 2023, pp. 37.
