Maximización con técnicas metaheurísticas de la Región de Voronoi de alcance limitado de un nuevo punto en un Diagrama de Voronoi de alcance limitado.

Abstract

Este proyecto aborda el problema de encontrar la posición óptima de un nuevo punto en un Diagrama de Voronoi de alcance limitado de forma que el área de su región asociada sea máxima. A diferencia de los Diagramas de Voronoi clásicos, que asumen una influencia ilimitada de cada punto en el plano, los de alcance limitado restringen cada región a un radio fijo r medido en distancia euclídea, modelando mejor problemas reales como redes de antenas o cadenas de establecimientos con zona de servicio acotada.

Para resolver este problema se ha desarrollado MAXVorAL, una aplicación interactiva programada en Python con interfaz gráfica basada en PySide6. La herramienta permite al usuario definir y manipular nubes de puntos, visualizar ambos tipos de diagramas de Voronoi en tiempo real y aplicar cuatro técnicas metaheurísticas: Random Search, Simulated Annealing, Algoritmo Genético y Ant System (mediante el enfoque ACOR para dominios continuos). Cada metaheurística recibe la nube de puntos, el radio y los límites del dominio, y devuelve el mejor punto encontrado junto con el área de su región y los puntos evaluados durante la búsqueda, que se visualizan sobre la herramienta al finalizar.

Los experimentos se realizaron sobre 250 instancias generadas aleatoriamente, con 50 conjuntos de 25, 50, 100, 150 y 200 puntos. Los parámetros de cada algoritmo se ajustaron mediante búsqueda en rejilla sobre instancias independientes. Los resultados muestran que el Algoritmo Genético obtiene consistentemente el mayor porcentaje de área, especialmente conforme aumenta el número de puntos, siendo también competitivo en tiempo. Ant System ofrece resultados similares en calidad pero con el mayor coste temporal. Random Search y Simulated Annealing son los más rápidos, siendo Random Search una alternativa razonable cuando el tiempo es la principal restricción.

This project addresses the problem of finding the optimal position for a new point in a Limited Range Voronoi Diagram such that the area of its associated region is maximized. Unlike classical Voronoi Diagrams, which assume unlimited influence of each point in the plane, limited range diagrams restrict each region to a fixed radius r measured in Euclidean distance, better modeling real problems such as antenna networks or service chains with a bounded coverage area.

To solve this problem, MAXVorAL has been developed, an interactive application programmed in Python with a graphical interface based on PySide6. The tool allows the user to define and manipulate point sets, visualize both types of Voronoi diagrams in real time, and apply four metaheuristic techniques: Random Search, Simulated Annealing, Genetic Algorithm and Ant System (using the ACOR approach for continuous domains). Each metaheuristic receives the point set, the radius and the domain bounds, and returns the best point found along with its region area and the points evaluated during the search, which are displayed on the tool upon completion.

Experiments were carried out on 250 randomly generated instances, with 50 sets of 25, 50, 100, 150 and 200 points. The parameters of each algorithm were tuned using grid search on independent instances. Results show that the Genetic Algorithm consistently achieves the highest area percentage, especially as the number of points grows, while also being competitive in execution time. Ant System offers similar solution quality but with the highest computational cost. Random Search and Simulated Annealing are the fastest, with Random Search being a reasonable alternative when time is the main constraint.