Simheuristics for the Multiobjective Nondeterministic Firefighter Problem in a Time-Constrained Setting

Krzysztof Michalak, Joshua D. Knowles

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Citations (Scopus)
182 Downloads (Pure)

Abstract

The firefighter problem (FFP) is a combinatorial problem requiring the allocation of ‘firefighters’ to nodes in a graph in order to protect the nodes from fire (or other threat) spreading along the edges. In the original formulation the problem is deterministic: fire spreads from burning nodes to adjacent, unprotected nodes with certainty.
In this paper a nondeterministic version of the FFP is introduced where fire spreads to unprotected nodes with a probability PspPsp (lower than 1) per time step. To account for the stochastic nature of the problem the simheuristic approach is used in which a metaheuristic algorithm uses simulation to evaluate candidate solutions. Also, it is assumed that the optimization has to be performed in a limited amount of time available for computations in each time step.
In this paper online and offline optimization using a multipopulation evolutionary algorithm is performed and the results are compared to various heuristics that determine how to place firefighters. Given the time-constrained nature of the problem we also investigate for how long to simulate the spread of fire when evaluating solutions produced by an evolutionary algorithm. Results generally indicate that the evolutionary algorithm proposed is effective for Psp≥0.7Psp≥0.7, whereas for lower probabilities the heuristics are competitive suggesting that more work on hybrids is warranted.
Original languageEnglish
Title of host publicationApplications of Evolutionary Computation
Subtitle of host publication19th European Conference, EvoApplications 2016, Porto, Portugal, March 30 - April 1, 2016, Proceedings, Part II
EditorsGiovanni Squillero, Paolo Burelli
PublisherSpringer
Pages248-265
VolumeLNCS 9598
ISBN (Electronic)9783319311531
ISBN (Print)9783319311524
DOIs
Publication statusPublished - 2 Apr 2016
EventEvolutionary Algorithms and Meta-heuristics in Stochastic and Dynamic Environments (EVOSTOC 2016) - Porto, Portugal
Duration: 30 Mar 20161 Apr 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9598
ISSN (Electronic)0302-9743

Conference

ConferenceEvolutionary Algorithms and Meta-heuristics in Stochastic and Dynamic Environments (EVOSTOC 2016)
Country/TerritoryPortugal
CityPorto
Period30/03/161/04/16

Fingerprint

Dive into the research topics of 'Simheuristics for the Multiobjective Nondeterministic Firefighter Problem in a Time-Constrained Setting'. Together they form a unique fingerprint.

Cite this