Título: Algoritmos metaheurísticos para el Firefighter Problem
Director: Javier Marenco
Jurado: Guillermo Durán y Federico Pousa

Resumen:

El Firefighter Problem es un modelo determinístico de difusión y contención discreta, cuyo objetivo es proteger una superficie para que no sea alcanzada por la propagación del fuego que nace de uno o más focos de incendio. El área bajo afectación de las llamas se la representa con un grafo, y el «fuego» inicial se ubica en uno o más vértices en el tiempo 0. En cada intervalo de tiempo posterior, el fuego avanza y se propaga por aquellos vértices vecinos que no se encuentren protegidos, hasta que no sea capaz de expandirse más.

Entre las distintas versiones del problema, existen objetivos como determinar si es posible proteger un cierto grupo de vértices o porcentaje del grafo, determinar si es posible contener al fuego cuando el área es infinita, o minimizar la cantidad de vértices alcanzados por las llamas.

Se han realizado numerosos avances teóricos sobre árboles y grillas infinitas con un foco de incendio, sin embargo no hay muchos trabajos sobre la resolución de instancias finitas. La presente tesis aborda la resolución práctica y análisis de grillas finitas chicas, medianas y grandes con distinto número de defensores y fuego inicial por medio de algoritmos exactos utilizando programación entera y algoritmos metaheurísticos basados en algoritmos genéticos y colonia de hormigas.