Сравнительный анализ методов решения задачи целераспределения и маршрутизации для мультиагентных робототехнических систем

Исследуется задача мультикоммивояжера, которая отличается от классической задачи коммивояжера тем, что рассматривается передвижение нескольких коммивояжеров, которые должны посетить определенное число городов ровно один раз и вернуться в исходную точку с минимальными затратами на поездку. Существуют три концепции решения данной задачи: на основе оптимизации, на основе концепции Cluster First—Order Second и на основе концепции Route First—Cluster Second. Последняя использовалась для решения задачи маршрутизации транспортных средств. В данной работе на основе этой концепции предложен метод для решения задачи мультикоммивояжера. Основная цель исследования — разработать эффективный метод решения, который сократит время выполнения задач и оптимизирует использование ресурсов. Для оценки эффективности разработанного метода был проведен сравнительный анализ методов решения задачи мультикоммивояжера. Выявлено, что предлагаемый метод на основе концепции Route First—Cluster Second позволяет более эффективно управлять нагрузкой и ресурсами, что способствует минимизации общего времени выполнения задач.
Универсальность и применимость метода в различных сценариях, включая разное число задач и коммивояжеров, являются его особенностью. Такой подход обеспечивает более широкий охват условий задачи и позволяет оценить применимость метода в различных контекстах, что является важным итогом данного исследования.
Оценка результатов основывалась на трех ключевых критериях: вычислительном времени получения решения задачи мультикоммивояжера, суммарной длине пройденных коммивояжерами маршрутов и максимальной длине маршрута. Анализ экспериментальных данных показал, что разработанный метод значительно превосходит классический подход, основанный на метаэвристике, по всем рассматриваемым критериям в большинстве экспериментов и в некоторых ситуациях превосходит подход на основе кластеризации и метаэвристики. 

1. Laporte G., Nobert Y. А cutting planes algorithm for the m-salesmen problem // Journal of the Operational Research Society. 1980. P. 1017—1023.

2. Bektas T. The multiple traveling salesman problem: an overview of formulations and solution procedures // OMEGA: The International Journal of Management Science. 2006. Vol. 34, N. 3. P. 209—219.

3. Dorigo M., Birattari M., Stutzle T. Ant colony optimization // IEEE Comput. Intell. Mag. 2006. P. 28—39.

4. Harrath Y., Salman A. F., Alqaddoumi A., Hasan H., Radhi A. А novel hybrid approach for solving the multiple traveling salesmen problem // Arab. J. Basic Appl. Sci. 2019. P. 103—112.

5. Lah I. А new kind of numbers and its application in the actuarial mathematics // Boletim do Instituto dos Actu@rios Portugueses. 1954. P. 7—15.

6. Shabanpour M., Yadollahi M., Hasani M. M. А New Method to Solve the Multi Traveling Salesman Problem with the Combination of Genetic Algorithm and Clustering Technique // IJCSNS International Journal of Computer Science and Network Security. May 2017. Vol. 17, N. 5.

7. Kusumahardhini N., Hertono G. F., Handari В. D. Implementation of K-Means and crossover ant colony optimization algorithm on multiple traveling salesman problem // Basic and Applied Sciences Interdisciplinary Conference. 2017.

8. Latah M. Solving multiple TSP problem by K-means and crossover based modified ACO algorithm // International Journal of Engineering Research and Technology. 2016. Vol. 5, N. 02.

9. Basma H., Bashir H., Cheaitou A. А Novel Clustering Method for Breaking Down the Symmetric Multiple Traveling Salesman Problem // Journal of Industrial Engineering and Management JIEM. 2021. Vol. 14, N. 2.

10. Arthur D., Vassilvitskii S. K-Means++: The Advantages of careful seeding // Proceedings of the 8th annual ACM-SIAM symposium on Discrete algorithms. 2007.

11. Graham R. L., Knuth D. E., Patashnik O. Concrete Mathematics, Addison—Wesley, Reading MA, 1988. 244 p.

12. Beasley J. E. Route First — Cluster Second Methods for Vehicle Routing // Omega. 1983. Vol. 11, Iss. 4. P. 403—408.

13. Bozdemir M. K., Bozdemir M., Burcu Ö. Route FirstCluster Second Method for Personal Service Routing Problem // Journal of Engineering Studies and Research. 2019. Vol. 25, N. 2. P. 18—24.

14. Костюков В. А., Хуссейн Ф. А., Евдокимов И. Д. Метод решения проблемы мульти-коммивояжера в среде без препятствий на основе уменьшения размера пространства решений // Известия ЮФУ. Технические науки. 2024. № 1.

15. de Castro Pereira S., Solteiro Pires E. J., de Moura Oliveira P. B. Ant-Balanced Multiple Traveling Salesmen: ACOBMTSP // Algorithms. 2023. P. 37.

16. Ruprecht-Karls. TSPLIB. URL: http://comopt.ifi.uniheidelberg.de/software/TSPLIB95 (accessed on 4 August 2024).