[Zurück]

B. Hu, A. Windbichler, G. Raidl:
"A New Solution Representation for the Firefighter Problem";
Vortrag: Evolutionary Computation in Combinatorial Optimization - EvoCOP 2015, Kopenhagen, Dänemark; 08.04.2015 - 10.04.2015; in: "Evolutionary Computation in Combinatorial Optimization - EvoCOP 2015", G. Ochoa, F. Chicano (Hrg.); 9026 (2015), ISBN: 978-3-319-16467-0; S. 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