Построение многоагентных маршрутов в сети с иерархией вершин
Ключевые слова:
задача коммивояжера TSP и mTSP, согласованная иерархическая кластеризация, алгоритмы решения mTSP, HCmTSP
Аннотация
Многоагентная задача маршрутизации типа коммивояжера является NP-трудной. Для построения приближенных решений важен учет всей имеющейся информации о структуре сети, ограничениях и целях. Выделяется класс задач (характерный для распределения ресурсов в инфраструктурных сетях), в которых введен иерархический порядок вершин. Рассматриваются прикладные задачи многоагентной маршрутизации mTSP на таких сетях с учетом разного уровня иерархии вершин и кластеризации сети (HCmTSP). Построение маршрутов HCmTSP согласовано с естественной кластеризацией сложной инфраструктурной сети. Приводится обзор задач, методов и алгоритмов, основанных на разных эвристиках. Показано, что в зависимости от логистических целей может быть выбран различный тип кластеризации, согласованной с mTSP. Сравниваются результаты вычислительного эксперимента по типам кластеризации и маршрутам. Приводятся результаты синтеза маршрутов двух уровней иерархии. Разработаны и реализованы алгоритмы построения маршрутов mTSP с одним центром (базой) и синтеза двухуровневых маршрутов обхода кластеров и маршрутов TSP на кластерах. В задаче mTSP с одним выделенным центром для построения начальных маршрутов исследуется гибридный алгоритм распределения вершин по кругу в зависимости от угла, с дальнейшим разбиением на кластеры и поиском TSP агентами на каждом кластере. Используются эвристики нескольких муравьиных колоний. В задаче синтеза базовый алгоритм имитации отжига сравнивается с решателем Concorde. Приведены численные результаты для известных тестовых наборов данных и для реальных данных городской инфраструктуры. Работа предназначена для отбора алгоритмов, их тестирования и проведения вычислительных экспериментов и наполнения программного комплекса: построение многоагентных маршрутов в сложных сетях с иерархией вершин.
Скачивания
Данные скачивания пока не доступны.
Литература
1. Germanchuk M. S., Lemtyuzhnikova D. V. and Lukianenko V. A. (2021) Metaheuristic Algorithms for Multiagent Routing Problems. Automation and Remote Control. 10 (82). P. 1787– 1801. DOI
2. Danilchenko M. N. and Muravnik A. B. (2021) Neural network approach to route construction in an automated control system for special purposes. High-tech technologies in space research of the Earth. 13 (1). P. 58–66. DOI
3. Kozlova M. G., Lukyanenko V. A., Rudenko L. I. and Germanchuk M. S. (2021) The use of artificial intelligence technologies in multi-agent control tasks. Distance educational technologies: Proceedings of the VI International Scientific and Practical Conference / ed. V. N. Taran. Simferopol, IT «ARIAL». P. 251–255. (In Russian)
4. Lukyanenko V. A., Germanchuk M. S. and Makarov O. O. (2021) Specifics of routing tasks in conditions of local network transformations. Mathematical methods of pattern recognition: Abstracts of the 20th All-Russian Conference with International Participation, Moscow 2021 – Mos cow : Russian Academy of Sciences. P. 460–462. (In Russian)
5. Cormen T. (2009) Introduction to Algorithms. ISBN 978-0-262-03384-8
6. Karapetyan D. and Gutin G. (2011) LinKernighan heuristic adaptations for the generalized traveling salesman problem. European Journal of Operational Research. V. 208, No. 3. P. 221–232.
7. Sivaraj R., Ravichandran T. and Devipriya R. (2012) Solving Traveling Salesman Problem using Clustering Genetic Algorithm. International Journal on Computer Science and Engineering. V. 4, No. 7. P. 1310–1317.
8. Phienthrakul T. (2014) Clustering Evolutionary Computation for Solving Traveling Salesman Problem. International Journal of Advanced Computer Science and Information Technology. V. 3, No 3. P. 243–262.
9. Nawaz M., Enscore E. and Ham I. (1983) A heuristic algorithm for the m-Machine, n-Job flow-shop sequencing problem. Omega-International Journal of Management Science. V. 11. P. 91–95.
10. Tang K., Wang J., Li X. and Yao X. (2015) Scalable Approach to Capacitated Arc Routing Problems Based on Hierarchical Decomposition. Research of Birmingham. University of Birmingham. P. 15. DOI
11. Medvedev S. N. (2021) Mathematical model and algorithm for solving the problem of routing vehicles with multiple centers with alternation and a single collection point. Vestnik VSU, Series: System analysis and information technologies. 1. P. 21–32. DOI
12. Amberg A., Domschke W. and Voss S. (2000) Multiple center capacitated arc routing problems: A tabu search algorithm using capacitated trees. European Journal of Operational Reseach. V. 124. P. 360–376. DOI
13. Tsai C. and Chiu C. (2006) A VNS based Hierarchical Clustering Method. International Conference on Computational Intelligence.
14. Nagy M. and Negru D. (2014) Using clustering software for exploring spatial and temporal patterns in non-communicable diseases. European Scientific Journal. V. 10, No. 33. P. 3747.
15. Vishnupriya N. and Sagayaraj F. (2015) Data Clustering using MapReduce for Multidimensional Datasets. International Advanced Research Journal in Science, Engineering and Technology. V. 2, No. 8. P. 39–42. DOI
16. Nidhi S. (2015) A modified Approach for Incremental k-Means Clustering Algorithm. International Journal of Engineering Development and Research. V. 3, No. 2. P. 1081–1084.
17. Liu G., Song S. and Wu C. (2011) Two Techniques to Improve the NEH Algorithm for Flow-Shop Scheduling Problems. Advanced Intelligent Computing Theories and Applications with Aspects of Artificial Intelligence of the series Lecture Notes in Computer Science. P. 41–48. DOI
18. Seck-Touh-Mora J., Garcia-Lechuga L. and Medina-Marin J. (2014) Improving a multi restart local search algorithm by permutation matrices and sorted work times for the flow shop scheduling problem. World Comp Proceedings. URL
19. Mestria M. (2014) Heuristic methods using variable neighborhood random local search for the clustered traveling salesman problem. Revista Cientifica y Electronica de ingenierı´a de produccion. P. 1511–1536.
20. Grasas A., Juan A. and Lorenzo H. (2014) SimILS: a simulation-based extension of the iterated local search metaheuristic for stochastic combinatorial optimization. Journal of Simulation. URL
21. Kozlova M., Lukianenko V. and Makarov O. (2022) Multiple hierarchical routing with time windows. Интеллектуализация обработки информации: Тезисы докладов 14-й Международной конференции, г. Москва 2022 г. – М.: Российская академия наук, P. 430–432.
22. Solomon benchmark. URL
23. Gocken T. and Yaktubay M. (2019) Comparison of different clustering algorithms via genetic algorithm for VRPTW. International Journal of Simulation Modelling. V. 18. No 4. P. 574–585. DOI
24. Kosolsombat S. and Ratanavilisagul C. (2022) Modified ant colony optimization with selecting and elimination customer and re-initialization for VRPTW. Bulletin of Electrical Engineering and Informatics. V. 11., No 6. P. 3471– 3482. DOI
25. Zhang Y. [et al.] (2020) Balancing Exploration and Exploitation in the Memetic Algorithm via a Switching Mechanism for the Large-Scale VRPTW. International Conference on Database Systems for Advanced Applications. Springer, Cham. P. 324–331. DOI
26. Germanchuk M. S., Kozlova M. G., Lukyanenko V. A. and Makarov O. O. (2020) Tasks of the type of many traveling salesmen in changing conditions. Collection of materials of the international conference KROMSH-2020: POLYPRINT, 2020. P. 241–245. (In Russian)
27. Germanchuk M. S., Kozlova M. G. and Lukyanenko V. A. (2020) Routing tasks in emergency conditions. Analysis, modeling, management, development of socio-economic systems: collection of scientific papers of the XIV All-Russian School-Symposium with international participation AMUR-2020, Simferopol-Sudak, September 14–27, 2020 / ed. Council: A.V. Sigal (pres.) and others. Simferopol : IP Kornienko A.A. P. 98–107. (In Russian)
28. Concorde TSP Solver. URL
29. PyConcorde. URL
30. TSPLIB. URL
2. Danilchenko M. N. and Muravnik A. B. (2021) Neural network approach to route construction in an automated control system for special purposes. High-tech technologies in space research of the Earth. 13 (1). P. 58–66. DOI
3. Kozlova M. G., Lukyanenko V. A., Rudenko L. I. and Germanchuk M. S. (2021) The use of artificial intelligence technologies in multi-agent control tasks. Distance educational technologies: Proceedings of the VI International Scientific and Practical Conference / ed. V. N. Taran. Simferopol, IT «ARIAL». P. 251–255. (In Russian)
4. Lukyanenko V. A., Germanchuk M. S. and Makarov O. O. (2021) Specifics of routing tasks in conditions of local network transformations. Mathematical methods of pattern recognition: Abstracts of the 20th All-Russian Conference with International Participation, Moscow 2021 – Mos cow : Russian Academy of Sciences. P. 460–462. (In Russian)
5. Cormen T. (2009) Introduction to Algorithms. ISBN 978-0-262-03384-8
6. Karapetyan D. and Gutin G. (2011) LinKernighan heuristic adaptations for the generalized traveling salesman problem. European Journal of Operational Research. V. 208, No. 3. P. 221–232.
7. Sivaraj R., Ravichandran T. and Devipriya R. (2012) Solving Traveling Salesman Problem using Clustering Genetic Algorithm. International Journal on Computer Science and Engineering. V. 4, No. 7. P. 1310–1317.
8. Phienthrakul T. (2014) Clustering Evolutionary Computation for Solving Traveling Salesman Problem. International Journal of Advanced Computer Science and Information Technology. V. 3, No 3. P. 243–262.
9. Nawaz M., Enscore E. and Ham I. (1983) A heuristic algorithm for the m-Machine, n-Job flow-shop sequencing problem. Omega-International Journal of Management Science. V. 11. P. 91–95.
10. Tang K., Wang J., Li X. and Yao X. (2015) Scalable Approach to Capacitated Arc Routing Problems Based on Hierarchical Decomposition. Research of Birmingham. University of Birmingham. P. 15. DOI
11. Medvedev S. N. (2021) Mathematical model and algorithm for solving the problem of routing vehicles with multiple centers with alternation and a single collection point. Vestnik VSU, Series: System analysis and information technologies. 1. P. 21–32. DOI
12. Amberg A., Domschke W. and Voss S. (2000) Multiple center capacitated arc routing problems: A tabu search algorithm using capacitated trees. European Journal of Operational Reseach. V. 124. P. 360–376. DOI
13. Tsai C. and Chiu C. (2006) A VNS based Hierarchical Clustering Method. International Conference on Computational Intelligence.
14. Nagy M. and Negru D. (2014) Using clustering software for exploring spatial and temporal patterns in non-communicable diseases. European Scientific Journal. V. 10, No. 33. P. 3747.
15. Vishnupriya N. and Sagayaraj F. (2015) Data Clustering using MapReduce for Multidimensional Datasets. International Advanced Research Journal in Science, Engineering and Technology. V. 2, No. 8. P. 39–42. DOI
16. Nidhi S. (2015) A modified Approach for Incremental k-Means Clustering Algorithm. International Journal of Engineering Development and Research. V. 3, No. 2. P. 1081–1084.
17. Liu G., Song S. and Wu C. (2011) Two Techniques to Improve the NEH Algorithm for Flow-Shop Scheduling Problems. Advanced Intelligent Computing Theories and Applications with Aspects of Artificial Intelligence of the series Lecture Notes in Computer Science. P. 41–48. DOI
18. Seck-Touh-Mora J., Garcia-Lechuga L. and Medina-Marin J. (2014) Improving a multi restart local search algorithm by permutation matrices and sorted work times for the flow shop scheduling problem. World Comp Proceedings. URL
19. Mestria M. (2014) Heuristic methods using variable neighborhood random local search for the clustered traveling salesman problem. Revista Cientifica y Electronica de ingenierı´a de produccion. P. 1511–1536.
20. Grasas A., Juan A. and Lorenzo H. (2014) SimILS: a simulation-based extension of the iterated local search metaheuristic for stochastic combinatorial optimization. Journal of Simulation. URL
21. Kozlova M., Lukianenko V. and Makarov O. (2022) Multiple hierarchical routing with time windows. Интеллектуализация обработки информации: Тезисы докладов 14-й Международной конференции, г. Москва 2022 г. – М.: Российская академия наук, P. 430–432.
22. Solomon benchmark. URL
23. Gocken T. and Yaktubay M. (2019) Comparison of different clustering algorithms via genetic algorithm for VRPTW. International Journal of Simulation Modelling. V. 18. No 4. P. 574–585. DOI
24. Kosolsombat S. and Ratanavilisagul C. (2022) Modified ant colony optimization with selecting and elimination customer and re-initialization for VRPTW. Bulletin of Electrical Engineering and Informatics. V. 11., No 6. P. 3471– 3482. DOI
25. Zhang Y. [et al.] (2020) Balancing Exploration and Exploitation in the Memetic Algorithm via a Switching Mechanism for the Large-Scale VRPTW. International Conference on Database Systems for Advanced Applications. Springer, Cham. P. 324–331. DOI
26. Germanchuk M. S., Kozlova M. G., Lukyanenko V. A. and Makarov O. O. (2020) Tasks of the type of many traveling salesmen in changing conditions. Collection of materials of the international conference KROMSH-2020: POLYPRINT, 2020. P. 241–245. (In Russian)
27. Germanchuk M. S., Kozlova M. G. and Lukyanenko V. A. (2020) Routing tasks in emergency conditions. Analysis, modeling, management, development of socio-economic systems: collection of scientific papers of the XIV All-Russian School-Symposium with international participation AMUR-2020, Simferopol-Sudak, September 14–27, 2020 / ed. Council: A.V. Sigal (pres.) and others. Simferopol : IP Kornienko A.A. P. 98–107. (In Russian)
28. Concorde TSP Solver. URL
29. PyConcorde. URL
30. TSPLIB. URL
Опубликован
2023-10-26
Как цитировать
Козлова, М. Г., Лукьяненко, В. А., & Макаров, О. О. (2023). Построение многоагентных маршрутов в сети с иерархией вершин. Вестник ВГУ. Серия: Системный анализ и информационные технологии, (3), 32-50. https://doi.org/10.17308/sait/1995-5499/2023/3/32-50
Выпуск
Раздел
Математические методы системного анализа, управления и моделирования
- Авторы сохраняют за собой авторские права и предоставляют журналу право первой публикации работы, которая по истечении 6 месяцев после публикации автоматически лицензируется на условиях Creative Commons Attribution License , которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
