Scientia Iranica

Scientia Iranica

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

Document Type : Research Article

Authors
Asudeh Shahidi 1
Reza Ramezanian 1
Shahrooz Shahparvari 2
1 Department of Industrial Engineering, K. N. Toosi University of Technology, Tehran, Iran.
2 School of Accounting, Information Systems and Supply Chain, College of Business and Law, RMIT University, Melbourne, Australia.
10.24200/sci.2022.57476.5258
Abstract
Uncoordinated responses are problematic in various operations, especially in crucial circumstances such as bushfires, where they are associated with decreased efficiency, effectiveness, and safety. This paper presents a new Vehicle Routing Problem (VRP) model for routing, scheduling, and coordinating bushfire-related resources, including Ground Resources (GR) and Aerial Resources (ARs) in the suppression phase of a bushfire event. The coordination must be in a way that ARs' operations are allowed prior to GRs' operations; otherwise, aerial interference is unhelpful. The problem is Non deterministic Polynomial time (NP)-hard and cannot be solved in polynomial time using exact methods, but due to the crucial circumstances of bushfires, it should be solved in a reasonable time. Therefore, we propose a greedy heuristic algorithm to solve it. Dividing the bushfire area into a set of  fire sites, we solved instances with different numbers of  fire sites using both CPLEX and the greedy algorithm and compared the results. CPLEX fails to solve the instances with more than three  fire sites, but the greedy algorithm solves the largest instance having 9  fire sites in less than 1 minute. The negligible Relative Percent Difference (RPD) of the greedy algorithm in the first  five instances indicates that our proposed algorithm is reliable.
Keywords
Coordination
Vehicle Routing Problem (VRP)
Scheduling
Bushfire suppression
Greedy heuristic algorithm
Subjects
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, 101967 (2020). https://doi.org/10.1016/j.tre.2020.101967
2. Shahparvari, Sh., Abbasi, B., Chhetri, P., and Abareshi, A. "Fleet routing and scheduling in bushfire emergency evacuation: A regional case study of the Black Saturday bushfires in Australia", Transportation Research Part D: Transport and Environment, (2017). https://doi.org/10.1016/j.trd.2016.11.015
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", (2019). https://www.businessinsider.de/amazon
4. Teague, B., et al., The Fires and the Fire-related Deaths, 2009 victorian bushfires royal commission (2010). 
5. Australian Bushfire Season, 2019-2020-Australian- Bushfires, GFED, (2019-2020). https://globalfiredata.org/pages/2020/01/03
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., et al. "Multiresource scheduling and routing for emergency recovery operations", International Journal of Disaster Risk Reduction, 50, 101780 (2020).
8. Karels, J. and Dudley, M., Yarnell Hill Serious Accident Investigation Report, Arizona State Forestry Division (2013). 
9. Minas, J.P., Hearne, J.W., and Handmer, J.W. "Areviewofoperationsresearch methodsapplicable to wild- fire management", International Journal of Wildland Fire, 21(3), pp. 189-196 (2012).https://doi.org/10.1071/WF10129
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. Rodrguez-Veiga, J., Gomez-Costa, I., Ginzo-Villamayor, M., et al. "Assignment problems 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, 283(1), pp. 1-21 (2017). http://dx.doi.org/10.1007/s10479-017-2598-9
13. Rodriguez-Veiga, J., Ginzo-Villamayor, M., and Casas- Mendez B. "An integer linear programming model to select and temporally allocate resources for fighting forest fires", Forests, 9(10), pp. 231-238, 583 (2018). https://doi.org/10.3390/f901000583
14. Wei, Y., Bevers, M., Belval, E. "A chance-constrained programming model to allocate wildfire initial attack resources for a fire season", Forest Science, 61(2), pp. 278-288 (2014). https://link.springer.com/article/10.5849/forsci.14-112
15. Wei, Y., Belval, E.J., Thompson, M.P., et al. "A simulation and optimisation procedureto model daily suppression resource transfers during a fire season in Colorado", International Journal of Wildland Fire, 26(7), pp. 630-641 (2017). https://doi.org/10.1071/WF16073 AC
16. Lee, Y., Fried, J.S., Albers, H.J., et al. "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). https://doi.org/10.1139/cjfr-2011-0433
17. Cerna, S., Guyeux, C., Royer, G., et al. "Predicting fire brigades operational breakdowns: A real case study", Mathematics, 8(8), 1383 (2020). https://doi.org/10.3390/math8081383
18. Galindres-Guancha, L., Toro-Ocampo, E., and Gallego-Rendon, R. "A biobjective capacitated vehicle routing problem using metaheuristic ils and decomposition", International Journal of Industrial Engineering Computations, 12(3), pp. 293-304 (2021). https://doi.org/10.5267/j.ijiec.2021.2.002
19. Mutar, M., Burhanuddin, M., Hameed, A., et al. "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). https://doi.org/10.5267/j.ijiec.2020.4.006
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). https://doi.org/10.5267/J.IJIEC.2020.4.001
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).https://doi.org/10.5267/j.ijiec.2020.8.001
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). http://dx.doi.org/10.5267/j.ijiec.2021.2.001
23. Shu, J. "An efficient greedy heuristic for warehouseretailer network design optimization", Transportation Science, 44(2), pp. 183-192 (2010). https://doi.org/10.1287/trsc.1090.0302
24. Hojati, M. "A greedy heuristic for shift minimization personnel task scheduling problem", Computers and Operations Re search, 100, pp. 66-76 (2018). https://doi.org/10.1016/j.cor.2018.07.010
25. Martinez-Torres, H.L., Perez-Salicrup, D.R., Castillo, A., et al. "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 NAFC-AR-2017-finalebook. pdf", (2017). http://nafc.org.au/wp-content/uploads/2018/01
27. Chen, D., Batson, R.G., and Dang, Y., Applied Integer Programming: Modeling and Solution, (2011).
28. Huai, C., Sun, G., Qu, R., et al. "Vehicle routing problem with multi-type vehicles in the cold chain logistics system", In International Conference on Service Systems and Service Management, (ICSSSM), IEEE, pp. 1-4 (2019). https://doi.org/10.1109/ICSSSM.2019.8887612
29. Brucker, P. "NP-Completeoperations research problems and approximation algorithms", Zeitschrift fur Operations-Research, 23(3), pp. 73-94 (1979). 
30. Gill, I "Replacement of essential water used during bushfire fighting operations". 
31. Rauchecker, G. and Schryen, G. "An exact branchand- price algorithm for scheduling rescue units during disaster response", European Journal of Operational Research, 272(1), pp. 352-363 (2019). https://doi.org/10.1016/j.ejor.2018.06.010
Scientia Iranica
Volume 32, Issue 16
Transactions on Industrial Engineering
September and October 2025 Article ID:5258

  • Receive Date 05 January 2021
  • Revise Date 01 January 2022
  • Accept Date 03 February 2022