Двухэтапная маршрутизация транспорта с использованием геопространственной кластеризации

Рассматривается одна из актуальных и ключевых задач транспортной отрасли — задача планирования маршрутов следования транспортных средств. Для многих приложений данная задача может быть описана и формализована как задача коммивояжера (англ. Traveling Salesman Problem, TSP), которая заключается в поиске для коммивояжера оптимального маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В общем случае при планировании таких маршрутов приходится решать множественную задачу коммивояжера (англ. Multiple Traveling Salesman Problem, MTSP), допускающую более одного коммивояжера и более одного депо — пункта их базирования, в котором начинаются и заканчиваются маршруты. MTSP как задача комбинаторной оптимизации относится к классу NP-трудных задач. В настоящей статье излагается эвристический метод ее решения на основе геопространственной кластеризации исходного множества го родов. Сначала рассматривается MTSP с одним депо. Дается двухиндексная математическая формализация данной задачи и излагается метод Миллера—Такера—Землина, сводящий ее к задаче целочисленного линейного программирования. Обсуждаются метаэвристические методы решения MTSP. Рассматривается более сложная задача — MTSP с несколькими депо. Излагается кластерный двухэтапный метод решения данной задачи — метод CFRS ("Cluster First — Route Second"), позволяющий свести ее к семейству MTSP с одним депо. Здесь на первом этапе осуществляется геопространственная кластеризация городов, для которой возможно использовать различные методы кластеризации, включая метод K-средних. На втором этапе для каждого построенного кластера осуществляется выбор депо для его обслуживания и строятся маршруты объезда всех городов данного кластера. Обсуждается методология кластеризации как эффективный инструмент решения MTSP.

Приводится числовой пример авиационной логистики — маршрутизация полетов группы БПЛА.

1. Caceres-Cruz J., Arias P., Guimarans D., Riera D., Juan A. A. Rich Vehicle Routing Problem: Survey // ACM Computing Surveys. 2015. Vol. 47, Iss. 2. P. 1—28. DOI: 10.1145/2666003.

2. Валеева А. Ф., Гончарова Ю. А., Валеев Р. С. Задачи маршрутизации при транспортировке: обзор моделей, методов и алгоритмов // Логистика и управление цепями поставок. 2019. № 4 (93). Ч. 1. С. 74—89.

3. Титов Б. А. Транспортная логистика: электрон: Учеб. пособ. Самара: Самарский университет, 2012. 198 с.

4. Toth P., Vigo D. (eds.). Vehicle Routing: Problems, Methods, and Applications. Philadelphia: Society for Industrial and Applied Mathematics, 2014. 481p. DOI: 10.1137/1.9781611973594.

5. Меламед И. И., Сергеев С. И., Сигал И. Х. Задача коммивояжера. Вопросы теории // Автоматика и телемеханика. 1989. № . 9. С. 3—33.

6. Dantzig G. B., Ramser J. H. The Truck Dispatching Problem // Management Science. 1959. Vol. 6, N. 1. P. 80—91. DOI: 10.1287/mnsc.6.1.80.

7. Clarke G., Wright J. W. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points // Operations research. 1964. Vol. 12, N. 4. P. 568—581.

8. The Traveling Salesman Problem and its Variations / Ed. by G. Gutin and A. P. Punnen. NY: Springer, 2007. 850 p.

9. Кубил В. Н. Обзор обобщений и расширений задачи маршрутизации транспорта // Вестник РГУПС. 2018. Т. 70, № 2. С. 97—109.

10. Филимонов А. Б., Филимонов Н. Б. Оптимальная маршрутизация полетов БПЛА при групповом патрулировании территорий // Journal of Advanced Research in Technical Science. 2023. Iss. 34. P. 49—55. DOI: 10.26160/2474-5901-2023-34-49-55.

11. Филимонов А. Б., Филимонов Н. Б., Фам К. Ф. Планирование маршрутов полета БПЛА в задачах группового патрулирования протяженных территорий // V Международная научная конференция по проблемам управления в технических системах (ПУТС-2023). СПб.: Изд. СПбГЭТУ "ЛЭТИ", 2023. С. 274—277.

12. Филимонов А. Б., Филимонов Н. Б., Нгуен Т. К., Фам К. Ф. Планирование маршрутов полета БПЛА в задачах группового патрулирования протяженных территорий // Мехатроника, автоматизация, управление. 2023. Т. 24, № 7. С. 374—381. DOI: 10.17587/mau.24.374-381.

13. Филимонов А. Б., Филимонов Н. Б. Задача группового патрулирования протяженных территорий с множеством депо // Journal of Advanced Research in Technical Science. 2023. Iss. 37. P. 42—51. DOI: 10.26160/2474-5901-2023-37-42-51.

14. Филимонов А. Б., Филимонов Н. Б. Планирование маршрутов полета БПЛА при групповом патрулировании протяженных территорий // XIV Всероссийское совещание по проблемам управления (ВСПУ-2024). М.: ИПУ РАН, 2024. С. 1138—1142.

15. Филимонов А. Б., Филимонов Н. Б., Нгуен Т. К., Фам К. Ф. Оптимизация маршрутов полета БПЛА при групповом патрулировании протяженных территорий как множественная задача коммивояжера с несколькими депо // Мехатроника, автоматизация, управление. 2024. Т. 25, № 5. С. 259—265. DOI: 10.17587/mau.25.259-265.

16. Bektas T. The Multiple Traveling Salesman Problem: an Overview of Formulations and Solution Procedures // OMEGA: The International Journal of Management Science. 2006. Vol. 34. Iss. 3. P. 209—219.

17. Cheikhrouhou O., Khoufi I. A Comprehensive Survey on the Multiple Traveling Salesman Problem: Applications, Approaches and Taxonomy // Comput. Sci. Rev. 2021. Vol. 40, N. 100369. P. 76. DOI: 10.1016/j.cosrev.2021.100369.

18. Филимонов А. Б., Нгуен Т. К. Кластерный метод решения множественной задачи коммивояжера с несколькими депо // Journal of Advanced Research in Natural Science. 2024, Iss. 19. P. 4—10. DOI: 10.26160/2572-4347-2024-19-4-10.

19. Dantzig G. B., Fulkerson D. R., Johnson S. M. Solution of a Large-Scale Traveling Salesman Problem // Operation Research. 1954. Vol. 2. P. 393—410. DOI: 10.1287/opre.2.4.393.

20. Miller C. E., Tucker A. W., Zemlin R. A. Integer Programming Formulation of Traveling Salesman Problems // Journal of the ACM. 1960. Vol. 7, N. 4. P. 326—329. DOI: 10.1145/321043.321046.

21. Gendreau M., Gilbert L., Jean-Yves P. Vehicle Routing: Modern Heuristics // Local Search in Combinatorial Optimization. Princeton: Princeton University Press. 2003. P. 311—336. DOI: 10.1515/9780691187563-012.

22. Şahin Y., Eroğlu A. Metaheuristic Methods for Capacitated Vehicle Routing Problem: Literature Review // Suleyman Demirel University: The Journal of Faculty of Economics and Administrative Sciences. 2014. Vol. 19, N. 4. P. 337—355.

23. Labadie N., Prins C., Prodhon C. Metaheuristics for Vehicle Routing Problems // Computer engineering series Computer engineering series. Metaheuristics set (Vol. 3). John Wiley & Sons. 2016. 194 p. DOI: 10.1002/9781119136767.

24. Singh D. R., Singh M. K., Singh T., Prasad R. Genetic Algorithm for Solving MTSP using a New Crossover and Population Generation // Computación y Sistemas. 2018. Vol. 22, N. 2. P. 491—503. DOI: 10.13053/cys-22-2-2956.

25. Курейчик В. М., Логунова Ю. А. Анализ перспективности применения генетического алгоритма при решении задачи коммивояжера // Информационные технологии. 2018. Т. 24, № 11. С. 691—697. DOI: 10.17587/it.24.691-697.

26. Ghoseiri K., Ghannadpour S. A Hybrid Genetic Algorithm for Multi-Depot Homogenous Locomotive Assignment with Time Windows // Appl. Soft Comput. 2010. Vol. 10. P. 53—65. DOI: 10.1016/j.asoc.2009.06.004.

27. Karakatič S., Podgorelec V. A Survey of Genetic Algorithms for Solving Multi Depot Vehicle Routing Problem // Applied Soft Computing. 2015. Vol. 27. P. 519—532. DOI: 10.1016/j.asoc.2014.11.005.

28. Савельев М. В., Енгибарян И. А. Решение задач целочисленного программирования на основе генетических алгоритмов // Известия вузов. Северо-Кавказский регион естественные науки. Приложение. 2005. № 9. С. 18—21.

29. Liu Y., Li H., Chen H. A Genetic Algorithm for Solving Linear Integer Bilevel Programming Problems // 2018 14th International Conference on Computational Intelligence and Security (CIS). Hangzhou, China. 2018. P. 40—44. DOI: 10.1109/CIS2018.2018.00017.

30. Laporte G., Nobert Y., Arpin D. Optimal Solutions to Capacitated Multi Depot Vehicle Routing Problems // Congressus Numerantium. 1984. Vol. 44. P. 283—292.

31. Dutta S., Bhattacharya S. A Short Review of Clustering Techniques // International Journal of Advanced Research in Management and Social Sciences. 2015. Vol. 4, N. 5. P. 132—139.

32. Berkhin P. A Survey of Clustering Data Mining Techniques // Grouping Multidimensional Data. Springer. 2006. P. 25—71. DOI: 10.1007/3-540-28349-8.

33. Jain A. K. Data Clustering: 50 years Beyond K-means // Pattern Recognition Letters. 2010. Vol. 31, N. 8. P. 651—666. DOI: 10.1016/j.patrec.2009.09.011.

34. Ikotun A. M., Ezugwu A. E., Abualigah L., Abuhaija B., Heming J. K-means Clustering Algorithms: A Comprehensive Review, Variants Analysis, and Advances in the Era of Big Data // Information Sciences. 2023. Vol. 622. P. 178—210. DOI: 10.1016/j.ins.2022.11.139.

35. Xu X., Yuan H., Liptrott M. et al. Two Phase Heuristic Algorithm for the Multiple-Travelling Salesman Problem // Soft Comput. 2018. Vol. 22. P. 6567—6581. DOI: 10.1007/s00500-017-2705-5.

36. Гасанов И. М., Гольцов И. С. Разработка двухфазного кластерного алгоритма для решения задачи маршрутиации транспорта // Инновации. Наука. Образование. 2022. № 50. С. 2366—2382.

37. Gillett B. E., Miller L. R. A Heuristic Algorithm for the Vehicle-Dispatch Problem // Operations Research. 1974. Vol. 22, N. 2. P. 340—349. DOI: 10.1287/opre.22.2.340.

38. Bodin L. D. A Taxonomic Structure for Vehicle Routing and Scheduling Problems // Computers &Urban Society. 1975. Vol. 1, N. 1. P. 11—29. DOI: 10.1016/0305-7097(75)90003-4.

39. Garside A. K., Laili N. R. A Cluster-First Route-Second Heuristic Approach to Solve the Multi-Trip Periodic Vehicle Routing Problem // Jurnal Teknik Industri. 2019. Vol. 20, N. 2. P. 171—181. DOI: 10.22219/JTIUMM.Vol20.No2.172-181.

40. Comert S. E., Yazgan H. R. Effective Cluster-First RouteSecond Approaches Using Metaheuristic Algorithms for the Capacitated Vehicle Routing Problem // International Journal of Industrial Engineering: Theory, Applications and Practice. 2021. Vol. 28, N. 1. P. 14—38.

41. Beasley J. E. Route First — Cluster Second Methods for Vehicle Routing // Omega. 1983. Vol. 11, Iss. 4. P. 403—408. DOI: 10.1016/0305-0483(83)90033-6.

42. Ekiz M. K., Bozdemir M., Türkkan B. Ö. Route First — Cluster Second Method for Personal Service Routing Problem // Journal of Engineering Studies and Research. 2019. Vol. 25, N. 2. P. 18—24. DOI: 10.29081/jesr.v25i2.31.

43. Chisman J. A. The Clustered Traveling Salesman Problem // Computers & Operations Research. 1975. N. 2. P. 115—119. DOI: 10.1016/0305-0548(75)90015-5.

44. Lu Y., Hao J.-K., Wu Q. Solving the Clustered Traveling Salesman Problem via Traveling Salesman Problem Methods // PeerJ Computer Science. 2022. Vol. 8. 24 p.

45. Zhang T., Ramakrishnan R., Livny M. BIRCH: a New Data Clustering Algorithm and its Applications // Data Mining and Knowledge Discovery. 1997. Vol. 1, Iss. 2. P. 141—182. DOI: 10.1023/A:1009783824328.

46. Murray C. C., Raj R. The Multiple Flying Sidekicks Traveling Salesman Problem: Parcel Delivery with Multiple Drones // Transportation Research Part C: Emerging Technologies. 2020. Vol. 110. P. 368—398. DOI: 10.1016/j.trc.2019.11.003.

47. Машненков Д. В. Перспективы использования БПЛА в логистике // Инновации и инвестиции. 2023. № 6. С. 168—171.