Este Trabajo Fin de Grado (TFG) aborda el problema de la partición estática del espacio para la asignación de tareas, tomando como referencia un escenario inspirado en la sectorización del espacio aéreo: un conjunto de entidades distribuidas en un plano, cada una con una carga asociada, que debe repartirse en sectores de forma equilibrada y razonable desde el punto de vista geométrico. La dificultad principal no está solo en “dividir el mapa”, sino en conseguir quela partición resultante mantenga un buen reparto de carga, evite sectores degenerados y genere fronteras estables, incluso cuando la distribución espacial es irregular y aparecen zonas densas junto con estructuras alargadas tipo flujo.
Para estudiar el problema con control y reproducibilidad, se desarrolla un generador de datos sintéticos que combina hubs (nubes gaussianas) y flujos (corredores lineales con ruido), incorporando además pesos heterogéneos. Sobre estos datos se definen métricas que permiten evaluar soluciones de forma comparable: equilibrio de carga mediante el coeficiente de variación, penalización de capacidad respecto a un rango aceptable, compacticidad normalizada y medidas de robustez ligadas a márgenes o fronteras. Estas métricas se integran en funciones objetivo escalares, lo que permite comparar métodos distintos bajo un mismo marco y analizar los compromisos entre criterios del problema multiobjetivo.
En cuanto a los métodos de partición, se parte de enfoques base como la rejilla ortogonal y k-means, y se exploran variantes que introducen restricciones de capacidad. Sin embargo, el núcleo del trabajo se apoya en técnicas de optimización basadas en EDA (en particular, UMDAc), empleadas para ajustar parámetros y buscar configuraciones que mejoren simultáneamente el equilibrio y la calidad geométrica. Además, se incluye un análisis tipo Pareto para visualizar la relación entre criterios como equilibrio y compacticidad, y así entender mejor qué soluciones son dominantes y cuáles representan compromisos razonables.
Como resultado, se obtiene un procedimiento reproducible que genera particiones coherentes en distintos tamaños de problema, incluyendo escenarios con 20, 50 y 300 entidades. Los experimentos muestran que los métodos simples sirven como referencia, pero se quedan cortos cuando la carga y la geometría entran en conflicto. En cambio, el uso de EDA permite encontrar soluciones más equilibradas y robustas, justificando su aplicación en un problema donde no existe una única respuesta óptima, sino un conjunto de alternativas que deben analizarse con criterios claros. Finalmente, se deja trazabilidad completa mediante ficheros CSV con la asignación de cada entidad a su sector y métricas agregadas, junto con figuras generadas automáticamente, de forma que el análisis pueda repetirse y ampliarse fácilmente.
ABSTRACT
This Final Degree Project addresses the problem of static space partitioning for task assignment, using an airspace sectorization-inspired setting: a set of weighted entities distributed on a 2D plane that must be divided into sectors in a balanced and geometrically meaningful way. The difficulty is not only “splitting the map”, but obtaining a partition that keeps the workload evenly distributed, avoids degenerate sectors, and produces stable boundaries, even when the spatial distribution is irregular and dense areas coexist with elongated flow-like structures.
To study the problem under controlled and reproducible conditions, a synthetic data generator is developed that combines hubs (Gaussian clusters) and flows (noisy linear corridors), also introducing heterogeneous weights. On top of this dataset, several metrics are defined to evaluate solutions consistently: workload balance through the coefficient of variation, a capacity penalty with respect to an acceptable range, normalized compactness, and robustness-related measures linked to margins and internal borders. These metrics are then combined into scalar objective functions, which makes it possible to compare different methods within the same evaluation framework and to analyze trade-offs between criteria within the multiobjective problem.
Regarding partitioning methods, the work starts from baseline approaches such as an orthogonal grid and k-means, and explores variants that introduce soft capacity constraints. The core of the project, however, relies on EDA-based optimization techniques (specifically UMDAc), used to tune parameters and search for configurations that improve balance and geometric quality at the same time. In addition, a Pareto-style analysis is included to visualize the relationship be tween criteria such as balance and compactness, helping to identify non-dominated solutions and understand which results represent reasonable compromises.
As an outcome, the project delivers a reproducible pipeline that generates coherent partitions across different problem sizes, including scenarios with 20, 50, and 300 entities. The experiments show that simple methods are useful as references but fall short when workload and geometry conflict, while EDA helps to find more balanced and robust solutions, which justifies its use in a setting where there is not a single universal optimum but a set of alternatives that must be assessed with clear criteria. Finally, full traceability is provided through CSV outputs containing the final assignment of each entity to a sector and aggregated metrics, together with automatically generated figures, so the analysis can be repeated and extended easily.
Este Trabajo Fin de Grado (TFG) aborda el problema de la partición estática del espacio para la asignación de tareas, tomando como referencia un escenario inspirado en la sectorización del espacio aéreo: un conjunto de entidades distribuidas en un plano, cada una con una carga asociada, que debe repartirse en sectores de forma equilibrada y razonable desde el punto de vista geométrico. La dificultad principal no está solo en “dividir el mapa”, sino en conseguir quela partición resultante mantenga un buen reparto de carga, evite sectores degenerados y genere fronteras estables, incluso cuando la distribución espacial es irregular y aparecen zonas densas junto con estructuras alargadas tipo flujo.
Para estudiar el problema con control y reproducibilidad, se desarrolla un generador de datos sintéticos que combina hubs (nubes gaussianas) y flujos (corredores lineales con ruido), incorporando además pesos heterogéneos. Sobre estos datos se definen métricas que permiten evaluar soluciones de forma comparable: equilibrio de carga mediante el coeficiente de variación, penalización de capacidad respecto a un rango aceptable, compacticidad normalizada y medidas de robustez ligadas a márgenes o fronteras. Estas métricas se integran en funciones objetivo escalares, lo que permite comparar métodos distintos bajo un mismo marco y analizar los compromisos entre criterios del problema multiobjetivo.
En cuanto a los métodos de partición, se parte de enfoques base como la rejilla ortogonal y k-means, y se exploran variantes que introducen restricciones de capacidad. Sin embargo, el núcleo del trabajo se apoya en técnicas de optimización basadas en EDA (en particular, UMDAc), empleadas para ajustar parámetros y buscar configuraciones que mejoren simultáneamente el equilibrio y la calidad geométrica. Además, se incluye un análisis tipo Pareto para visualizar la relación entre criterios como equilibrio y compacticidad, y así entender mejor qué soluciones son dominantes y cuáles representan compromisos razonables.
Como resultado, se obtiene un procedimiento reproducible que genera particiones coherentes en distintos tamaños de problema, incluyendo escenarios con 20, 50 y 300 entidades. Los experimentos muestran que los métodos simples sirven como referencia, pero se quedan cortos cuando la carga y la geometría entran en conflicto. En cambio, el uso de EDA permite encontrar soluciones más equilibradas y robustas, justificando su aplicación en un problema donde no existe una única respuesta óptima, sino un conjunto de alternativas que deben analizarse con criterios claros. Finalmente, se deja trazabilidad completa mediante ficheros CSV con la asignación de cada entidad a su sector y métricas agregadas, junto con figuras generadas automáticamente, de forma que el análisis pueda repetirse y ampliarse fácilmente.
ABSTRACT
This Final Degree Project addresses the problem of static space partitioning for task assignment, using an airspace sectorization-inspired setting: a set of weighted entities distributed on a 2D plane that must be divided into sectors in a balanced and geometrically meaningful way. The difficulty is not only “splitting the map”, but obtaining a partition that keeps the workload evenly distributed, avoids degenerate sectors, and produces stable boundaries, even when the spatial distribution is irregular and dense areas coexist with elongated flow-like structures.
To study the problem under controlled and reproducible conditions, a synthetic data generator is developed that combines hubs (Gaussian clusters) and flows (noisy linear corridors), also introducing heterogeneous weights. On top of this dataset, several metrics are defined to evaluate solutions consistently: workload balance through the coefficient of variation, a capacity penalty with respect to an acceptable range, normalized compactness, and robustness-related measures linked to margins and internal borders. These metrics are then combined into scalar objective functions, which makes it possible to compare different methods within the same evaluation framework and to analyze trade-offs between criteria within the multiobjective problem.
Regarding partitioning methods, the work starts from baseline approaches such as an orthogonal grid and k-means, and explores variants that introduce soft capacity constraints. The core of the project, however, relies on EDA-based optimization techniques (specifically UMDAc), used to tune parameters and search for configurations that improve balance and geometric quality at the same time. In addition, a Pareto-style analysis is included to visualize the relationship be tween criteria such as balance and compactness, helping to identify non-dominated solutions and understand which results represent reasonable compromises.
As an outcome, the project delivers a reproducible pipeline that generates coherent partitions across different problem sizes, including scenarios with 20, 50, and 300 entities. The experiments show that simple methods are useful as references but fall short when workload and geometry conflict, while EDA helps to find more balanced and robust solutions, which justifies its use in a setting where there is not a single universal optimum but a set of alternatives that must be assessed with clear criteria. Finally, full traceability is provided through CSV outputs containing the final assignment of each entity to a sector and aggregated metrics, together with automatically generated figures, so the analysis can be repeated and extended easily. Read More
Related posts:
Casos de éxito en la implementación de bicicletas de carga para reparto urbano
Manipulación y transporte de carga a granel en México y Latinoamérica
Radiografía del robo de transporte de carga en México
Análisis de la relación entre carga de entrenamiento semanal y la HRV, la frecuencia cardíaca en reposo y el sueño en nadadores de alto rendimiento
No dejes que el Año Nuevo Chino hunda tus envíos: cómo planificar de forma inteligente
China realiza nuevas pruebas de drones de carga