Application of Clarke and Wright algorithm in the tasks of forest fire suppression by aviation forest air protection

Introduction. The purpose of this study is to determine the minimum cost of a path to a standstill forest fire and its localization. To achieve this goal, it is necessary to perform the tasks of analyzing the selected method for calculating the minimum costs for the process of unloading a fire landing and the process of localization of a low forest fire accordingly; identifying and characterizing the necessary equipment used in localizing a low forest fire; on definition of the optimal way and the number of employees of the Ministry of Emergency Situations as part of a fire landing force using an algorithm in the form of a pseudocode.

The analytical part. The models, methods and algorithms of search of shortest way, optimization, circulation routing of transport are reviewed. Some problem of extinguishing of forest fire is set. The application of the modi­fied Clarke and Wright algorithm, which considers a possibility of variation of depth of route splice and definition of optimal value of probability of realization of the worsening step, makes it possible to find the minimum time spent by aviation forest protection for localization of a low forest fire. A solution to the problem of fire troop deli­very thanks to pseudocode implementing the basic Clarke and Wright algorithm is given.

Conclusions. The solution based on the modified Clarke and Wright algorithm provides circular air routes that will be assigned to a helicopter, so that the delivery of firefighting troops will become economically feasible. The results of the research will be useful to analysts and software developers for the implementation of aerial firefighting activities.

1. Beresneva E., Avdoshin S. Analysis of mathema­tical formulations of capacitated vehicle routing problem and methods for their solution. Proceedings of the Institute for System Programming of the RAS. 2018; 30(3):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; 11(2):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; 39:97-113.

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

5. Kolyada A.V. Optimization of forest fire extinguishing processes using simulation modeling. Scientific Notes of the Russian State Social University. 2010; 8:89-94. URL: https://elibrary.ru/item.asp?id=17066620 (rus).

6. Tarantsev A.A., Chekistov Yu.I. Model of the unmanned aerial vehicles applying in purpose of forest firefighting in ground forces zone. Bulletin of the St. Petersburg University of the State Fire Service of the Mini­stry of Emergency Situations of Russia. 2016; 2:21-27. URL: https://elibrary.ru/item.asp?id=26183977 (rus).

7. Borodin V.A., Kuzovlev A.V., Kharitonov A.A. Forest fire extinguishing tactics. Fire safety: problems and prospects. 2018; 1(8):83-85. URL: https://elibrary.ru/item.asp?id=36576096 (rus).

8. Alatortsev A.S. Improving the organization of extinguishing forest fires in the Samara region : master’s thesis in specialty. Togliatti, 2017; 113. (rus).

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; 32(1):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 Mo­delling and Problem Solving in the Networked World: Interfaces in Computer Science and Operations Research. Operations Research. H.K. Barghava, N. Ye (eds). Boston, Kluwer Academic Publisher, MA, 2003; 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; 56(8):954-961. DOI: 10.1057/palgrave.jors.2601916

12. Cherepanov D.A., Ermakov A.S. Expert fire risk assessment camping with the use of a matrix of consequences and probability. Pozharovzryvobezopasnost/Fire and Explosion Safety. 2017; 26(2):62-71. DOI: 10.18322/PVB.2017.26.02.62-71 (rus).

13. Shvetsov V.I. Mathematical modeling of traffic flows. Automation and Remote Control. 2003; 11: 3-46. URL: https://www.mathnet.ru/php/getFT.phtml?jrnid=at&paperid=1966&what=fullt&option_lang=rus (rus).

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

15. Nikonorov V.M. Improvement of the Clark and Wright method for solving routing problems of small-party auto­mobile transportation. Scientific and Technical bulletin of SPbSTU. 2012; 1:295-298. (rus).

16. Bronstein E.M., Zelev P.A. About optimum delivery of freights by the vehicle taking into account dependence of cost of transportations on loading of vehicles on several cyclic routes. Informatics and Applications. 2014; 8(4):53-57. DOI: 10.14357/19922264140407 URL: https://elibrary.ru/item.asp?id=22846465 (rus).

17. Bronstein E.M., Zelov P.A. The vehicle routing problem with the transportation cost dependence of vehicle loading. Information Technologies. 2014; 4:33-37. (rus).

18. Zelev P.A., Bronstein E.M. Investigation of the effectiveness of modifications of the Clark-Wright algorithm in solving cargo delivery problems : Proceedings of the fourth international conference “Information technologies of intellectual decision support”. Ufa, 2016; 94-97. (rus).

19. Korobova L.A., Zelenova E.E. Modification of the Clark and Wright algorithm for optimizing the work of a city transport company : Materials of the LV repo­rting scientific conference of VSUIT teachers and researchers for 2016 : in 3 p. Part 2. S.T. Antipov (Ed.). Voronezh, VSUIT, 2017; 111-114. (rus).

20. Artashes S. Investigation of some classical algorithms of the transport routing problem. World Science. 2019; 1(3):10-14. DOI: 10.31435/rsglobal_ws/31032019/6398 (rus).