Talks and Poster Presentations (with Proceedings-Entry):
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.
English abstract:
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.
Keywords:
firefighter problem
Created from the Publication Database of the Vienna University of Technology.