Modelos y algoritmos para el Moving Firefighter Problem.
Loading...
Date
2025
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción
Abstract
Esta tesis aborda el Moving Firefighter Problem (MFP), una extensión del clásico Firefighter Problem (FP), que modela la contención de fenómenos que se propagan en redes. El MFP introduce una representación más realista del problema al incorporar el movimiento de los bomberos en la red, cuya capacidad de respuesta depende de las distancias euclidianas entre nodos. Esta consideración hace que el tiempo de protección ya no sea uniforme y aumenta significativamente la complejidad del problema, lo que incrementa notablemente los tiempos de resolución. Actualmente, solo existe un modelo de programación cuadrática en la literatura, que resuelve eficientemente tamaños pequeños del problema. Para enfrentar este desafío, se proponen tres enfoques: un modelo de programación lineal entera, un modelo de programación con restricciones, y una metaheurística basada en el Iterated Local Search y Simulated Annealing (ILS-SA). Este último combina perturbaciones controladas con una búsqueda local con dos tipos de intensidades, junto con un mecanismo de aceptación probabilística dependiente de una temperatura que desciende a medida que avanzan las iteraciones. Esta estrategia permite equilibrar exploración e intensificación, mejorando la calidad de las soluciones y evitando quedar atrapado en óptimos locales. Los modelos y algoritmo propuestos son validados en un conjunto de 160 instancias de la literatura. Los resultados computacionales evidenciaron que el modelo de programación con restricciones logró encontrar mejores soluciones o cercanas al óptimo en tiempos de cómputo considerablemente más bajos que los modelos de programación cuadrática y lineal entera. Por su parte, el ILS-SA obtuvo soluciones competitivas con una notable reducción del tiempo de cómputo, destacando su utilidad para instancias de mayor tamaño o escenarios donde se requiere una respuesta rápida.
This thesis addresses the Moving Firefighter Problem (MFP), an extension of the classical Firefighter Problem (FP), which models the containment of spreading phenomena in networks. The MFP introduces a more realistic representation of the problem by incorporating the movement of firefighters within the network, where their response capacity depends on the Euclidean distances between nodes. This consideration makes the protection time non-uniform and significantly increases the problem’s complexity, which in turn greatly extends solution times. Currently, only one quadratic programming model exists in the literature, capable of efficiently solving small-sized instances of the problem. To tackle this challenge, three approaches are proposed: an integer linear programming model, a constraint programming model, and a metaheuristic based on Iterated Local Search and Simulated Annealing (ILSSA). The latter combines controlled perturbations with a local search featuring two levels of intensity, along with a probabilistic acceptance mechanism that depends on a temperature value decreasing as iterations progress. This strategy allows for a balance between exploration and intensification, improving solution quality and helping avoid entrapment in local optima. The proposed models and algorithm are validated on a benchmark set of 160 instances from the literature. Computational results showed that the constraint programming model was able to find better or near-optimal solutions in significantly lower computation times compared to the quadratic and integer linear programming models. Meanwhile, the ILS-SA produced competitive solutions with a notable reduction in computational time, highlighting its usefulness for larger instances or scenarios requiring rapid responses.
This thesis addresses the Moving Firefighter Problem (MFP), an extension of the classical Firefighter Problem (FP), which models the containment of spreading phenomena in networks. The MFP introduces a more realistic representation of the problem by incorporating the movement of firefighters within the network, where their response capacity depends on the Euclidean distances between nodes. This consideration makes the protection time non-uniform and significantly increases the problem’s complexity, which in turn greatly extends solution times. Currently, only one quadratic programming model exists in the literature, capable of efficiently solving small-sized instances of the problem. To tackle this challenge, three approaches are proposed: an integer linear programming model, a constraint programming model, and a metaheuristic based on Iterated Local Search and Simulated Annealing (ILSSA). The latter combines controlled perturbations with a local search featuring two levels of intensity, along with a probabilistic acceptance mechanism that depends on a temperature value decreasing as iterations progress. This strategy allows for a balance between exploration and intensification, improving solution quality and helping avoid entrapment in local optima. The proposed models and algorithm are validated on a benchmark set of 160 instances from the literature. Computational results showed that the constraint programming model was able to find better or near-optimal solutions in significantly lower computation times compared to the quadratic and integer linear programming models. Meanwhile, the ILS-SA produced competitive solutions with a notable reduction in computational time, highlighting its usefulness for larger instances or scenarios requiring rapid responses.
Description
Tesis presentada para optar al grado de Magíster en Ingeniería Industrial.
Keywords
Moving Firefighter Problem, Programación lineal, Simulated annealing (Mathematics), Algoritmos