Repositorio USM (Universidad Técnica Federico Santa María)
Not a member yet
423 research outputs found
Sort by
Decomposition-based Matheuristics for Green Vehicle Routing Problems
No full text.Doctorado en Ingeniería Informátic
Impact evaluation of experience on efficacy of an architectural design decision-making technique
No full textLa literatura sobre ingeniería de software describe una serie de técnicas para la toma de decisiones de diseño de arquitectura, entre las cuales encontramos TaSPeR ("Tactics Selection Poker"), técnica utilizada para la selección de tácticas arquitecturales basa en "Planing Poker". Sin embargo, falta conocimiento sobre el impacto de la experiencia de quienes utilizan técnicas basadas en la selección de tácticas, sobre su eficacia. Este artículo aborda esta brecha de investigación a través de un estudio experimental sonre el impacto de la experiencia de los miembros de equipos que toman decisiones de diseño de arquitectura de software mediante la selección de tácticas arquitecturales, sobre la eficacia de la técnica TaSPeR para la correcta selección de estas tácticas. Un conjunto de 24 desarrolladores, profesionales de TI, se dividieron en dos equipos de "expertos" y dos de "novatos" (de seis personas cada uno); cada equipo tenía que resolver dos escenarios, uno usando TaSPeR y otros usando una técnica ad-hoc; los escenarios fueron cruzado para mitigar posibles efectos de aprendizaje. Se definieron como métricas de eficacia de TaSPeR la variación al usar la técnica (respecto a no usarla) de sus rendimientos en términos de "precision", "recall" y "accuracy" (tácticas seleccionadas versus una "gound truth"); el imacto de la experiencia de los equipos en la eficacia de la técnica se evaluó comparando los valores de las métricas de eficacia obtenidos por los equipos "novatos" con los obtenidos por los "expertos". Los resultados iniciales sugieren que TaSPeR mejora la eficacia de los equipos "novatos", pero la perjudica en el caso de los "expertos". Este resultado es bastante inesperado y requiere replicación con poblaciones aún más grandes de profesionales de TI (no es un tarea fácil). Si se confirman los resultados, la pregunta que surgirá es: si las técnicas de consenso son tan buneas para estimar, ¿por qué afectaríab a la toma de decisiones de equipos expertos?Magíster en Ciencias de la Ingeniería Informátic
Estrategias heurísticas para la solución eficiente del problema de enrutamiento, nivel de modulación y asignación de espectro en redes ópticas elásticas con operación estática
No full textEn este trabajo de tesis se resuelve problema RMLSA en redes ópticas elásticas estáticas. Con este objetivo, se desarrollaron dos algoritmos para resolver los problemas del enrutamiento y nivel de modulación; mientras que se desarrollaron otros dos algoritmos para resolver el problema de la asignación de espectro. Los algoritmos de enrutamiento pretenden balancear el ancho de banda total demandado en cada enlace de la red usando las rutas más cortas que exigen el menor número de FSUs. Para el cálculo de las rutas, además, los algoritmos tienen en consideración las degradaciones que experimenta la señal óptica durante su propagación por la capa física. Para lograr un correcto balanceo de la red, la selección de rutas se realiza utilizando tres métricas diferentes: el número máximo de FSUs exigidos a cada enlace, el número máximo de FSUs exigidos en cada ruta, y una medida de costo de la ruta. De esta manera, las rutas se eligen una a una, equilibrando la demanda de ancho de banda en cada enlace de la red.
Por otro lado, los algoritmos de asignación de espectro propuestos buscan minimizar la fragmentación espectral introducida en la red mediante el desarrollo de un nuevo paradigma de asignación de espectro, buscando usuarios para un subconjunto dado del espectro de frecuencias, en lugar de los enfoques estándar de asignación de espectro. De esta forma, al tener menor fragmentación, se logra disminuir la capacidad total requerida en la red para atender a todos los usuarios.
Los algoritmos de enrutamiento y asignación de espectro fueron evaluados en topologías de redes reales, aprovechando la operación de red estática para ordenar los usuarios previo a la asignación de espectro. El problema RMLSA entonces se resuelve utilizando estrategias basadas tanto en el enrutamiento, la asignación de espectro, como en ambos enfoques combinados.Magíster en Ciencias de la Ingeniería Electrónic
Iot based approach for load monitoring and activity recognition in smart homes
No full textAppliance load monitoring in smart homes has been gaining importance due to its significant advantages in achieving an energy e cient smart grid. The methods to manage such processes can be classified into hardware-based methods, including intrusive load monitoring (ILM) and software-based methods referring to non-intrusive load monitoring (NILM). ILM is based on low-end meter devices attached to home appliances in opposition to NILM techniques, in which only a single point of sensing is needed. Although ILM solutions are relatively expensive, they provide higher e ciency and reliability rather than NILMs do. Moreover, future solutions are expected to be hybrid, combining the benefits of NILM along with individual power measurement by smart plugs and smart appliances. This thesis proposes a novel ILM approach for load monitoring that aims to develop an activity recognition system based on an IoT architecture. The proposed IoT architecture consists of an appliances layer, a perception layer, a communication network layer, a middleware layer, and an application layer. The application layer consists of an appliance recognition module and activities of daily living (ADL) classification algorithm. The main function of the appliance recognition module is to label sensor data and to allow the implementation of di erent home applications. Three di erent classifier models are tested using real data from the UK-DALE dataset: feed-forward neural network (FFNN), long short-term memory (LSTM), and support vector machine (SVM). The developed ADL algorithm maps each ADL to a set of criteria depending on the appliance used. The features are extracted according to the consumption in Watt-hours and the times where appliances are switched on. In the FFNN and the LSTM networks, the accuracy is above 0.9 while being around 0.8 for the SVM network. Other experiments are performed to evaluate the classifier model using a test set. A sensitivity analysis is also carried out to study the impact of the group size on the classifier accuracy. Once results were obtained, the proposed ADL classification system was enhanced in two frameworks: a training framework and an inference framework. This is to allow a practical implementation of the system. In this regard, several modifications were made in the appliance recognition module, including the use of new data, and therefore new appliances: an electric vehicle, an oven and a microwave, from the Dataport dataset. The frameworks include graphical interfaces that significantly facilitate its use. The dataset configuration, pre-processing and classification parameters can be easily selected and modified. In the feature extraction, inside a sliding window, statistical features of the power samples are computed. In this way, the same pre-processing can be applied in the two di erent datasets. A feature importance analysis can also be rerformed to analyze the contribution of the selected features in the models predictions. With this implementation, the real-time operation is directly related with the size of the window used.El monitoreo de carga de electrodomésticos en hogares inteligentes ha ido ganando importancia debido a sus múltiples ventajas para lograr una red eléctrica inteligente eficiente. Los métodos para administrar dichos procesos se pueden clasificar en métodos basados en hardware, conocidos como monitoreo de carga intrusivo (ILM) y los métodos basados en software que se refieren al monitoreo de carga no intrusivo (NILM). ILM se basa en dispositivos de medición de gama baja conectados a electrodomésticos en oposición a las técnicas NILM, donde solo se necesita un único punto de detección. Aunque las soluciones ILM son relativamente caras, estas brindan mayor eficiencia y confiabilidad que las soluciones NILM. Además, se espera que las soluciones futuras sean híbridas, combinando los
beneficios de NILM junto a la medición de energía individual mediante enchufes y electrodomésticos inteligentes. Esta tesis propone un novedoso enfoque ILM para el monitoreo de carga que tiene como objetivo desarrollar un sistema de reconocimiento de actividad basado en una la arquitectura IoT. La arquitectura de IoT propuesta en este estudio consta de una capa de dispositivos, una capa de percepción, una capa de red de comunicación, una capa de middleware y una capa de aplicación. El sistema propuesto consta de un módulo de reconocimiento de electrodoméesticos y un algoritmo de clasificación de actividades diarias (ADLs). La función principal del módulo de reconocimiento de electrodomésticos es etiquetar los datos de los sensores y permitir la implementación de diferentes aplicaciones domésticas. Se prueban tres modelos de clasificadores diferentes utilizando datos reales del dataset UK-DALE: feed fordward neural network (FFNN), long short-term memory (LSTM) y support vector machine (SVM). El algoritmo de ADL desarrollado asigna cada ADL a un conjunto de criterios según el dispositivo utilizado. Las características se extraen según el consumo en Watt-hora y los timestamps en que estos se encienden. En las redes FFNN y LSTM, la precisión está por encima de 0,9 mientras que en la red SVM la misma es de alrededor de 0,8. Se realizan otros experimentos para evaluar el modelo de clasificador utilizando un nuevo conjunto de prueba. También se lleva a cabo un análisis de sensibilidad para estudiar el impacto del tamaño del grupo en la precisión del clasificador. Una vez que se obtuvieron los resultados, el sistema de clasificación de ADL propuesto se integró en dos frameworks de implementación: un framework de entrenamiento y otro de inferencias. Esto con el fin de permitir una implementación práctica del sistema. Para ello, se realizaron varias modificaciones en el módulo de reconocimiento de electrodomésticos, incluyendo el uso de nuevos datos pertenecientes a nuevos dispositivos: un vehículo eléctrico, un horno y un microondas, del dataset Dataport. Los frameworks incluyen interfaces gráficas que facilitan significativamente su uso. Los parámetros de clasificación, preprocesamiento y configuración del conjunto de datos se pueden seleccionar y modificar fácilmente. En la extracción de características una ventana deslizante calcula las características estadísticas
de las muestras de potencia. De esta forma, se puede aplicar el mismo preprocesamiento en los dos datasets. Adicionalmente se puede realizar un análisis de importancia de las características para analizar la contribución de las características seleccionadas en las predicciones de los modelos. Con los frameworks propuestos, la operación en tiempo real está directamente relacionada con el tamaño de la ventana.Magíster en Ciencias de la Ingeniería Electrónic
Estimación del flujo de aire glotal mediante filtraje y suavizamiento de Kalman usando modelos de bajo orden
No full textLas patologías relacionadas con la voz son un problema de creciente importancia en materia de salud pública. Identi car las condiciones de abuso y/o mal uso del mecanismo vocal (es decir, la hiperfunción vocal) que, mantenidas en un período de tiempo, derivan en dichas patologías, es clave para poder prevenirlas y/o tratarlas. Métricas objetivas que han mostrado ser adecuadas para evaluar la presencia de hiperfunción vocal son las características aerodinámicas del flujo de aire que pasa por la glotis. En consecuencia, estimar el flujo de aire glotal resulta de gran apoyo en la tarea de prevenir y/o tratar trastornos comunes de la voz.
Si bien ya es posible obtener estimaciones del flujo de aire glotal en un ambiente de laboratorio, la literatura reciente se ha enfocado en realizarlo de manera ambulatoria y no invasiva. La evaluación ambulatoria permite caracterizar el comportamiento vocal asociado al uso de la voz durante las actividades diarias de los sujetos, lo que supone una evaluación de la hiperfunción vocal más con able con respecto a la evaluación en laboratorio. Para ello, se ha propuesto el modelo basado en impedancia subglotal, el cual modela, en el dominio de la frecuencia, al sistema respiratorio junto a la piel y sus propiedades, para estimar el flujo de aire glotal a partir de las mediciones de un acelerómetro puesto sobre la piel del cuello. En la presente tesis se trata el problema de estimar el ujo de aire glotal utilizando un enfoque Bayesiano aplicado sobre modelos en variables de estado de bajo orden. Este tipo de enfoques entrega una medida de la incertidumbre que existe en las estimaciones, al mismo tiempo que aminora el error producido al estimar el flujo de aire glotal con una vocal distinta a la utilizada para calibrar el modelo. Para realizar lo anterior, se obtiene una representación en variables de estado del modelo basado en impedancia subglotal, para luego utilizar un suavizador de Kalman y así estimar el ujo de aire glotal a partir de la aceleración que se produce sobre la piel del cuello. La contribución principal de esta tesis es la de proveer estimaciones del flujo de aire glotal mediante el uso de un suavizador de Kalman aplicado sobre un modelo en variables de estado de bajo orden. Los resultados numéricos obtenidos son similares a los de enfoques existentes en la literatura. Sin embargo, el esquema propuesto involucra un costo computacional bastante menor que otros esquemas Bayesianos presentes en la literatura. A su vez, el enfoque Bayesiano provee una medida de la incertidumbre en las estimaciones, lo que constituye información valiosa en un ambiente ambulatorio.Voice-related pathologies are a problem of growing importance in public health. Identifying the conditions of abuse and/or misuse of the vocal mechanism (i.e. vocal hyperfunction) that lead to these pathologies, is key to be able to prevent and/or treat them. Objective metrics that have shown to be adequate to assess the presence of vocal hyperfunction are the aerodynamic characteristics of the air ow through the glottis. In conclusion, estimating the glottal air ow may help in the task of preventing and/or treating common voice disorders. Although it is already possible to obtain estimates of the glottal air
ow in a laboratory environment, the state-of-art is focused on ambulatory and non-invasive monitoring. Ambulatory assessment allows to characterize the vocal behavior associated with the voice during the subjects' daily activities, which suppose a more reliable assessment of the vocal hyperfunction with respect to laboratory assessment. With this aim, the subglottal impedance-based model has been proposed in the frequency domain, to model the respiratory system together the skin and its properties. This model has been used to estimate the glottal air ow from measurements of an accelerometer placed on the neck skin. This thesis deals with the problem of estimating the glottal air ow using a Bayesian approach based on low order state-space models. Speci cally, the proposed approach yields a measure of the uncertainty in the estimates, at the same time that reduces the error produced when the glottal air ow is estimated with a di erent vowel that the one used to calibrate the model. To carry out the above, a state-space representation for the subglottal impedance-based model is obtained, to then use a Kalman smoother and, in this way, to estimate the glottal air ow from the acceleration produced on the neck skin. The main contribution in this thesis is to provide estimates of the glottal air ow through the use of a Kalman smoother based on a low order state-space model. The obtained numerical results are similar to current approaches presented in the literature. The proposed scheme, however, involves a lower computational cost, at the same time that it provides a measure of the uncertainty in the estimates, which is equivalent to valuable information in an ambulatory environment.Magíster en Ciencias de la Ingeniería Electrónic
Apoyo a la comparación de múltiples corpus a través de la exploración visual de modelado de tópicos
No full textEl constante aumento en el volumen de datos de tipo texto ha llevado al desarrollo de varios
algoritmos destinados a resumir y comprender este tipo de datos. Una solución prometedora
este problema es el modelado de temas (en inglés conocido como topic modeling), un enfoque estadístico para extraer temas de alto volúmenes de datos. Humanos que interactúan e interpretan directamente el resultado de estos algoritmos pueden usar herramientas de visualización para interpretar mejor los resultados, sin embargo, estas herramientas todavía
tienen una limitación significativa. Las representaciones visuales actuales permiten refinar y
comparar temas basados solo en sus palabras claves, lo que genera un rendimiento deficiente
cuando estas son demasiado genéricas, están mal conectadas o no proporcionan suficiente
información. Para abordar este problema, propongo TopicVisExplorer, un conjunto de visualizaciones interactivas que soporta Latent Dirichlet Allocation (LDA). Esta propuesta tiene
por objetivo ayudar a los usuarios durante el refinamiento y comparación de temas. Tres
innovaciones claves de este trabajo buscan apoyar refinamiento del modelo de tema e identificar temas similares de uno o dos corpus. (1) Propongo un algoritmo de fusión de temas que considera tanto términos como documentos de los tópicos, (2) un nuevo algoritmo de división de temas basado en sus documentos, (3) y una métrica que estima la similitud entre temas en base a sus palabras y documentos más relevantes. Realice un estudio de usuarios con 95 usuarios no expertos para evaluar las funcionalidades de TopicVisExplorer. Los resultados muestran que los participantes pudieron identificar los temas que necesitan mejorar su calidad. Aproximadamente la mitad de los participantes mejoraron la coherencia de su modelo después de aplicar operaciones de división y fusión de temas. Además, los participantes pudieron identificar temas similares entre dos corpus. Aquellos que utilizaron la métrica de similitud propuesta cometieron menos errores que aquellos que usaron una métrica base.Magíster en Ciencias de la Ingeniería Informátic
Fake news detection model for the early stages of the spread
No full textEl masivo uso de redes sociales ha permitido un aumento explosivo de noticias falsas circulantes en la red. La principal razón es que este tipo de contenido puede ser creado y publicado rápidamente a un costo nulo, comparado con medios tradicionales como el periódico. Realizar un análisis de veracidad a cada una de estas noticias es una tarea imposible de realizar manualmente debido al esfuerzo humano requerido y al gran volumen de información que se produce cada hora, por lo que es necesario buscar medios de verificación automáticos que clasifiquen estos contenidos dentro de las primeras horas en que fueron emitidos. Este problema ha sido de gran interés para la comunidad académica donde se han creando diversos mecanismos para la detección de noticias falsas, principalmente basados en técnicas de deep learning y machine learning. No obstante, existen pocos trabajos específicamente diseñados para resolver la tarea de detección temprana, que utilicen tanto contenido como contexto para la clasificación. Por esta razón, en este trabajo proponemos un nuevo modelo de detección temprana de noticias falsas condicionado a las primeras etapas de la propagación. El modelo llamado Early Rumor Detection Model (ERDM), compuesto por una red Bi-GRU con un módulo de atención global, recibe en cada tiempo tanto características de la propagación de los mensajes (texto y tiempo) como información de los usuarios que participan en las conversaciones. Los resultados muestran que ERDM sobrepasa a los métodos de la literatura, tanto para escenario a 4 clases como binario, donde en este último escenario se consigue una mejora de 7% y 13.4% en los datasets Twitter 15 y Twitter 16 respectivamente. Además, ERDM supera los resultados del estado del arte en detección temprana obteniendo sobre 80% en accuracy en ambos datasets dentro de las primeras 4 horas de difusión de una noticia.The massive use of social networks has allowed an explosive increase of fake news circulating on the web. The main reason is that this type of content can be created and published quickly and at zero cost, compared to traditional media such as newspapers. Performing a veracity analysis of each of these news items is an impossible task to perform manually due to the human effort required and the large volume of information that is produced every hour, so it is necessary to find automatic methods of verification that classify these contents within the first hours after they were published.
This problem has been of great interest to the academic community where several mechanisms for the detection of fake news have been created, mainly based on techniques of Ddeep learning and Machine learning. However, there are few works specifically designed to solve the early detection task, using both content and context for classification. For this reason, in this paper we propose a new model for early detection of fake news conditioned to the early stages of propagation. The model called Early Rumor Detection Model (ERDM), composed of a Bi-GRU network with a global attention module, receives at each time both features of the message propagation (text and time) and information of the users participating in the conversations. The results show that ERDM outperforms current detection methods, both for 4-class and binary scenarios, where in the last scenario an improvement of 7 % and 13.4 % is achieved in the Twitter 15 and Twitter 16 datasets, respectively. In addition, ERDM outperforms the state-of-the-art results in early detection, obtaining over 80 % in accuracy in both datasets within the first 4 hours of news dissemination.Magíster en Ciencias de la Ingeniería Informátic
Tactics selection poker, TaSPeR technique for selecting tactics of software architecture by consensus (a security approach)
No full textConstruir software seguro requiere tomar decisiones de diseño que permitan cumlir los requerimientos de seguirdad deseados; estas decisiones deben realizarse detenidamente antes de ser establecidas, lo anterior debido a que un mal diseño podría impactar gravemente el resultado final de un sistema, afectando los objetivos esperados.
Respecto al punto anterior, son los arquitectos quienes suelen tomar estas resoluciones, basándose tanto en sus experiencias como en el uso de diferentes técnicas de arquitectura, como por ejemplo el uso de tácticas de arquitectura de software; por otro lado, los desarrolladores también ejecutan acciones claves al desarrollar el software, sin embargo es posible que estos no consideren de forma sistemática y primordial la importancia de un diseño seguro desde el punto de vista de las decisiones de diseño.
El trabajo realizado en esta tesis presenta la Técnica TaSPER (Security Tactics Selection Poker), técnica consensuada basada en Planning Poker, la cual permite que todas las peronas involucradas en un desarrollo de software puedan identificar, argumentar, discutir y seleccionar las tácticas de seguridad para el desarrollo de arquitectura de acuerdo a los objetivos, requerimientos y prioridades establecidas.
Para lograr esto, primero se realizó un estudio de caso a un grupo de nueve profesionales de la Armada de Chile, para luego desarrollar un estudio experimental el cual consideró cinco etapas: definición, planificación, evaluación, ejecución y análisis. Para ello, se realizaron dos pre-experimentos con estudiantes de pregrado y postgrado en diferentes universidades y finalmente, se ejecutó un experimento con veinte profesionales del Programa del Magíster en TI con el objeto de evualuar la efectividad de la técnica en varios escenarios.
Los resultados muestran que la técnica TaSPeR apoya la toma de decisiones arquitectónicas colaborativas, formenta la participación de los diferentes involucrados y genera una dinámica grupal sobre cómo actuar contra las amenazas. Al mismo tiempo, se pudo determinar que la técnica propuesta permite decisiones más cercanas a Ground Truth (establecido por expertos) en comparación con decisiones individuales tomadas por los participantes.
Por tanto, el uso de una técnica consensuada para la evualuación de arquitecturas parece ser un enfoque prometedor para establecer de forma grupal la seguridad en el desarrollo de software.Magíster en Ciencias de la Ingeniería Informátic
Clasificación de textos multi-etiquetados con representación dependiente de la etiqueta
No full textLa asignación de una o más categorías, predefinidas a los textos en lenguaje natural, basados en su contenido, es un componente importante y necesario en muchas tareas al interior de las organizaciones. Esta tarea se realiza comúnmente a través de la clasificación automática de textos, esto es, clasificando documentos dentro de un conjunto de categorías predefinidas por medio de un modelo y métodos computacionales. La representación de los textos para propósitos de clasificación automática ha sido tradicionalmente llevada a cabo usando un modelo de espacio vectorial debido a su simplicidad y buen rendimiento. Por otro lado, la clasificación automática de textos por multi-etiquetados ha sido típicamente abordada utilizando métodos de clasificación de etiqueta simple, lo que implica transformar el problema estudiado para aplicar técnicas binarias o adaptar algoritmos binarios para que funcionen con múltiples etiquetas. En esta investigación el objetivo es evaluar una función para la ponderación de las palabras de los textos para modificar la representación de los textos en clasificación multi-etiqueta, usando una combinación de dos enfoques: transformación de problema y adaptación de modelo. Esta función de ponderación y la combinación de enfoques en la clasificación automática fue puesto a prueba con diez diferentes conjuntos de datos textuales utilizados en la literatura especializada y comparado con técnicas alternativas por medio de tres medidas de evaluación. Los resultados presentan mejoras superiores al 10% en el rendimiento de los clasificadores, atribuidas a nuestra propuesta, en todos los casos analizados.Doctorado en Ingeniería Informátic
Un framework para la creación de instancias del problema de rutas de tránsito urbano
No full textLos sistemas de transporte son componentes críticos para las ciudades, impactando inmensamente la calidad de vida de sus ciudadanos, proveyendo alternativas de transporte, reduciendo drásticamente el tráfico vehicular y la contaminación atmosférica. Se requiere de una cuidadosa planificación para evitar usuarios descontentos y un sistema insostenible, siendo fundamental el correcto diseño de la red de rutas de buses. En consecuencia, el Urban Transit Routing Problem (UTRP) se enfoca en encontrar un conjunto de rutas de buses que minimiza el tiempo de viaje de los pasajeros y los costos al operador del sistema. Varios algoritmos han sido desarrollados para resolver el UTRP, pero la mayoría de las instancias del problema carecen de datos de demanda de la vida real, con las instancias más conocidas siendo muy pequeñas para los estándares actuales y/o generadas aleatoriamente. Las técnicas de relajación del estado del arte se basan en características inherentes de los sistemas de transporte urbano y no pueden reducir de manera significativa el orden de magnitud de instancias complejas. En este trabajo, se propone un framework para generar instancias de UTRP usando datos de demanda zonal de la vida real, que incluyen miles de ubicaciones de paraderos. Los algoritmos de clustering permiten al framework reducir la complejidad del problema generando una aproximación que mantiene el comportamiento de la demanda y la estructura de caminos manteniendo conectadas y representadas tanto ubicaciones centrales como periféricas. El framework se aplica al complejo sistema de transporte público de la ciudad de Santiago de Chile. Se generan instancias con un comportamiento similar de demanda al usar una cantidad suficiente de clústeres. Además, los diversos algoritmos de clustering probados muestran una alta similitud en su salida y rendimiento. Este framework es fácilmente aplicable a diferentes realidades y debería ayudar a futuros investigadores en el diseño de algoritmos de resolución, así como mejorar los modelos de aproximación de otras ciudades.Transportation systems are critical components of urban cities, by hugely impacting the quality of life of their citizens, providing alternative means of transportation and drastically reducing street traffic and atmospheric pollution. Careful planning is required to avoid disgruntled users and an unsustainable system, where the correct design of the bus routes network is a fundamental task. Thus, Urban Transit Routing Problem (UTRP) aims to find a set of bus routes that minimises users travelling time and system operator costs. Several algorithms have been developed to solve the UTRP, but most problem instances lack real-life demand data information, where well-known benchmark instances are very small w.r.t. current standards and/or they have been randomly generated. State-of-the-art relaxation techniques are based on inherent features of urban transport systems and they cannot significantly reduce the order of magnitude of complex instances. In this work, we propose a framework to generate UTRP instances using real-life zone-based demand data, including thousand of bus stops locations. Clustering algorithms allow the framework to reduce the problem complexity by generating an approximation that preserves demand behaviour and road structure by keeping central and periphery locations represented and connected. Our study case is the complex public transport system of Santiago, Chile. We generate instances that have similar demand behaviour when using enough amount of clusters. Also, the use of several cluster algorithms shows similar performance and output. This framework is easily applicable to different realities and it should help future researchers to test network design algorithms as well as to improve the approximation models of other cities.Magíster en Ciencias de la Ingeniería Informátic