Document Type : Original Article

Authors

1 Department of Industrial Engineering, Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University, Qazvin, Iran.

2 Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran.

Abstract

The firefighter problem on a graph, depending on the environment, the graph can be continuous or discrete, which includes tree, cubic, regular and irregular graphs, etc., is described in such a way that by starting a fire from a series of vertices, the goal is to contain the fire with the maximum number of vertices saved. Our main innovation is to model the firefighter problem with on a bi- objective model, which simultaneously saves the maximum number of vertices with the minimum number of firefighters. The firefighter problem is a type of Np-hard problem, and because we defined the problem as a bi-objective problem and added three constraints to it, the problem became more difficult, and the weighted bi-objective model is also Np-hard. To solve the NP-hard problem, we used multi-objective optimization4 such as Goal Programming (GP), ε- Constraint, Global Criterion Approach, Weighting Sum Method methods. To prove the performance of our method, we used a randomly generated sample.

Keywords

Alvarez Carme, Blesa Maria J., Molter Hendrik (2016) Fireghting as a Game, https://www.researchgate.net/publication/290878736. DOI: 10.1007/978-3-319-13123-8_9
Bazgan, Cristina, Chopina, Morgan and Ries, Bernard (2012) The firefighter problem with more than one firefighter on trees. Discrete Applied Mathematics, 161:899-908.
Duffy, Christopher and MacGillivray, Gary (2019) The Firefighter problem: Saving sets of vertices on cubic graphs.  wileyonlinelibrary.com/journal/net. Networks.;74:62–69.
Duffy, Christopher and Macgillivray, Dr. Gary (2010) An Analysis of The Weighted Firefighter Problem.  Mathematics Subject Classification, 05C57, 05C85.
Hu, Bin, Windbichler, Andreas and Raidl, G¨unther R (2015) A New Solution Representation for the Firefighter Problem. EvoCOP 2015, 9026: 25–35. DOI: 10.1007/978-3-319-16468-7 3.
Michalak, Krzysztof (2018) Crossover Operator Using Knowledge Transfer for the Firefighter Problem. Springer Nature Switzerland AG, 11314: 305–31.
Michalak, Krzysztof (2017) ED-LS - A Heuristic Local Search for the Multiobjective Firefighter Problem.  Applied Soft Computing, S1568-4946(17)30314-9.
Hartnell, B (1995) Firefighter! An application of domination. Presentation, 25thManitoba Conference on Combinatorial Mathematics and Computing, University of Manitoba in Winnipeg, Canada.
Fomin, FedorV., Heggernes, Pinar and Leeuwen, Erik Jan vanb (2015) The Firefighter problem on graph classes. Theoretical Computer Science, 613:38-50.
Finbow, Stephen and MacGillivray, Gary (2009) The firefighter problem: a survey of results, directions and questions.  Australasian Journal of Combinatorics, 43:57–78.
Finbow, Stephen, King, Andrew, MacGillivray, Gary and Rizzi, Romeo (2007) The firefighter problem for graphs of maximum degree three. Discrete Mathematics, 307: 2094 – 2105.
Ramos, Natanael, de Souza, Cid Carvalho and Jussieu de Rezende, Pedro (2019) A matheuristic for the firefighter problem on graphs.  International Transactions Inoperational research, 2019, 00:1–28
Tennenholtz, guy, Caramanis, Constantine and mannor, shie (2017) the stochastic firefighter problem. Computer Science > Systems and Control, arxiv:1711.08237v1 [cs.sy] 22.
Zambon, Mauricio J. O., de Rezende, Pedro J. and C. de Souza, Cid (2018) Solving the geometric firefighter routing problem via integer programming. European Journal of Operational Research,274:1090-1101.
Zambon, Mauricio J.O., de Rezende, PedroJ. and de Souza, Cid C (2018) Finding exact solutions for the Geometric Firefighter Problem in practice. Computers and Operations Research, 97:72-83.
Ramos, Natanael, de Souza, Cid Carvalho and Jussieu de Rezende, Pedro (2019) A matheuristic for the firefighter problem on graphs.  International Transactions Inoperational research, 2019, 00:1–28
Hartnell, B (1995) Firefighter! An application of domination. Presentation, 25thManitoba Conference on Combinatorial Mathematics and Computing, University of Manitoba in Winnipeg, Canada.
Finbow, Stephen and MacGillivray, Gary (2009) The firefighter problem: a survey of results, directions and questions.  Australasian Journal of Combinatorics, 43:57–78.
Tennenholtz, guy, Caramanis, Constantine and mannor, shie (2017) the stochastic firefighter problem. Computer Science > Systems and Control, arxiv:1711.08237v1 [cs.sy] 22.
Xiujuan Lei & Zhongke Shi (2004) Overview of multi-objective optimization methods.
Journal of Systems Engineering and Electronics, Vol .15, No. 2, pp. 142 146.