B. Hu, A. Windbichler, G. Raidl:

"A New Solution Representation for the Firefighter Problem";

Talk: Evolutionary Computation in Combinatorial Optimization - EvoCOP 2015, Kopenhagen, Dänemark; 2015-04-08 - 2015-04-10; in: "Evolutionary Computation in Combinatorial Optimization - EvoCOP 2015", G. Ochoa, F. Chicano (ed.); 9026 (2015), ISBN: 978-3-319-16467-0; 25 - 35.

The firefighter problem (FFP) is used as a model to simulate how a fire breaks out and spreads to its surroundings over a discrete time period. The goal is to deploy a given number of firefighters on strategic points at each time step to contain the fire in a most efficient way, so that as many areas are saved from the fire as possible. In this paper we introduce a new solution representation

for the FFP which can be applied in metaheuristic approaches. Compared to the existing approach in the literature, it is more compact in a sense that the solution space is smaller although the complexity for evaluating a solution remains unchanged. We use this representation in conjunction with a variable neighborhood search (VNS) approach to tackle the FFP. To speed up the optimization process, we propose an incremental evaluation technique that omits

unnecessary re-calculations. Computational tests were performed on a benchmark instance set containing 120 random graphs of different size and density. Results indicate that our VNS approach is highly competitive with existing state-of-the-art approaches.

firefighter problem

Created from the Publication Database of the Vienna University of Technology.