TY - JOUR
T1 - The Moving Firefighter Problem
AU - Gutiérrez-De-La-Paz, Bruno R.
AU - García-Díaz, Jesús
AU - Menchaca-Méndez, Rolando
AU - Montenegro-Meza, Mauro A.
AU - Menchaca-Méndez, Ricardo
AU - Gutiérrez-De-La-Paz, Omar A.
N1 - Publisher Copyright:
© 2022 by the authors.
PY - 2023/1
Y1 - 2023/1
N2 - The original formulation of the firefighter problem defines a discrete-time process where a fire starts at a designated subset of the vertices of a graph G. At each subsequent discrete time unit, the fire propagates from each burnt vertex to all of its neighbors unless they are defended by a firefighter that can move between any pair of vertices in a single time unit. Once a vertex is burnt or defended, it remains in that state, and the process terminates when the fire can no longer spread. In this work, we present the moving firefighter problem, which is a generalization of the firefighter problem where the time it takes a firefighter to move from a vertex u to defend vertex v is determined by a function (Formula presented.). This new formulation models situations such as a wildfire or a flood, where firefighters have to physically move from their current position to the location of an entity they intend to defend. It also incorporates the notion that entities modeled by the vertices are not necessarily instantaneously defended upon the arrival of a firefighter. We present a mixed-integer quadratically constrained program (MIQCP) for the optimization version of the moving firefighter problem that minimizes the number of burnt vertices for the case of general finite graphs, an arbitrary set (Formula presented.) of vertices where the fire breaks out, a single firefighter, and metric time functions (Formula presented.).
AB - The original formulation of the firefighter problem defines a discrete-time process where a fire starts at a designated subset of the vertices of a graph G. At each subsequent discrete time unit, the fire propagates from each burnt vertex to all of its neighbors unless they are defended by a firefighter that can move between any pair of vertices in a single time unit. Once a vertex is burnt or defended, it remains in that state, and the process terminates when the fire can no longer spread. In this work, we present the moving firefighter problem, which is a generalization of the firefighter problem where the time it takes a firefighter to move from a vertex u to defend vertex v is determined by a function (Formula presented.). This new formulation models situations such as a wildfire or a flood, where firefighters have to physically move from their current position to the location of an entity they intend to defend. It also incorporates the notion that entities modeled by the vertices are not necessarily instantaneously defended upon the arrival of a firefighter. We present a mixed-integer quadratically constrained program (MIQCP) for the optimization version of the moving firefighter problem that minimizes the number of burnt vertices for the case of general finite graphs, an arbitrary set (Formula presented.) of vertices where the fire breaks out, a single firefighter, and metric time functions (Formula presented.).
KW - exact algorithm
KW - firefighter problem
KW - mathematical programming
KW - mixed-integer quadratically constrained programming (MIQCP)
KW - np-hard
KW - spread and containment in networks
UR - http://www.scopus.com/inward/record.url?scp=85145848879&partnerID=8YFLogxK
U2 - 10.3390/math11010179
DO - 10.3390/math11010179
M3 - Artículo
AN - SCOPUS:85145848879
SN - 2227-7390
VL - 11
JO - Mathematics
JF - Mathematics
IS - 1
M1 - 179
ER -