Применение метода Кларка – Райта в задачах тушения лесных пожаров силами авиационной охраны

Введение. Целью данного исследования является определение минимальных затрат на путь до очагов низового лесного пожара и на его локализацию. Для достижения поставленной цели выполняются задачи: по анализу выбранного метода для расчета минимальных затрат на процесс выгрузки пожарного десанта и процесс локализации низового лесного пожара соответственно; по идентификации и характеристике необходимого оборудования, используемого при локализации низового лесного пожара; по определению оптимального пути и количества сотрудников МЧС в составе пожарного десанта с помощью приведенного псевдокода.

Аналитическая часть. Произведен обзор моделей, методов и алгоритмов поиска кратчайшего пути, оптими­зации, кольцевой маршрутизации транспорта. Поставлена некоторая задача тушения лесного пожара. Применение модифицированного метода Кларка – Райта, который учитывает возможность варьирования глубины сращивания маршрутов и определение оптимального значения вероятности осуществления ухудша­ющего шага, позволяет найти минимальные временные затраты авиалесоохраны на локализацию низового лесного пожара. Предоставлено решение задачи доставки пожарного десанта благодаря псевдокоду, реализующему базовый метод Кларка – Райта.

Выводы. Решение на основе модифицированного метода Кларка – Райта предложит кольцевые авиамаршруты, которые будут закреплены за вертолетом, благодаря чему доставка пожарного десанта станет экономи­чески обоснованной. Результаты исследования будут полезны аналитикам и разработчикам про­­г­рам­­­­много обеспечения для осуществления деятельности авиалесоохраны.

1. Beresneva E., Avdoshin S. Analysis of mathematical formulations of capacitated vehicle routing problem and methods for their solution // Proceedings of the Institute for System Programming of the RAS. 2018. Vol. 30. Issue 3. Pp. 233–250. DOI: 10.15514/ISPRAS-2018-30(3)-17

2. Vega-Mejia C.A., Neira E.M.G., Montoya-Torres J.R., Islam S.M.N. Using a hybrid heuristic to solve the balanced vehicle routing problem with loading constraints // International Journal of Industrial Engineering Computations. 2020. Vol. 11. Issue 2. Pp. 255–280. DOI: 10.5267/j.ijiec.2019.8.002

3. Achamu G., Berhan E. A classical heuristic algorithm implementation for logistic analysis of waste collection problem: a case of Addis Ababa Arada subicty // Journal of EEA. 2021. Vol. 39. Pp. 97–113.

4. Kosasih W., Ahmad A., Laricha Salomon L., Febricky. Comparison study between nearest neighbor and farthest insert algorithms for solving VRP model using heuristic method approach // IOP Conference Series Materials Science and Engineering. 2020. Vol. 852. Issue 1. P. 012090. DOI: 10.1088/1757-899X/852/1/012090

5. Коляда А.В. Оптимизация процессов тушения лесного пожара с использованием имитацион­ного моделирования // Ученые записки российского государственного социального университета. 2010. № 8. С. 89–94. URL: https://elibrary.ru/item.asp?id=17066620

6. Таранцев А.А., Чикитов Ю.И. Модель применения беспилотных летательных аппаратов в целях тушения крупных лесных пожаров в зоне применения наземных сил и средств // Вестник Санкт-Петербургского университета Государственной противопожарной службы МЧС России. 2016. № 2. С. 21–27. URL: https://elibrary.ru/item.asp?id=26183977

7. Бородин В.А., Кузовлев А.В., Харитонов А.А. Тактика тушения лесных пожаров // Пожарная безопасность: проблемы и перспективы. 2018. № 1 (8). С. 83–85. URL: https://elibrary.ru/item.asp?id=36576096

8. Алаторцев А.С. Совершенствование организации тушения лесных пожаров в Самарской обла­сти : магистерская дис. Тольятти, 2017. 113 с.

9. Pepper J., Golden B., Wasil E. Solving the traveling salesman problem with annealing-based heuristics: A computational study // IEEE Transactions on Systems, Man, and Cybernetics — Part A: Systems and Hum. 2002. Vol. 32. Issue 1. Pp. 72–77. DOI: 10.1109/3468.995530

10. Chandran B., Golden B., Wasil E. A computational study of three demon algorithm variants for solving the traveling salesman problem // Computational Modeling and Problem Solving in the Networked World. H.K. Barghava, N. Ye (eds). Boston : Kluwer Academic Publisher, MA, 2003. Pp. 155–175. DOI: 10.1007/978-1-4615-1043-7_8

11. Altinel I.K., Öncan T. A new enhancement of the Clarke and Wright savings heuristic for the capacitated vehicle routing problem // Journal of the Operational Research Society. 2005. Vol. 56. Issue 8. Pp. 954–961. DOI: 10.1057/palgrave.jors.2601916

12. Черепанов Д.А., Ермаков А.С. Экспертная оценка пожарного риска для кемпинга с применением матрицы последствий и вероятностей // Пожаровзрывобезопасность/Fire and Explosion Safety. 2017. Т. 26. № 2. С. 62–71. DOI: 10.18322/PVB.2017.26.02.62-71

13. Швецов В.И. Математическое моделирование транспортных потоков // Автоматика и теле­механика. 2003. Вып. 11. С. 3–46. URL: https://www.mathnet.ru/php/getFT.phtml?jrnid=at&paperid=1966&what=fullt&option_lang=rus

14. Kristina S., Jason. Minimize transportation cost with Clark and Wright algorithm saving heuristic method with considering traffic congestion factor // IOP Conference Series: Materials Science and Engineering. 2019. Vol. 673. Issue 1. P. 012080. DOI: 10.1088/1757-899X/673/1/012080

15. Никоноров В.М. Усовершенствование метода Кларка – Райта для решения задачи маршрутизации автомобильных мелкопартионных пере­возок // Научно-технические ведомости СПбГПУ. 2012. № 1. С. 295–298.

16. Бронштейн Е.М., Зелев П.А. Об оптимальной доставке грузов транспортным средством с учетом стоимости перевозки от загрузки транспортного средства по нескольким циклическим маршрутам // Информатика и ее применения. 2014. Т. 8. № 4. С. 53–57. DOI: 10.14357/19922264140407 URL: https://elibrary.ru/item.asp?id=22846465

17. Бронштейн Е.М., Зелев П.А. Задача маршрутизации транспортного средства с учетом зависимости стоимости перевозок от загрузки // Информационные технологии. 2014. № 4. С. 33–37.

18. Зелев П.А., Бронштейн Е.М. Исследование эффективности модификаций алгоритма Кларка – Райта при решении задач доставки грузов // Информационные технологии интеллектуальной поддержки принятия решения : тр. IV Междунар. конф. Уфа, 2016. С. 94–97.

19. Коробова Л.А., Зеленова Е.Е. Модификация алгоритма Кларка – Райта для оптимизации работы городской транспортной компании : мат. LV отчет. науч. конф. преподавателей и науч. сотрудников ВГУИТ за 2016 г. : в 3 ч. Ч. 2. / под ред. С.Т. Антипова. Воронеж : ВГУИТ, 2017. С. 111–114.

20. Арташес С. Исследование некоторых классических алгоритмов задачи маршрутизации транспорта // World Science. 2019. Vol. 1. Issue 3 (43). Pp. 10–14. DOI: 10.31435/rsglobal_ws/31032019/6398