Análisis de la eficiencia de los sistemas de colonias de hormigas para problemas de accesibilidad

Abstract

A pesar de los avances en materia de predicción, los desastres naturales siguen teniendo
consecuencias devastadoras. Entre los principales problemas a los que se enfrentan los
equipos de ayuda y rescate después de un desastre natural o provocado por el hombre
se encuentra la planificación de las tareas de reparación de carreteras para conseguir la
máxima ventaja de los limitados recursos económicos y humanos.
En la presente Tesis Fin de Máster se intenta dar solución al problema de la accesibilidad,
es decir, maximizar el número de supervivientes que consiguen alcanzar el centro regional
más cercano en un tiempo mínimo mediante la planificación de qué carreteras rurales
deberían ser reparadas dados unos recursos económicos y humanos limitados. Como se
puede observar, es un problema combinatorio ya que el número de planes de reparación
y conexiones entre las ciudades y los centros regionales crece de forma exponencial con el
tamaño del problema.
Para la resolución del problema se comienza analizando una adaptación básica de los
sistemas de colonias de hormigas propuesta por otro autor y se proponen múltiples mejoras
sobre la misma. Posteriormente, se propone una nueva adaptación más avanzada de los
sistemas de colonias de hormiga al problema, el ACS con doble hormiga. Este sistema
hace uso de dos tipos distintos de hormigas, la exploradora y la trabajadora, para resolver
simultáneamente el problema de encontrar los caminos más rápidos desde cada ciudad a
su centro regional más cercano (exploradora), y el de obtener el plan óptimo de reparación
que maximice la accesibilidad de la red (trabajadora).
El algoritmo propuesto se ilustra por medio de un ejemplo de gran tamaño que simula
el desastre natural ocurrido en Haití, y su rendimiento es comparado con la combinación
de dos metaheurísticas, GRASP y VNS.---ABSTRACT---In spite of the advances in forecasting, natural disaster continue to ocasionate devastating
consequences. One of the main problems relief teams face after a natural or man-made
disaster is how to plan rural road repair work to take maximum advantage of the limited
available financial and human resources.
In this Master´s Final Project we account for the accesability issue, that is, to maximize
the number of survivors that reach the nearest regional center in a minimum time
by planning whic rural roads should be repaired given the limited financial and human
resources. This is a combinatorial problem since the number of possible repairing solutions
and connections between cities and regional centers grows exponentially with the size of
the problem.
In order to solve the problem, we analyze the basic ant colony system adaptation proposed
by another author and point out multiple improvements on it. Then, we propose a
novel and more advance adaptation of the ant colony systems to the problem, the double-
ant ACS. This system makes use of two diferent type of ants, the explorer and the worker,
to simultaneously solve the problem of finding the shorthest paths from each city to their
nearest regional center (explorer), and the problem of identifying the optimal repairing
plan that maximize the network accesability (worker).
The proposed algorithm is illustrated by means of a big size example that simulates the
natural disaster occurred in Haiti, and its performance is compared with a combination
of two metaheuristics, GRASP and VNS.