A METHOD FOR SOLVING THE MULTI-TRAVELING SALESMAN PROBLEM IN AN ENVIRONMENT WITHOUT OBSTACLES BASED ON REDUCING THE SIZE OF THE SOLUTION SPACE
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
References
2007.
2. Braekers K., Ramaekers K. Nieuwenhuyse I. The vehicle routing problem: State of the art classification
and review, Comput. Ind. Eng., 99.
3. Oncan T. A survey of the generalized assignment problem and its applications // INFOR:
Information Systems and Operational Research. – 2007. – Vol. 45. – P. 123-141.
4. Van Buer M.G., Woodru D.L., Olson R.T. Solving the medium newspaper production/distribution
problem // European Journal of Operational Research. – 1999. – 115. – P. 237-253.
5. Carter A.E., Ragsdale C.T. Scheduling pre-printed newspaper advertising inserts using genetic
algorithms // Omega. – 2002. – P. 415-421.
6. Kewei Huang, Dingwei Wang. Multiple traveling salesman problem and its application to hot
rolling planning // Application Research of Computers. – July 2007. – 24 (7). – P. 43-46.
7. 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). – P. 267-282.
8. Kim K.H., Park Y.M. A crane scheduling method for port container terminals // European
Journal of Operational Research. – 2004. – 156. – P. 752-768.
9. 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. – P. 1061-1073.
10. 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. – P. 333-347.
11. 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. – P. 103-112.
12. 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.
13. Akbay M.A., Kalayci C.B. A Variable Neighborhood Search Algorithm for Cost-Balanced
Travelling Salesman Problem // In Proceedings of the Metaheuristics Summer School,
Taormina, Italy, 2018.
14. Muño -Herrera S., Suchan K. Constrained Fitness Landscape Analysis of Capacitated Vehicle
Routing Problems // Entropy. – 2022. – Vol. – P. 53.
15. Xu H.L., Zhang C.M. The research about balanced route MTSP based on hybrid algorithm // In
Proceedings of the 2009 International Conference on Communication Software and Networks,
Chengdu, China, 2009. – P. 533-536.
16. 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. – Vol. 3.
– P. 66.
17. de Castro Pereira S., Solteiro Pires E.J., de Moura Oliveira P.B. A Hybrid Approach GABC–
LS to Solve MTSP // In Proceedings of the Optimization, Learning Algorithms and Applications.
– Springer International Publishing: Cham, Switzerland, 2022. – P. 520-532.
18. Dorigo M., Birattari M., Stutzle T. Ant colony optimization // IEEE Comput. Intell. Mag.
– 2006. – P .28-39.
19. Zhan S.C., Xu J., Wu J. The optimal selection on the parameters of the ant colony algorithm //
Bull. Sci. Technol. – 2003. – P. 381-386.
20. Dorigo M. Optimization, Learning and Natural Algorithms. Ph.D. Thesis, Politecnico di Milano,
Milano, Italy, 1992.
21. Gambardella L.M., Dorigo M. Ant-Q: A reinforcement learning approach to the traveling
salesman problem // In Machine Learning Proceedings. – Elsevier: Amsterdam, The Netherlands,
1995. – P. 252-260.
22. Dorigo M., Gambardella L.M. Ant colonies for the travelling salesman problem // Biosystems.
– 1997. – P. 73-81.
23. Bullnheimer B., Hartl R., Strauss C. A New Rank Based Version of the Ant System—A Computational
Study // Cent. Eur. J. Oper. Res. – 1999. – P. 25-38.
24. Guntsch M., Middendorf M. A population based approach for ACO // In Proceedings of the
Workshops on Applications of Evolutionary Computation, Kinsale, Ireland, 3–4 April 2002.
– Springer: Berlin/Heidelberg, Germany, 2002. – P. 72-81.
25. Blum C. Theoretical and Practical Aspects of Ant Colony Optimization. – IOS Press: Amsterdam,
The Netherlands, 2004. – Vol. 282.
26. Хуссейн Ф.А., Финаев В.И. Исследование эффективности алгоритма искусственных по-
тенциалов, муравьиного алгоритма и их комбинации при планировании траектории
движения мобильного робота // Компьютерные и информационные технологии в науке,
инженерии и управлении (КомТех-2020). – 2020. – С. 39-48.
27. Huang K.L., Liao C.J. Ant colony optimization combined with taboo search for the job shop
scheduling problem // Comput. Oper. Res. – 2008. – P. 1030-1046.
28. Xiao J., Li L. A hybrid ant colony optimization for continuous domains // Expert Syst. Appl.
– 2011. – P. 11072-11077.
29. Rahmani R., Yusof R., Seyedmahmoudian M., Mekhilef S. Hybrid technique of ant colony and
particle swarm optimization for short term wind energy forecasting // J. Wind. Eng. Ind.
Aerodyn. – 2013. – P. 163-170.
30. Lah Ivo. A new kind of numbers and its application in the actuarial mathematics // Boletim do
Instituto dos Actuários Portugueses. – 1954. – P. 7-15.
31. de Castro Pereira S., Solteiro Pires E.J., de Moura Oliveira P.B. Ant-Balanced Multiple Traveling
Salesmen: ACO-BMTSP // Algorithms. – 2023. – P. 37.
