A greedy heuristic algorithm to solve a VRP-based model for planning and coordinating multiple resources in emergency response to bushfires

Document Type : Article

Authors

1 Department of Industrial Engineering, K. N. Toosi University of Technology (KNTU), Tehran, Iran

2 School of Accounting, Information Systems and Supply Chain, College of Business and Law, RMIT University, Melbourne, Australia

Abstract

Uncoordinated responses have always caused problems in any kind of operation, in particular, for crucial circumstances it is considerable. As uncoordinated responses in bushfire are also associated with decreased efficiency, effectiveness, and safety, we proposed a new VRP-based mathematical coordination model for routing and allocating resources in fire suppression phase of a bushfire event. The focus of this paper is to plan and coordinate the available resources (ground and aerial resources) for efficient fire suppression. problem is NP-hard, but due to the crucial circumstances of bushfire it should be solved in a reasonable time. Therefore, we proposed an efficient greedy heuristic to solve it. We presented test cases with different characteristics that in those that CPLEX can solve them, the results are compared with the solution of the heuristic. We considered a unit of fire within an incident as a fire site. CPLEX fails to solve cases with more than three fire sites, but the proposed greedy heuristic solves cases with 9 fire sites in less than 1 minute. As the optimality RPD of the heuristic is 00.00% for the first three cases and it is also ignorable in the next two cases, it indicates that our algorithm is reliable.

Keywords


References
[1] Govindan, K., Mina, H., and Alavi, B. ”A decision support system for demand management in healthcare supply chains
considering the epidemic outbreaks: A case study of coronavirus disease 2019 (covid-19)”. Transportation Research Part E:
Logistics and Transportation Review, 138:pp. 101967, (2020).
[2] Shahparvari, Sh., Abbasi, B., Chhetri, P., and Abareshi, A. ”Fleet routing and scheduling in bushfire emergency evacua-
tion: A regional case study of the Black Saturday bushfires in Australia”. Transportation Research Part D: Transport and
Environment, (2017).
[3] Aylin, W. ”The blazes in the Amazon are so big they can be seen from space. One map shows the alarming scale of the fires.”.
https://www.businessinsider.de/amazon-fires-satellite-images-map-of-rainforest-blazes-2019-8?
r=US&IR=T.
[4] Teague, B. et al. ”2009 victorian bushfires royal commission”. (2010).
[5] GFED. ”2019-20 australian bushfire season”. https://globalfiredata.org/pages/2020/01/03/
2019-20-australian-bushfires/.
[6] Kim, K. D., Hossain, Li., and Uddin, S. ”Situated response and learning of distributed bushfire coordinating teams”. Journal
of Homeland Security and Emergency Management, 10(1):pp. 95–111, (2013).
[7] Bodaghi, B., Shahparvari, S., Fadaki, M., Lau, K. H., Ekambaram, P., and Chhetri, P. ”Multi-resource scheduling and routing
for emergency recovery operations”. International Journal of Disaster Risk Reduction, 50:pp. 101780, (2020).
[8] Janice, k. B. and Scott, H. ”Yarnell hill fire serious accident investigation”. https://www.
wildfirelessons.net/HigherLogic/System/DownloadDocumentFile.ashx?DocumentFileKey=
4c98c51d-102c-4e04-86e0-b8370d2beb27&forceDialog=0.
[9] Minas, J. P., Hearne, J. W., and Handmer, J. W. ”A review of operations research methods applicable to wildfire management”.
International Journal of Wildland Fire, 21(3):pp. 189–196, (2012).
[10] Bodaghi, B. and Palaneeswaran, E. ”An optimization model for scheduling emergency operations with multiple teams”.
In Proceedings of the International Conference on Industrial Engineering and Operations Management, Detroit, Michigan,
(2016).
[11] Rodr ́ıguez-Veiga, J., G ́omez-Costa, I., Ginzo-Villamayor, M., Casas-M ́endez, B., and S ́aiz-D ́ıaz, Jos ́e L. ”Assignment prob-
lems in wildfire suppression: Models for optimization of aerial resource logistics”. Forest Science, 64(5):pp. 504–514,
(2018).
[12] Yang, Z., Guo, L., and Yang, Z. ”Emergency logistics for wildfire suppression based on forecasted disaster evolution. Annals
of Operations Research, pages pp. 1–21, (2017).
[13] Rodr ́ıguez-Veiga, J., Ginzo-Villamayor, M., and Casas-M ́endez B. ”An integer linear programming model to select and
temporally allocate resources for fighting forest fires”. Forests, 9(10):pp. 583, (2018).
[14] Wei, Y., Bevers, M., Belval, E., and Bird, B. ”A chance-constrained programming model to allocate wildfire initial attack
resources for a fire season”. Forest Science, 61(2):pp. 278–288, (2014).
[15] Wei, Y., Belval, E. J., Thompson, M. P., Calkin, D. E., and Stonesifer, C. S. ”A simulation and optimisation procedure
to model daily suppression resource transfers during a fire season in Colorado”. International Journal of Wildland Fire,
26(7):pp. 630–641, (2017).
[16] Lee, Y., Fried, J. S., Albers, H. J., and Haight, R. G. ”Deploying initial attack resources for wildfire suppression: spatial
coordination, budget constraints, and capacity constraints”. Canadian Journal of Forest Research, 43(1):pp. 56–65, (2012).
[17] Cerna, S., Guyeux, C., Royer, G., Chevallier C., and Plumerel, G. ”Predicting fire brigades operational breakdowns: A real
case study”. Mathematics, 8(8):pp. 1383, (2020).
[18] Galindres-Guancha, L., Toro-Ocampo, E., and Gallego-Rend ́on, R. ”A biobjective capacitated vehicle routing problem using
metaheuristic ils and decomposition”. International Journal of Industrial Engineering Computations, 12(3):pp. 293–304,
(2021).
[19] Mutar, M., Burhanuddin, M., Hameed, A., Yusof, N., and Mutashar, H. ”An efficient improvement of ant colony system
algorithm for handling capacity vehicle routing problem”. International Journal of Industrial Engineering Computations,
11(4):pp. 549–564, (2020).
[20] Ouaddi, K., Mhada, F., and Benadada, Y. ”Memetic algorithm for multi-tours dynamic vehicle routing problem with overtime
(mdvrpot)”. International Journal of Industrial Engineering Computations, 11(4):pp. 643–662, (2020).
[21] Londono, J., Rendon, R., and Ocampo, E. ”Iterated local search multi-objective methodology for the green vehicle rout-
ing problem considering workload equity with a private fleet and a common carrier”. International Journal of Industrial
Engineering Computations, 12(1):pp. 115–130, (2021).
[22] Suksee, S. and Sindhuchao, S. ”GRASP with alns for solving the location routing problem of infectious waste collection in
the northeast of thailand”. International Journal of Industrial Engineering Computations, 12(3):pp. 305–320, (2021).
[23] Shu, J. ”An efficient greedy heuristic for warehouse-retailer network design optimization”. Transportation Science, 44(2):pp.
183–192, (2010).
[24] Hojati, M. ”A greedy heuristic for shift minimization personnel task scheduling problem”. Computers & Operations Re-
search, 100:pp. 66–76, (2018).
[25] Mart ́ınez-Torres, H. L., P ́erez-Salicrup, D. R., Castillo, A., and Ram ́ırez, M. I. ”Fire management in a natural protected area:
what do key local actors say?”. Human ecology, 46(4):pp. 515–528, (2018).
[26] NAFC. ”Annual report 2017”. http://nafc.org.au/wp-content/uploads/2018/01/
NAFC-AR-2017-final-ebook.pdf.
[27] Chen, D., Batson, R. G., and Dang, Y. Applied integer programming: modeling and solution. (2011).
[28] Huai, C., Sun, G., Qu, R., Gao, Z., and Zhang, Z. ”Vehicle routing problem with multi-type vehicles in the cold chain
logistics system”. In 2019 16th International Conference on Service Systems and Service Management (ICSSSM), pages pp.
1–4. IEEE, (2019).
[29] Brucker, P. ”NP-Complete operations research problems and approximation algorithms”. Zeitschrift f ̈ur Operations-Research,
23(3):pp. 73–94, (1979).
[30] Ian, G. ”Replacement of essential water used during bushfire fighting operations policy”. https://www.ffm.vic.gov.
au/__data/assets/pdf_file/0019/21286/Essential-Water-Replacement-Policy-Nov-2016.pdf.
[31] Rauchecker, G. and Schryen, G. ”An exact branch-and-price algorithm for scheduling rescue units during disaster response”.
European Journal of Operational Research, 272(1):pp. 352–363, (2019).