Shaaban ALI Hoseinpour; Behrouz Afshar Nadjafi; Seyed Taghi Akhavan Niaki
Volume 10, Issue 1 , July 2023, , Pages 77-87
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 ...
Read More
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.