Optimización de la topología de una red wifi mediante un proceso Heurístico

Equation Chapter 1 Section 1 Proyecto Fin de Grado Ingeniería de Tecnologías Industriales Especialidad de Organización y Producción Optimización de la topología de una red wifi mediante un proceso Heurístico Autor: Borja Pérez de Guzmán Bermúdez-Coronel Tutor: Pedro L. González Rodríguez Dep. Organización Industrial I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2016 Índice de Tablas 2 Trabajo Fin de Grado Organización Industrial y Gestión de empresas I. Optimización de la topología de una red wifi mediante un proceso Heurístico Autor: Borja Pérez de Guzmán Bermúdez-Coronel Tutor: Pedro L. González Rodríguez Profesor titular Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2016 Índice de Tablas 4 Proyecto Fin de Grado: Optimización de la topología de una red wifi mediante un proceso Heurístico Autor: Borja Pérez de Guzmán Bermúdez-Coronel Tutor: Pedro L. González Rodríguez El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: Sevilla, 2016 El Secretario del Tribunal Índice de Tablas 6 A mis padres. Índice de Tablas 8 Agradecimientos Tras una larga carrera, finalmente se ve la luz al fondo de este primer pasillo, recuerdo todos esos momentos de angustias y alegrías. Todo esto no habría sido posible sin la ayuda de todos aquellos que me han apoyado, por ello quiero agradecer: A mi padre Javier por su afable carácter y su incondicional apoyo por la causa, por su cariño su afecto y su incontable conocimiento. A mi madre Silvia, por todas esos tapers para aprovechar el día de biblioteca, por sus consejos en otras cosas menos técnicas pero igual de importantes y porque siempre está ahí para ayudar. A mis hermanos, porque siempre han sabido animarme y ayudarme a desconectar, porque siempre se han preocupado y me han apoyado. A el Colegio Tabladilla que me ha formado para llegar hasta aquí. A mi tutor Pedro Luis que me ha ayudado cuando no veía la forma de hacer las cosas, por su apoyo y sus ánimos para finalizar este proyecto. Borja Pérez de Guzmán Bermúdez-Coronel Índice de Figuras 16 Figura 6-5. Fichero asignación terminales sin conectar. 47 Figura 6-6. Fichero cuenta cuantos lleva. 48 Figura 6-7. Fichero buscador sin colocar. 48 Figura 6-8. Fichero terminales sin conexión. 49 Figura 6-9. Fichero routers más conectables. 49 Figura 6-10. Fichero routers definitivos. 50 Figura 6-11. Fichero nuevo grafo routers. 50 Figura 6-12. Fichero ejecución buena. 51 Figura 6-13. Fichero busca sin árbol. 51 Figura 6-14. Fichero busca camino más corto. 52 Figura 6-15. Árbol de expansión mínima y grafo asociado de conexiones. 52 Figura 6-16. Fichero selecciona concentradores. 53 Figura 6-17. Fichero concentrador elegido. 53 Figura 6-18. Fichero calcula con arcos. 54 Figura 6-19. Fichero reasignación de terminales. 54 Figura 6-20. Fichero reasignación por niveles. 55 Figura 6-21. Fichero camino salida cercana. 55 1 JUSTIFICACIÓN Y OBJETIVOS 1.1 Justificación ctualmente vivimos en un mundo cada vez más conectado, donde las cosas más sencillas se van añadiendo a una red global. El desarrollo de la tecnología conlleva nuevas formas de trabajo y al mismo tiempo desaparecen otras. Estas nuevas formas de funcionar, intentan hacer la vida más cómoda a las personas. La globalización y la comunicación son dos adjetivos del mundo en el que vivimos actualmente. Esto conlleva la aparición de nuevas normativas cada vez más restrictivas que hay que cumplir. A partir de 2017, una ley de carácter europeo entrará en vigor exigiendo la información de los consumos de distintos servicios como son la luz, el gas o el agua corriente queden telematizados con una disposición de información sobre los consumos instantáneos. El objetivo de la telematización de los servicios (luz, gas, agua) es la cohesión de todos ellos en una sola red. En está única red se obtendrá la información de los consumos de todos los servicios, quedando incluidos el alumbrado, semáforos, parkings, etc. Esta unificación conllevaría la aparición de un único centro de control donde estarían disponibles los informes de cada uno de los servicios, facilitando así su análisis. La distribución y transporte de energía eléctrica y agua, recursos cada vez más escasos y costosos, necesita de redes de gestión donde se pueda conocer a tiempo real todos los parámetros que influyen en el funcionamiento de estas redes, con el objeto de hacerlas cada día más eficaces y fiables. Además, la tendencia de las redes de distribución de transporte de energía y agua es que estás se integren con otras redes (alumbrado, semáforos, parkings…etc.) con el objeto de que todos los servicios en una ciudad estén telegestionados desde un único centro de control. Originalmente, la obtención de los diversos consumos era leída de forma analógica y con el paso del tiempo se ha ido renovando por nuevos terminales digitales. La lectura tanto de los manuales como de los digitales se viene haciendo de forma manual por un operario al que se le asigna una determinada ruta, donde miden en los distintos puntos de lectura instalados en cada edificio con un sistema de Walk-By hacia los distintos TPL (Terminal de Punto de Lectura) de cada edificio. Se han planteado por tanto, una serie de mejoras para las distintas compañías de agua en los sistemas de telelectura que son: 1. Ahorro en la obtención de datos por la sustitución del sistema Walk-By por un sistema completamente automatizado y remoto, donde toda la información esté disponible en las oficinas centrales, pudiendo así ser integrado en sus propios sistemas de gestión. 2. Conocimiento continuo y real de las lecturas. 3. Posibilidad de una mejor gestión de los recursos mediante una predicción de la demanda basada en los datos obtenidos de los consumos lo que a su vez permitirá la monitorización de la red. 4. Un sistema más eficaz en la detección de fugas gracias a la disposición de los tiempos reales de consumo. 5. La detección de posibles fraudes. A "Si quieres cambiar al mundo, cámbiate a ti mismo.”. - Mohandas Gandhi - Justificación y objetivos 18 6. La aplicación de diferentes políticas de ahorro de agua. 7. Las grandes ciudades evolucionan hacia lo que se conoce como Smart City, donde cada vez más los servicios como el alumbrado público, las redes de semáforos o el tráfico es dirigido como un conjunto para una mejora global de los servicios. En el presente Trabajo Fin de Grado (TFG) se estudiará cómo conseguir una primera solución al problema de la localización de routers de una red de comunicación inalámbrica de contadores de agua. Está solución se servirá como punto de partida de posteriores metodologías de resolución. 1.2 Objetivos 1.2.1 Objetivo General El objetivo principal de este Proyecto es aportar una primera solución admisible cercana al óptimo mediante un proceso constructivo de la solución. Esta solución serviría posteriormente como punto de arranque de otras heurísticas para acabar de optimizar el problema de la localización de los routers. 1.2.2 Objetivos Específicos (O.E) y estructura del documento A continuación describimos brevemente los objetivos específicos que se van a alcanzar en el estudio y resolución del problema. 1.2.3 O.E.1: Comprensión detallada del problema En el problema que se estudia en el presente Proyecto se detectan tres elementos: terminales, concentradores y routers. En cada localidad, hay una serie de terminales con unas localizaciones conocidas a priori (en los edificios), estos terminales enviarán los consumos mediante señales hacia los routers. La localización de estos routers no está definida pero sí se conocen las posibilidades de su localización (esquinas de las calles). A estos routers se les asigna los terminales anteriormente nombrados. En último lugar quedan los concentradores, que tienen unas posibles localizaciones y habrá que decidir dónde ubicarlos y crear las rutas desde los routers hasta ellos. En el siguiente capítulo (Descripción del problema, 2) se hará una descripción más detallada de los elementos anteriormente descritos, así como de sus especificaciones y limitaciones. 1.2.4 O.E.2: Realizar una revisión o estado del Arte En el tercer capítulo realizaremos un análisis bibliográfico de los trabajos que se han desarrollado hasta el momento y trataremos de buscar similitudes con nuestro problema para tener material en el que apoyarnos. Clasificaremos nuestro problema en función de las características que este tenga, es decir, en función de cómo sea la solución, del tipo de función objetivo, según el número de Hubs, según la capacidad, etc. Finalmente en este apartado haremos una revisión de los algoritmos para la creación del árbol de expansión mínima y veremos algunos de ellos. 1.2.5 O.E.3: Modelo matemático y Grafo asociado Este Proyecto propone un nuevo enfoque a un Proyecto que ya se expuso (Sevilla, 2014. Localización Óptima de Routers de una Red de Comunicación Inalámbrica de Contadores de Agua.), cuyo autor Salvador Caro Jiménez desarrolló el modelo matemático del problema Localización Óptima de Routers de una Red de Comunicación Inalámbrica de Contadores de Agua. Con el estudio de dicho modelo tendremos una mayor perspectiva del problema con el objetivo de facilitar la comprensión del método constructivo propuesto. En este apartado se verá a partir de un ejemplo como las soluciones óptimas a estos problemas tienen estructura de árbol, en concreto al Árbol de Expansión Mínima. La heurística desarrollada se aplicará en grafos con los rangos usuales de terminales por calles, lo que significa que el número de terminales por calle oscilará entre 10 y 20. Se verá el RPD (relative percent difference) entre la solución constructiva y la óptima que obtuvo Salvador Caro. 1.2.6 O.E. 4: Desarrollo de un proceso heurístico En este apartado se desarrollará paso a paso el proceso de construcción y se mostrarán los pasos a partir de un ejemplo. Para la explicación de la heurística se mostrará un ejemplo y se ejecutará sobre el la heurística desarrollada. Por otro lado, se explicará detalladamente cada parte del proceso constructivo y se justificará como se ha decidido construir de esta manera la solución. Se mostrarán los resultados del ejemplo y se verán las distintas representaciones graficas del ejemplo así como los cambios. 1.2.7 O.E. 5: Discutir las implicaciones prácticas de los resultados obtenidos Durante este capítulo se analizarán los resultados obtenidos y los posibles nuevos algoritmos para aplicar a estas soluciones de partida. Así mismo, se verán las ventajas y las limitaciones que se han tenido durante el desarrollo del trabajo. En último lugar se explicará cómo hacer una ejecución en Matlab de lo que se ha desarrollado en el TFG con uno de los ejemplos de la batería aportada por el tutor. 1.3 Estructura del documento La estructura que se va a seguir a lo largo del documento aquí presente tendrá la siguiente forma: El presente documento estará formado por siete capítulos donde se desarrollará cada uno de los apartados. Además se incluyen dos anexos en los que se muestran un ejemplo en cada uno de los dos tamaños de problema a los que se ha aplicado el algoritmo. En primer lugar haremos una descripción del problema en el apartado 2. En este apartado veremos los distintos tipos de redes Wireless, sus tipos y sus distintos tipos de arquitecturas. Una vez hecho esto pasaríamos a ver la estructura de nuestra red, sus elementos y las características de ellos. En segundo lugar en el apartado 3 haremos una revisión del estado del arte de los problemas de localización de routers. En este apartado veremos algunos de los problemas similares al nuestro para ver sí podemos enmarcarlos entre ellos y finalmente hablaremos de las características y restricciones específicas de nuestro problema. Finalmente haremos una revisión de los distintos tipos de árboles de expansión mínima y los algoritmos más utilizados para obtenerlos. En el cuarto apartado veremos el modelo matemático que se utiliza para la obtención de la solución óptima. En este apartado hablaremos de los tipos de nodos existentes y los arcos permitidos entre ellos. Así mismo estudiaremos las soluciones óptimas dadas por el modelo y la similitud que este tiene con el árbol de expansión Justificación y objetivos 20 mínima. En el quinto apartado estudiaremos el algoritmo que se ha desarrollado y se completará la explicación del mismo con un ejemplo. Del mismo modo en este apartado se desarrollara el pseudocódigo asociado a la heurística y se profundizará en el análisis de la heurística. En el sexto apartado veremos las soluciones que la heurística propuesta nos da. Veremos sí las soluciones son cercanas al óptimo o se alejan mucho de él. Del mismo modo, en este apartado se mostrará como ejecutar el algoritmo desarrollado en el programa informático Matlab. Además, el documento contará con un apartado para las referencias y dos anexos. En ambos anexos se muestran los datos de dos problemas que se han utilizado en la heurística. Finalmente en el sexto capítulo se estudiarán las conclusiones del proyecto. Se verá si se han cumplido los objetivos específicos y se comentarán. Así mismo se verán las posibles ampliaciones de este proyecto. 2 DESCRIPCIÓN DEL PROBLEMA n este apartado se estudiarán las restricciones tecnológicas. A su vez se explicará el tipo de redes y sus arquitecturas, conexiones disponibles, las limitaciones y los modelos de los dispositivos con sus características. 2.1 Redes de comunicación Wireless Las redes inalámbricas son sistemas de comunicación, las cuales emplean el aire como medio transmisor donde las ondas de radiofrecuencia son las que llevan la información entre los diferentes dispositivos. Estás redes, cada vez más desarrolladas y de un mayor alcance, no necesitan de cableado, diferenciándose así de las redes convencionales. Las redes inalámbricas también tienen algunas limitaciones y en general algunos problemas, como por ejemplo:  Las interferencias que se producen entre diferentes dispositivos. Estas interferencias pueden ser provocadas mediante inhibidores o simplemente por otros dispositivos, ya que envían señales a una misma frecuencia.  Otro problema es que la potencia de alcance de las diversas señales se ve afectada por los elementos físicos que han de atravesar, (arboles, farolas o muros). 2.1.1 Clasificación de las redes Wireless Las redes inalámbricas (Wireless) se agrupan según el alcance máximo de las ondas de transmisión y se clasifican principalmente en tres tipos de redes: 1. WPAN (Wireless Personal Área Network): son las redes de menor alcance. Dicho alcance ronda los diez metros. Entre ellas se encuentran los RFID (Radio Frequency IDentification) y el Bluetooth, los cuales tienen bajos consumos energéticos y sirven para comunicar distintos dispositivos. 2. WLAN (Wireless Local Área Network): estás redes se caracterizan por poseer un alcance aproximado de cien metros. El uso habitual de las redes WLAN es conectar ordenadores en un mismo espacio de trabajo o en hogares, así como para establecer conexiones entre las redes tipo WPAN. 3. WMAN (Wireless Metropolitan Area Network): Este tipo de redes son empleadas a nivel metropolitano, con el objetivo de mantener conectada una ciudad o localidad. 4. Globales: Estas redes serían el siguiente nivel de conexiones de tipo Wireless, las cuales conectan por completo Comunidades Autónomas o países. E “Mientras me quede algo por hacer, no habré hecho nada” - Julio Cesar (100-44 A.C.) - Descripción del problema 22 2.1.2 Arquitectura de las redes Wireless La arquitectura de las redes Wireless se divide en dos grupos: las redes centralizadas y distribuidas. La principal diferencia entre ambas reside en cómo se regentan las conexiones, como están distribuidas y donde está el corazón de las mismas. 2.1.3 Redes centralizadas En este tipo de redes hay un único dispositivo que dirige la red y sus accesos. En grandes espacios, con diversos accesos y envíos de información, para una mayor cohesión de los datos entrantes o salientes y una mejor relación, este tipo de red permite un ahorro de costes así como de una mayor fiabilidad de la red. Del mismo modo, estas redes permiten crear unos sistemas de seguridad más fuertes y un mayor control de los distintos puntos de acceso. Gracias a esto, el administrador de la red puede conocer la localización de los accesos mediante un sistema de triangulación. Otra característica de este tipo de red es que permitirá al administrador la creación de túneles de conexiones entre los dispositivos existentes en caso de que uno de los elementos de la red esté estropeado, evitando así el parón completo de las transmisiones en la red. Figura 2-1. Ejemplo de Red Centralizada. Como vemos en la figura 2-1, el portátil y la PDA se conectan con el router el cual es el que administra la red a la que se conectan. 2.1.4 Redes inalámbricas distribuidas Este tipo de conexiones son las que utilizan las redes WPAN y WLAN y se definen por no tener un administrador. En la red habrá distintos emisores-receptores, estos son usuarios y administradores de la red. Los distintos usuarios serán a su vez creadores de la propia red lo que significa que los dispositivos más alejados de la red pueden acceder a ella utilizando los canales creados por la red de dispositivos. Actualmente está configuración de redes de dispositivos está progresando a gran velocidad y permite un gran abanico de posibilidades gracias a su la adaptabilidad a distintos entornos (bibliotecas, aeropuertos, colegios, etc.). Al no existir un punto donde se canalice toda la información, cuando uno de los dispositivos queda desconectado, la red no se ve perjudicada al no haber dependencia entre unos usuarios y otros. Del mismo modo, todos los elementos de la red emiten a una misma frecuencia y no será necesario de ningún tipo de traductor de frecuencia. Figura 2-2. Ejemplo de Red Distribuida. Como vemos en la figura 2-2, todos los dispositivos de la red se conectan entre ellos a partir de las señales que envía cada uno. 2.2 Arquitectura del problema objeto de estudio Con el conocimiento de los tipos de red y con el entendimiento del problema llegamos a la conclusión de que nuestra red será WPAN con distancias máximas de 500 metros en función de los obstáculos según el estándar IEEE 802.15.4 de. Mediante esta red creada entre los distintos dispositivos el flujo de información entre los router se hará de tal forma que la información se reenvíe desde los routers más alejados de los puntos de la red y se vaya repitiendo utilizando los routers existentes hacia la salida en el concentrador. Un correcto conocimiento de la estructura de la red nos permitirá buscar una forma correcta de crear una forma constructiva para crear la solución, como se mueven los flujos, cuales son los puntos frecuentes, cuales son necesarios y los más probables. Hace unos años, los contadores de agua eran de tipo analógico pero se han ido actualizando a hacia modelos digitales más modernos, sin embargo, la recolección de los datos se seguía haciendo de forma manual mediante la programación de rutas de operarios con un sistema llamado Walk-By. Los operarios utilizaban los TPL (Terminal de Punto de Lectura) para la obtención de los datos de los terminales. En el nuevo sistema los distintos terminales de lectura enviarán los datos obtenidos del contador o contadores hacia el router al que esté asignado, estos routers tienen un límite máximo de conexiones. Los routers se conectarán directamente con la Sede Central donde se encuentra el Concentrador, o bien se conectarán con otro router de la ruta que tiene asignada hasta llegar finalmente al Concentrador. La ubicación de los Routers será una variable con posibilidades discretas, en concreto se podrán poner los routers en las esquinas de cada una de las calles. Descripción del problema 24 Al igual que los routers, los concentradores tienen sus limitaciones en el número de conexiones posibles, debido a esto, por la cuidad habrá distintas sedes locales, en las que la información obtenida en ellos será enviada por fibra óptica hacia la sede central de la compañía suministradora. La localización de los concentradores será en aquellos lugares predefinidos donde haya conexión con la red de fibra óptica de la ciudad. En este proyecto pues se va a buscar de forma constructiva una primera solución de partida que sirva para futuras heurísticas a aplicar en este tipo de problemas. Se va a tratar de poner un mínimo número de Routers y de Concentradores cumpliendo con las limitaciones técnicas de los mismos. Con todo esto, siempre tratando que el coste sea el mínimo. 2.3 Elementos y sus características A continuación se expondrán los elementos que conforman el problema y se explicarán detalladamente sus características: Terminal de Lectura El terminal de lectura es aquel que cada edificio tiene asignado y que recoge los datos de cada uno de los contadores que tiene. Dicho terminal estará asignado a un router determinado al que le enviará la información. Los contadores estarán en distintos puntos en los edificios, típicamente se hayan en las fachadas de ellos aunque también podrán estar en los sótanos o en el interior. Dependiendo de donde se sitúen tendrán un mayor o menor alcance debido a los impedimentos físicos (paredes, arboles, etc.). Figura 2-3. Ejemplo de TPL. Router El router es aquel al que le llegan los datos de los distintos terminales de cada edificio así como los datos de los otros routers de la red. El router podrá ir conectado a otro router creando el camino de una ruta o bien conectado directamente al concentrador que es el destino final de la red. El router es el elemento del que sabemos sus posibles localizaciones y que tenemos que minimizar su cantidad. Cada una de las esquinas de una ciudad es un punto susceptible de poseer uno de los routers lo cual da un número muy grande para calcular los puntos de forma manual. La máxima distancia que puede haber entre dos routers para que la conexión entre ellos sea buena es sobre unos 500 metros cuando no hay entre ellos obstáculos. Los routers tienen que tener visión directa debido a restricciones de la tecnología y frecuencia de transmisión elegida, por lo que las ubicaciones donde interfiera cualquier arboleda u otro elemento de tipo arquitectónico, entre Terminal- Router, Router-Router o Router- Concentrador, no será una ubicación candidata. Otra limitación de los Routers es la cantidad de terminales de los que puede transmitir los datos. El límite está situado en 20 terminales por router. En estos 20 terminales se incluyen tanto los que vienen directamente transmitidos por los TPL hacia el router, como los que han sido recibidos por otro router. Es decir, sí un terminal tiene asociados 15 TPL directamente y un router conecta con él y le envía una señal con los datos de más de 5 terminales, en ese nodo habría que poner otro router. El coste cada uno de los Routers será de 98 €, el cual incluye los costes del propio router, el estudio de las posibles ubicaciones y la instalación del mismo. Figura 2-4. Ejemplo de router. Concentrador Los concentradores son los puntos de salida de la red. El concentrador recibe las señales emitidas por los distintos routers y la envía por la red de fibra óptica hacia la sede central. Los concentradores tienen limitados el número de conexiones con routers en 20 y el máximo flujo de información sobre terminales es de 500. El concentrador no está localizado a priori pero sí que se conocen las posibles ubicaciones, las cuales son lugares donde hay acceso a la red de fibra óptica. La distancia máxima que puede haber entre concentrador que recibe la información de un router es de 500 metros sin obstáculos. El coste por cada uno de los concentradores es de 350 euros, donde se incluyen el coste del propio concentrador y los costes de montaje y diseño de la red. Figura 2-5. Ejemplo de concentrador de red. Estado del Arte 16 16 no dirigido cuyas aristas tienen unos pesos asignados. El algoritmo selecciona las aristas con un menor peso, ya que este es el objetivo de la función. En caso de que el grafo fuera no conexo, el algoritmo buscaría un árbol para cada uno de los componentes del grafo. El Algoritmo de Prim, también llamado Algoritmo DJP o Algoritmo de Jarnik, fue diseñado por Prim (1957). También fue diseñado por Jarnik (1930) y Dijkstra (1959) de forma independiente. El algoritmo comienza eligiendo la arista de menor peso, lo cual añadiría dos nodos que ya estarían conectados. Una vez hecho esto, el algoritmo va buscando en cada iteración añadir las aristas de menor peso que vayan conectando con los nodos restantes. El algoritmo antes de seleccionar una arista, comprueba que esta no está ya conectada al árbol que ha ido formando ya que en caso de que esto ocurriera estaríamos formando un ciclo. 3.3.2.1 Pseudocódigo Algoritmo de Prim Fase 1: Elegimos el arco con un menor peso; Fase 2: Evaluación del arco con menor peso Fase 2.1: Sí el arco elegido no conecta con nodos que ya están activos Fase 2.1.1: Añadimos el arco al árbol; Marcamos los nodos como conectados; Fase 2.2: Sí el arco elegido conecta dos nodos que ya están activos Fase 2.2.1: Se cancela el arco; Fase 2.3: Comprobar si todos los nodos están conectados Fase 2.3.1: Sí todos los nodos están conectados Fase 2.3.1: Fin Fase 2.3.2: Sí quedan nodos por conectar volvemos a la fase 2. 3.3.2.2 Ejemplo Algoritmo de Prim En el siguiente ejemplo veremos cómo funciona el Algoritmo de Prim. Para estudiar el problema vamos a utilizar el mismo ejemplo que para el caso de Kruskal. El ejemplo se ha montado con el programa Grafos cuya distribución es gratuita. Dicho programa pertenece a Alejandro Rodríguez Villalobos. Figura 3-5. Ejemplo utilizado para la solución de Prim. * 0 ---- (169,71) ---> 8 * 1 ---- (160) ---> 2 * 1 ---- (144,22) ---> 7 * 2 ---- (144,22) ---> 3 * 3 ---- (169,71) ---> 4 * 4 ---- (160) ---> 5 * 5 ---- (160) ---> 6 * 6 ---- (200) ---> 8 Coste total = 1307,86. La representación de la solución dada por el Algoritmo de Prim sería: Estado del Arte 18 18 Figura 3-6. Solución utilizando el algoritmo de Prim. Como observamos, el coste total obtenido ha sido el mismo pero el orden en el que se obtienen los arcos ha sido diferente en ambas ocasiones. 3.3.3 Diferencias Como vemos, la principal diferencia es el propio algoritmo. En el Algoritmo de Prim partimos de un primer nodo y vamos añadiendo nodos cuyo coste sea el menor. Es decir, si partimos del nodo 0, tenemos tres posibilidades, hacia 1, 6 y 8 cuyos arcos que los conectan pesan 240, 243.31 y 169.71 respectivamente. Por ello el Algoritmo de Prim decide elegir el arco que lo une con 8 que es el de menor peso. Ahora tendríamos los nodos 1 y 8 para seguir conectando el árbol y evaluaríamos los arcos de igual manera que antes. Sin embargo, en el Algoritmo de Kruskal lo primero que se hace es ordenar todas las aristas de menor a mayor peso. Este algoritmo va eligiendo la de menor coste y evaluando con dos condiciones, nunca se puede repetir un nodo y no se pueden generar bucles. Por otro lado, cada uno de los algoritmos no siempre da una misma solución, es decir, ambas llegan a la solución óptima pero puede ser que las soluciones sean distintas, esto puede ser por la existencia de arcos con un mismo peso en localizaciones distintas u otras razones. Lo cual significa que puede haber más de una solución óptima 2 . El Algoritmo de Kruskal no necesita que todos los nodos hayan quedado conectados ya que sí esto pasa se dedica a crear un bosque en cambio el Algoritmo de Prim sí que necesita para poder ejecutarse que exista alguna ruta entre todos los nodos. Respecto a la complejidad, la diferencia principal es que Prim añade nodos sabiendo que llegamos a ellos con menor coste y Kruskal ordena las aristas para obtener el menor coste. Teniendo ello presente obtenemos que: Complejidad de Prim: O (n²) Complejidad de Kruskal: O(a log a) (siendo a el número de arcos). La función que utilizaremos para obtener el arco contempla ambas opciones y elige la mejor de ellas en función 2 Ver también http://www.ing.ula.ve/~aguilar/actividad-docente/AYDA/Clase4MiniSem.pdf del problema. Grafo asociado y Modelo Matemático 20 20 4 GRAFO ASOCIADO Y MODELO MATEMÁTICO “Cada hora de tiempo perdido en la juventud es una posibilidad más de desgracia en la adultez.” Claude Shannon, 1948 n el modelo matemático habrá que definir las distintas localizaciones de los terminales, los routers y los concentradores así como las restricciones. Las diversas localizaciones formarán un grafo no dirigido que será el objeto de estudio. Cada uno de los terminales tendrá asignada una unidad de flujo que viene dada por el nodo origen O. Los nodos intermedios son los nodos routers, los cuales se conectan entre sí o con los nodos concentradores. Finalmente, los nodos concentradores se conectan con el nodo final E, el cual tendrá que tener el mismo número de unidades de flujo que salieron en O. 4.1 Tipos de Nodos 1. Nodo O: comienzo del grafo, de O salen tantas unidades de flujo como terminales hay en el grafo. Hay un nodo O por grafo. 2. Nodos Ti: Son los terminales de cada edificio de la localidad y habrá que asignarlo a alguno de los posibles routers. El número total de terminales será NT. 3. Nodos Pi: Son las Posibles localizaciones de los routers. Tendrán asignados terminales y/o routers e irán a otro router o concentrador. Las posibles localizaciones de los routers serán Np. 4. Nodos Ci: Son las posibles localizaciones de los concentradores, reciben los datos de los routers y reenvían al nodo E la información. El total de las localizaciones de los Concentradores serán NC. 5. Nodo E: Final del Grafo. Todas las unidades de flujo que entraron por el nodo O han de ser las mismas que le lleguen ahora a E. Solo hay un nodo E por grafo. 4.2 Tipos de conexiones o arcos Una vez definidos los tipos de Nodos, se desarrollan los tipos de conexiones entre los distintos nodos, los cuales son: 1. Nodo Origen (O): Origen del nodo que tiene una dirección única del nodo O hacia cada uno de los terminales Ti. el nodo O le asigna una unidad de flujo a cada uno de los Ti del grafo. 2. Nodos Terminales (Ti): cada uno de los terminales del grafo llegará a uno o más posibles nodos routers. Cada Ti lleva asignada una unidad de flujo que enviará a uno de los arcos posibles que tiene hacia los routers. Los terminales solo pueden enviar la información hacia alguno de los routers que le llegan. 3. Nodos Routers (Pi): tienen dos conexiones permitidas. Como entrada pueden tener distintos terminales y routers. Como salidas pueden conectarse con otros routers o bien conectar con alguno de los concentradores. 4. Nodos Concentradores: a los concentradores les llegan uno o varios routers de los posibles como entradas y como salidas siempre conectan con el nodo E. E 5. Nodo E: El nodo E es el nodo de salida y solo tiene como entradas los distintos concentradores posibles del grafo. Tabla 4-1. Conexiones entre Nodos. Origen Destino Nodo O Terminal Terminal Router Router Router Concentrador Concentrador Nodo E Figura 4-1. Arcos y nodos. Terminales Routers Concentradores Grafo asociado y Modelo Matemático 22 22 En concreto, la distribución de la red quedaría: Donde vemos como el terminal de un edificio envía la señal al router que tiene asignado y este router va reenviando la señal hacia otro router y así sucesivamente hasta el punto de salida en el concentrador. 4.3 Parámetros y variables 4.3.1 Parámetros A continuación se describen los parámetros de los distintos dispositivos así como los costes unitarios de cada uno de ellos: Conexiones máximas de un Router nTR: 20. Límite de terminales que recoge un concentrador nTC: 500. Límite de routers que admite un concentrador, nRC: 24. Precio por cada router, CR: 98. Coste de cada concentrador, CC: 350. 4.3.2 Variables La variable njr es una variable entera la cual es la suma de todos los routers que se han colocado en el grafo de entre todas las posibilidades. La variable nkc es una variable entera la cual es la suma de todos los concentradores que se han colocado de entre todas las posibilidades. La variable yij es la variable que me dice que flujo asociado tiene cada uno de los nodos del grafo en el arco (i,j). 4.4 Función Objetivo y Restricciones El propósito de este Proyecto es el de minimizar el coste por lo que la función objetivo del modelo lineal será una función de miniar los costes: El coste vendrá dado por el precio de cada uno de los Routers (CR), multiplicado por el número de routers que se han puesto en el grafo. A esto habrá que sumarle el coste asociado al número de concentradores que será la suma de concentradores que finalmente se han colocado por el precio de cada uno de los concentradores (CC). El modelo estará sometido a las siguientes restricciones: Restricción 1(R1): Inyección del flujo. Desde el nodo origen O se inyecta una unidad de flujo a cada uno de los terminales que conforman el nodo. R2: Balance de Flujo. El número de unidades de flujo que entra en un nodo ha de ser igual al que sale. R3: Sumidero de Flujo. Todo el flujo que sale de los nodos asociados a posiciones candidatas de los concentradores llega al nodo final (e), siendo su suma el número de elementos que está contenido en el conjunto. R4: Contador de Routers. El número de routers en cada uno de los nodos se puede saber a partir del flujo de entrada o de salida de los mismos, redondeándolo al entero superior obteniendo los routers necesarios. R5: Contador de Concentradores. El número de concentradores se puede saber a partir del flujo de entrada o de salida de los mismos, redondeando al entero superior, obteniendo así el número de concentradores necesarios. Grafo asociado y Modelo Matemático 24 24 4.5 Modelo Completo Seguidamente se expondrá el modelo completo, con la Función Objetivo (F.O.) y sus Restricciones. F.O. Sujeto a (s.a.): R1 R2 R3 R4 R5 En resumen, la función objetivo calcula el coste de cada una de las soluciones posibles. La R1 le asigna una unidad de flujo a cada uno de los terminales. La R2 obliga a que el flujo que entra por en un router sea la misma que sale. La restricción 3 obliga a que el todo el flujo que llega a los concentradores sea el mismo que el flujo que se ha inyectado a los terminales. La R4 calcula el número de routers de cada una de las iteraciones. La R5 calcula el número de concentradores en cada una de las iteraciones. 4.6 Análisis y topología de las soluciones Analizando las soluciones de la batería de problemas llegamos a la conclusión de que poseen una gran similitud con el Árbol de Expansión Mínima (Minimum Spanning Tree (MST)). Las soluciones no son directamente un MST sin embargo quitando algunos de los arcos activos en la solución óptima la solución se vuelve un MST. Para la explicación de la heurística desarrollada se ha utilizado el problema 20-200-1 de una batería de problemas aportada por el tutor (ver González, 2015). Para la representación de la solución se ha utilizado el programa Grafos – 1.3.5 de Alejandro Rodríguez Villalobos. Figura 4-2. Grafo de la solución óptima. La anterior figura con los arcos podados quedaría: Figura 4-3. Grafo de la solución en forma de árbol. Proceso Constructivo 32 32 Fase 5: Cálculo de la Función Objetivo; A continuación se desarrollan las anteriores ideas de manera extendida. 5.2 Fase 0: Preprocesado y Ordenación de datos En primer lugar se procede a una ordenación de los datos de las conexiones: En primer lugar las conexiones Terminal-Router, las cuales siempre tienen una unidad de flujo asignadas. Estarán guardadas en un vector origen con un índice negativo y su correspondiente destino solo podrán ser routers con un destino positivo. Así mismo tendrán asignado una distancia entre el terminal y los routers a los que llega. En segundo lugar tenemos las conexiones con origen en un Router y destino un Router. En el vector origen tendremos un número determinado, que será el número de router que tiene asignado y este será positivo y mayor que cero. En el destino de este router estará otro número de otro router al que llega que también será positivo y mayor que cero. Entre dichos routers habrá una distancia determinada. En tercer lugar tenemos las conexiones desde los Routers hacia los concentradores. En el origen tendremos un valor positivo entero, uno de los routers, y en el destino tendremos un número negativo, que es el que cada concentrador tendrá asociado. Tabla 5-1. Codificación de los datos. Origen Destino Dirección Terminal (-) Router(+) (-) → (+) Router (+) Router(+) (+) → (+) Router (+) Concentrador(-) (+) → (-) El resto de las combinaciones no estarían permitidas. Los datos se ordenan en Excel, abriendo los .txt y ordenándolos según el origen según este en un Router primero y después los Terminales, teniendo así una constante llamada cambio que guarda donde en los vectores origen, destino y distancia cambian de origen en terminal y origen en router. Teniendo los vectores así ordenados nos ahorramos tener que ir buscando las conexiones y sabiendo donde están de antemano. 5.3 Fase 1: Asignación de Terminales 5.3.1 Fase 1.1 y 1.2: Terminales asignados a un único Router y Determinación de los Routers obligatoriamente activos Debido a las restricciones del problema, algunas de las esquinas obligarán siempre ha que determinados routers estén siempre activos. Esto se produce porque algunos terminales solo llegan a un único router lo cual nos permite de antemano que esquinas van a estar activas con un 100% de seguridad. Gracias a la ordenación de los datos, empezamos en el vector origen desde el elemento cambio, donde estaría el primero de los terminales (-1) y comprobamos si el siguiente es igual que él o no. En caso de que el siguiente inmediato no fuera y el anterior tampoco, significa que dicho terminal solo tiene alcance a un único router y quedaría automáticamente asignado para el resto del problema. Tabla 5-2. Asignaciones obligadas Origen Destino Distancia -45 10 110.8 -45 20 98.8 -46 9 1 -47 10 79.32 -47 9 58.68 Como vemos en el ejemplo, el terminal 46 tiene como único arco permitido el 9 por lo que queda asignado a ese router para el resto del problema. 5.3.2 Fase 1.3: Asignar Terminales a Routers Activos Tras este primer paso ya tendremos una serie de esquinas activas a las cuales les asignaremos todos los terminales que tengan de un arco disponible hacia ellas. Es decir, tenemos unas esquinas activas con algún terminal que lo ha activado de forma obligatoria, y ahora en este paso los terminales que no están asignados puede que lleguen a alguno de los obligatorios y por ello se los asignamos. Recorremos el vector origen por los terminales y vemos cuál de ellos tiene como destino alguno de los routers que ya están asignados. Tabla 5-3. Terminales con conexión a alguno de los routers obligatorios Origen Destino Distancia -48 23 200.4 -48 9 100.4 -48 20 25.6 Como vemos, el terminal 48 tiene un arco posible con el router número 9, por ello se asigna ese terminal a dicho router. Procediendo de esta manera vamos asignando todos los terminales posibles a los distintos routers obligatorios y vamos reduciendo el número de terminales sin asignación. Proceso Constructivo 34 34 5.3.3 Fase 1.4: Asignar Terminales al Resto de Routers Una vez tenemos asignados todos los terminales posibles a los routers que eran obligatorios, vamos a asignar aquellos que han quedado sin conectarse. Para ello, vamos a evaluar cuál de las posibles esquinas tiene más posibilidades de ser elegida, es decir, cuál de las posibles ubicaciones de los distintos routers tiene más arcos de entrada entre los terminales que no han quedado asignados. Para esto definimos un vector en el cual cada componente me dirá cuántos de los terminales que no están asignados podría asignar a un determinado router. Eligiendo el máximo de los elementos de este vector estaremos activando dicho router y asignándole todos los terminales que le llegan. Este proceso es iterativo, es decir, cada vez que asignamos uno de los routers tenemos que actualizar el vector cuantos le llegan a cada router e ir seleccionando en cada iteración al router que más terminales le pueda asignar. Figura 5-1. Asignación terminales al resto de routers. Esta forma de proceder nos deja los siguientes routers activos. En la siguiente tabla un 1 indicará que el nodo está activo y un cero al contrario: Tabla 5-4. Routers Activos e Inactivos. Nodo 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 1/0 1 0 0 1 0 1 0 1 1 0 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 1 1 1 Como vemos, esto nos dice que con 18 esquinas activas somos capaces de asignar todos los flujos de cada uno de los terminales a algún router, sin embargo, no nos dice que todos hayan quedado conectados entre sí. 5.4 Fase 2: Conexionado de Routers 5.4.1 Fase 2.1 Construir Grafo no dirigido Con estos pasos, ya tenemos todos los terminales asignados a alguno de los routers. A partir de los routers activos montamos un grafo de conexiones entre los routers. En la matriz habrá filas y columnas de ceros, donde una fila o columna de ceros significará que el router de esa fila no ha sido activado. Con esta matriz y la función de Matlab biograph dibujamos el grafo no dirigido de nodos que nos ha quedado con los nodos activos. View (biograph (UG, [],'ShowArrows','off','ShowWeights','on')) La ejecución de esta función nos dará un grafo donde veremos todas las conexiones posibles. Figura 5-2. Grafo de conexiones Inicial. Donde los nodos que están sin conexiones son aquellos que no tienen conexiones, o bien aquellos que si tienen asignados algunos de los terminales pero no tienen conexiones entre los routers que hay disponibles. Proceso Constructivo 36 36 5.4.2 Fase 2.2 Construir Bosque A este primer grafo obtenido le calculamos el árbol de expansión mínima para hacer que todo quede conectado y obtener una primera ruta del problema. Esto no tiene porqué ocurrir y entonces se forman bosques. Los cuales son pequeños arboles desconectados entre sí. Esto lo hacemos con una función de Matlab graphisspantree (ST). Esta función necesita como entrada una matriz dispersa de conexiones y nos devolverá el árbol de expansión mínima en el cual no estarán conectados aquellos que no están activos, o bien, aquellos activos que no tienen conexión posible entre los activos. La función graphisspantree (ST) nos dará un vector con las direcciones de las conexiones y en los no conectados nos dará un error (Not a Number (NaN)). Sabiendo cuales son las esquinas activas y comparando con los que han salido NaN, cuando un nodo activo tenga asignado un NaN significará que el nodo activo ha quedado desconectado del árbol y que hay que conectarlo. Figura 5-3. Arbol de Expansión mínima inicial. Como podemos apreciar, los nodos 6 y 24 se incluían entre los nodos activos y vemos que no han quedado conectados en el árbol. Por ello y para que todo quede conectado buscamos un camino para conectarlos. 5.4.2.1 Fase 2.2.1 Conexionado del Bosque Los nodos que han quedado sin conexión hay que conectarlos con el árbol que tenemos, para ello calculamos el camino más corto desde el nodo a conectar hacia todos los nodos activos pasando por los inactivos. Es decir, construimos la matriz de conexiones de los routers entera y buscamos el camino más corto, que será el que necesite un menor número de saltos (routers extra) hacia uno de los nodos activos. Siguiendo este modo de proceder, obtenemos que el nodo 6 puede conectarse al árbol si añadimos como router activo el nodo 7 necesitando únicamente un router extra. Del mismo modo, el nodo 24 queda unido a la red añadiendo como router extra el 25. Quedando finalmente un total de 20 esquinas activas y un grafo donde todos los nodos activos están conectados con al menos un arco. La función que calcula el camino más corto es: [Dist, path, pred] = graphshortestpath (B, k, i) Donde B será una matriz dispersa que incluya todas las conexiones Router-Router. Dist: la distancia que hay entre los nodos k e i. Path: es el más importante, pues nos dirá el número de saltos necesarios (routers extra) para hacer la conexión entre el árbol y los nodos desconectados. Pred: nos dirá la dirección de los saltos. 5.4.2.2 Fase 2.2.2 Construir nuevo grafo de conexiones Sabiendo ya por tanto que todos los nodos van a estar conectados, montamos el grafo de conexiones entre los routers que están activos. Ahora el número de conexiones ha cambiado así como el número de arcos posibles, por lo que el grafo será distinto y tendrá más posibilidades. Figura 5-4. Grafo de Conexiones Final. Como podemos observar, el nodo 6 solo tiene como conexión disponible el 7, al igual que ocurre con el 25 pero ha quedado todo conectado. 5.4.3 Fase 2.3: Construir Árbol de Expansión Mínima Con el grafo calculado en el anterior apartado, creamos su árbol de expansión mínima que utilizaremos como una primera solución. Como han cambiado las conexiones en el grafo, el árbol de expansión mínima habrá cambiado a su vez. Proceso Constructivo 38 38 Figura 5-5. Árbol de Expansión mínima final. Como se observa, el grafo ha cambiado y además el orden de sus conexiones. Una vez tenemos todo conectado, pasamos a decidir los concentradores que van a quedar activos. 5.5 Fase 3: Conexión con concentradores Una vez tenemos el árbol conectado, hay que estudiar cuál de los concentradores sería mejor. Para esto, vemos cuál de los concentradores posibles tiene un mayor número de conexiones. Con ello presente, vemos cual tiene más arcos posibles con los nodos activos. El concentrador con más conexiones a los arcos activos producirá un mayor número de salidas en los arcos. Así mismo, todos aquellos nodos que tengan un arco hacia el concentrador elegido no necesitarán de una ruta por la que ir repitiendo la información, por lo que en principio estaríamos ahorrando routers en el reenvío de señales. Siguiendo con este procedimiento, evaluamos todos lo concentradores y nos queda que la cantidad de arcos activos en cada concentrador es de: Tabla 5-5. Selección de Concentradores. Concentrador 1 2 3 4 5 6 7 8 Cantidad que llegan 3 3 6 3 4 2 3 3 Como se observa, en el concentrador 3 tenemos 6 arcos activos, esto quiere decir que en nuestro grafo tenemos 6 puntos de salida del mismo y que en ellos no habrá que crear ningún tipo de ruta sino que directamente se enlazarán con el concentrador. De los 20 nodos activos, solo tendremos que crear 14 rutas para cada uno de ellos tratando de llenar siempre los que están más cercanos a la salida, ya que estos tendrán que ir repitiendo la señal un número de veces menor que cuando están más alejados de esta, dándonos siempre una solución mejor o igual a la que ya tenemos. Tras la elección del primer concentrador buscamos la adición de más concentradores. Los siguientes concentradores más valorados serán aquellos que creen nuevos arcos con nodos que no conectan directamente con el concentrador anterior. Es decir, sí el concentrador elegido me ha producido tener en nuestro grafo seis puntos de salida, el siguiente mejor concentrador a elegir será aquel que ponga produzca un mayor incremento en el número de salidas. Una vez tenemos el concentrador que más salidas nos da, para meter otro concentrador usaríamos el anterior elegido y buscaríamos cuál de los otros concentradores nos incrementa más el número de nodos activos como salidas y así sucesivamente. 5.6 Fase 4: Obtención del Grafo dirigido y mejoras El uso de la función en la creación del árbol de expansión mínima nos ha dado una primera ruta a seguir. Como ya tenemos los terminales asignados a los distintos nodos, lo que hacemos es partir de los extremos del árbol, nodos hoja, y vamos utilizando los arcos dados por la función desde estos hacia las distintas salidas. Lo cual nos da ya una primera solución, sin embargo, esta es fácilmente mejorable, ya que esta solución solo utiliza un número de arcos ya dados cuando en realidad hay un mayor número de posibilidades que pueden mejorar nuestra solución. Como vemos en el ejemplo que vamos estudiando, en el árbol de expansión mínima el nodo el camino a seguir por el nodo 17 sería de tres saltos hasta la salida uno. Figura 5-6. Ruta dada por el Árbol de Expansión Mínima. Es decir, la ruta puesta como una serie de saltos sería: Sin embargo, en el grafo completo hay una alternativa que dará una solución que siempre será mejor o igual: Nodo 17 Nodo 4 Nodo 7 Nodo 1 Salida Proceso Constructivo 40 40 Figura 5-7. Posibles Rutas Alternativas. Es decir, del nodo 17 vamos al cuatro y del cuatro al uno. Con esta manera de proceder no tenemos que repetir la señal desde siete hasta uno, lo cual significa que sí los terminales asignados a 6, 7, 4 y 17 suman más de 20, en 7 tendríamos que poner dos routers y sin embargo al hacer directamente el salto desde 4 hacia uno puede que nos estemos ahorrando un Router. 5.6.1 Mejora 1: Reasignación por niveles Llegados a este punto, vemos que cuanto más cerca está un nodo de la salida menos saltos va a necesitar, por ello se hace una reasignación de los terminales, donde van a estar priorizados por niveles. El nivel cero lo tendrán los nodos salida, ya que estos no tienen que seguir ningún tipo de ruta y por tanto vamos a tratar de asignar todos los terminales posibles a las distintas salidas. El siguiente nivel sería para aquellos que necesitan de un salto para llegar a la salida y así sucesivamente. De esta manera, no vamos a ser capaces de reducir en ningún número el número de nodos activos, sin embargo sí que podemos disminuir el número de routers necesarios, ya que la repetición de señales puede hacer que en uno de los nodos sea necesario más de un router y al ejecutar de esta manera disminuimos la cantidad de routers. Figura 5-8. Niveles de los nodos. 5.6.2 Mejora 2: Ruta a la salida más cercana Una vez reasignados los terminales, y viendo las mejoras posibles en saltarnos nodos hasta llegar a la salida, buscamos la ruta más corta hacia la salida, esta vez con todos los arcos de los nodos activos. Esto lo hacemos buscando el camino más corto entre los nodos y la salida con la función graphshortestpath (B, k, i) que nos dará el camino más corto. De esta manera estaremos evaluando sí el nodo ha quedado asignado a una salida a la que tiene que llegar dando un número de saltos que se podría reducir. Figura 5-9. Camino a la salida más cercana. 5.7 Fase 5: Cálculo de la Función Objetivo Una vez tenemos la solución con las mejoras pasamos a calcular el valor de la función objetivo. Para calcular el valor de la función objetivo multiplicamos el número de routers que hemos calculado como necesario y lo multiplicamos por el coste de cada uno de los routers. A ese valor le sumamos el número de concentradores por el número de concentradores. 𝐶𝑜𝑠𝑡𝑒= 𝑁º𝑅𝑜𝑢𝑡𝑒𝑟𝑠 ∗ 98(€ 𝑅𝑜𝑢𝑡𝑒𝑟)+𝑁º𝐶𝑜𝑛𝑐𝑒𝑛𝑡𝑟𝑎𝑑𝑜𝑟𝑒𝑠∗350(€ 𝐶𝑜𝑛𝑐𝑒𝑛𝑡𝑟𝑎𝑑𝑜𝑟) Lo que nos daría el valor de la función objetivo en euros. Y finalmente en el ejemplo que hemos venido desarrollando, el coste total sería de 3290€. Experimentación y análisis de los Resultados 48 48 Obtenemos la cantidad de terminales que han quedado asignados. Figura 6-6. Fichero cuenta cuantos lleva. Ahora abrimos el archivo BuscadorSinColocar.m y nos aparece una ventana como la figura 6-7 que se dedicará a buscar cual de los terminales no ha quedado asignado. Una vez abierto le damos a Run. Figura 6-7. Fichero buscador sin colocar. Ahora abrimos TerminalesSinConexion.m y nos aparece una ventana como la figura 6-8 y le damos a Run. Esto creará una matriz con los terminales no colocados. Figura 6-8. Fichero terminales sin conexión. Ahora abrimos el archivo RoutersMasConectables.m y nos aparece una ventana como la figura 6-9 que evaluará cada uno de los routers no colocados y nos dará cuantos terminales llegan a cada uno de los routers. Una vez abierto el archivo le damos a Run. Figura 6-9. Fichero routers más conectables. Tras esto, abrimos el archivo RouterDefinitivos.m y nos aparece una ventana como la figura 6-10 y cuando esté Experimentación y análisis de los Resultados 50 50 abierto le damos a Run. Aquí se eligen el resto de routers necesarios para tener todos los terminales asignados. Figura 6-10. Fichero routers definitivos. Tras esto pasamos a abrir NuevoGrafoRouters.m y nos aparece una ventana como la figura 6-11 donde se creará la matriz con las conexiones entre los routers que han quedado activos. Una vez abierto le damos a Run. Figura 6-11. Fichero nuevo grafo routers. Ahora tenemos la matriz de conexiones y abrimos el archovo EjecucionBuena.m y le damos a Run. Esto generará un dibujo del grafo y del árbol de expansión mínima. Figura 6-12. Fichero ejecución buena. Ahora buscamos cuales de los nodos no han quedado conectados con el arbol. Para esto abrimos BuscaSinArbol.m y nos aparece una ventana como la figura 6-13 y le damos a Run. Figura 6-13. Fichero busca sin árbol. Ahora ya tenemos los nodos que han quedado desconectados y buscamos la forma de unirlo con el resto del arbol. Para esto abrimos BuscaCaminoMasCorto y nos aparece una ventana como la figura 6-14 y le damos a Experimentación y análisis de los Resultados 52 52 Run. Figura 6-14. Fichero busca camino más corto. Ahora tenemos que crear una matriz donde todos los nodos están conectados entre sí. Ahora volvemos a ejecutar la funcion NuevoGrafoRouters y nos dará la nueva matriz de conexiones. Este paso es igual que la otra ejecución de NuevoGrafoRouters.m. Ahora ejecutamos otra vez EjecucionBuena.m y nos dará el grafo definitivo de conexiones y el árbol de expansión mínima definitivo. Figura 6-15. Árbol de expansión mínima y grafo asociado de conexiones. Ahora abrimos la funcion SeleccionaConcentradores.m y nos aparece una ventana como la figura 6-16 que me dirá cuales de los concentradores son mejores. Una vez abierto, le damos a Run. Figura 6-16. Fichero selecciona concentradores. Ahora abrimos ConcentradorElegido.m y nos aparece una ventana como la figura 6-17 y le damos a run, donde utilizando la evaluación de la anterior funcion selecciona concentrador. Figura 6-17. Fichero concentrador elegido. Ahora abrimos CalculaConArcos.m y nos aparece una ventana como la figura 6-18. Una vez abierto el archivo Experimentación y análisis de los Resultados 54 54 le damos a Run. Figura 6-18. Fichero calcula con arcos. Ahora abrimos ReasignacionDeTerminales.m y nos aparece una ventana como la figura 6-19 donde comenzaremos a reasignar los terminales en otro orden. Una vez abierto el archivo le damos a Run. Figura 6-19. Fichero reasignación de terminales. Ahora abrimos ReasignacionPorNiveles.m y nos aparece una ventana como la figura 6-20 y le damos a Run. Con está función hemos reasignado los terminales en función de la distancia al concentrador. Una vez abierto el script le damos a Run. Figura 6-20. Fichero reasignación por niveles. Y finalmente abrimos CaminoSalidaCercana.m y nos aparece una ventana como la figura 6-21 y le damos a Run. Esto nos dará la solución definitiva del algoritmo. Figura 6-21. Fichero camino salida cercana. Conclusiones 56 56 7 CONCLUSIONES ara concluir este TFG se van a comentar las conclusiones que hemos obtenido después de realizar el análisis de los resultados del anterior capítulo. El problema objeto de estudio aborda la localización de routers en un sistema de recogida de datos para una red de abastecimiento de aguas. Como se ha argumentado en la revisión de la literatura dicho problema es considerado NP duro, por lo que los modelos matemáticos tienen una aplicación limitada. Debido a esto, surgen maneras alternativas para resolver este tipo de problemas. En ocasiones puede ser interesante renunciar a la optimalidad del problema a favor de obtener soluciones admisibles rápidamente con una calidad adecuada. En el segundo capítulo hemos estudiado el problema y sus condiciones. Aquí hemos analizado los distintos tipos de redes y cómo se comportan para poder caracterizar nuestro problema a las redes existentes y entender cómo funcionan los distintos tipos, particularmente hemos detallado nuestro problema, sus condiciones y como son cada uno de los elementos que lo forman. De esta manera, hemos cumplido el primer objetivo específico, comprensión detallada del problema. En el tercer capítulo hemos revisado varios trabajos ya desarrollados por otros autores en el problema de la localización de routers. Así mismo, hemos caracterizado nuestro problema y lo hemos enmarcado entre ellos. En este capítulo también se ha hecho una revisión de los algoritmos más utilizados en la creación de Árboles de Expansión Mínima, ya que la técnica constructiva propuesta se basa en la generación de un árbol de expansión mínima y hemos analizado sus diferencias. Con esta forma de proceder hemos cumplido el objetivo específico número dos, Realizar una revisión o estado del Arte. En el cuarto capítulo hemos estudiado el grafo asociado al problema, los tipos de nodos del problema y los diferentes tipos de arcos que hay entre ellos. Además en este capítulo hemos estudiado el modelo matemático del problema y hemos visto la topología de las soluciones óptimas de donde hemos obtenido la conclusión de que las soluciones tienen una gran similitud con el Árbol de Expansión Mínima. Por ello concluimos que el objetivo específico número tres, Modelo matemático y Grafo asociado, ha sido cumplido. En el quinto capítulo hemos desarrollado el proceso Heurístico constructivo y hemos ido detallando en cada uno de los pasos del proceso. Así mismo en este capítulo se ha explicado la heurística utilizando un ejemplo y viendo los distintos resultados. Debido a esto obtenemos la conclusión de que el objetivo específico número cuatro, Proceso Constructivo, ha sido correctamente cumplido. En el sexto capítulo hemos aplicado la heurística a una pequeña batería de problemas y hemos obtenido los resultados correspondientes. Así mismo, hemos analizado los resultados y hemos visto que las soluciones son siempre admisibles y muy buenas para problemas pequeños y para problemas más grandes la solución sigue siendo admisible y aunque siguen siendo buenas nunca llegan al valor de la solución óptima. Por ello, obtenemos la conclusión de que el objetivo específico número cinco, Discutir las implicaciones prácticas de los resultados obtenidos, ha sido cumplido. Podemos entonces afirmar que hemos logrado alcanzar el objetivo general de este TFG ya que hemos podido cumplir todos los objetivos específicos que nos habíamos puesto. A pesar de que los resultados obtenidos con la heurística nunca llegan a ser igual de buenos que las soluciones obtenidas por el modelo MILP, la heurística aquí propuesta obtendrá siempre una solución inicial de partida admisible en un tiempo de ejecución es mínimo. Analizando los resultados, vemos que para problemas con un número menor de terminales las soluciones obtenidas por la heurística son mejores que aquellos casos en los que hay una mayor cantidad de terminales. Hemos de comentar que en este TFG se ha utilizado la heurística propuesta para un modelo donde no hay routers GPRS (donde se permitiría la conexión directa de cada nodo router al nodo final) y una ampliación de esta heurística sería contemplar el caso de que sí existiera y ver cómo se comporta. Una futura ampliación de este proyecto sería el utilizar esta heurística como punto de arranque para nuevas P heurísticas para seguir mejorando la solución. Una de las opciones sería aplicar el algoritmo ALNS (Algorithm Large Neighborhood Search , ver por ejemplo Pisinger y Ropke, 2009). Otra posible ampliación de este TFG sería el aplicar el método desarrollado a problemas reales y a otros problemas similares de abastecimiento de otros servicios y ver cómo se comporta. Otra opción sería ampliar el número de problemas, con mayor diversidad de tamaños, a los que se le ha desarrollado la heurística y desarrollar la heurística en alguno de los lenguajes compilados. Anexo I. Batería 20-200 64 64 Origen Destino Distancia Origen Destino Distancia -150 19 139.369998932 -164 2 179.720001221 -150 2 56.6300010681 -165 8 61.0399932861 -150 16 88.6300010681 -165 9 1.96000671387 -151 16 192.380004883 -166 22 122.059999943 -151 2 160.380004883 -166 8 124.940000057 -151 19 35.6199951172 -167 9 24.0700073242 -152 3 32.6600036621 -167 8 38.9299926758 -153 3 94.3899993896 -168 22 23.8799972534 -153 13 117.61000061 -169 22 209.809997559 -154 16 107.460006714 -169 9 100.190002441 -154 2 139.460006714 -169 8 37.1900024414 -154 13 194.539993286 -170 22 12.0400009155 -154 3 17.4600067139 -171 9 43.1000061035 -155 3 91.7600002289 -171 8 19.8999938965 -155 16 1.76000022888 -172 8 72.5999984741 -155 2 30.2399997711 -173 8 232.279998779 -156 3 129.820007324 -173 22 14.7200012207 -156 13 82.1799926758 -174 22 63.2099990845 -157 16 66.9800033569 -175 22 125.360000014 -157 3 23.0199966431 -175 8 121.639999986 -157 2 98.9800033569 -176 22 1.80999755859 -158 3 61.25 -177 12 31.8800048828 -158 16 151.25 -177 11 180.119995117 -158 2 183.25 -178 12 50.6000061035 -158 13 150.75 -179 11 10.8300018311 -159 16 15.8600006104 -179 12 201.169998169 -159 2 47.8600006104 -180 11 2.81999969482 -159 3 74.1399993896 -181 11 90.4900054932 -159 19 243.86000061 -182 15 4.93000030518 -160 16 9.22999954224 -182 14 85.0699996948 -160 2 22.7700004578 -183 15 13.0299987793 -160 3 99.2299995422 -183 14 76.9700012207 -161 16 132.339996338 -184 15 83.5899963379 -161 2 100.339996338 -184 14 6.41000366211 -161 19 95.6600036621 -185 17 171.899993896 -162 13 77.0700073242 -185 18 24.1000061035 -162 16 224.929992676 -186 17 112.080001831 -162 3 134.929992676 -186 18 83.9199981689 -163 3 47.3300018311 -187 18 5.74000549316 -163 16 42.6699981689 -187 17 190.259994507 -163 2 74.6699981689 -188 18 18.8000030518 -164 13 154.279998779 -188 17 177.199996948 -164 3 57.7200012207 -189 17 140.779998779 -164 16 147.720001221 -189 18 55.2200012207 Origen Destino Distancia -190 18 44.1100006104 -191 18 9.4700012207 -192 28 41.0599975586 -192 20 34.9400024414 -193 21 61.0 -193 25 28.0 -194 21 194.959999084 -194 25 105.959999084 -194 28 23.9599990845 -194 20 52.0400009155 -195 28 36.2299995422 -195 21 134.770000458 -195 25 45.7700004578 -195 20 112.229999542 -196 20 108.590000153 -196 21 138.409999847 -196 25 49.4099998474 -196 28 32.5900001526 -197 21 89.4799995422 -197 28 81.5200004578 -197 25 0.479999542236 -198 20 132.239999771 -198 25 25.7600002289 -198 28 56.2399997711 -198 21 114.760000229 -199 26 10.2600021362 -199 27 65.7399978638 -200 27 41.4300003052 -200 26 34.5699996948 El resto de elementos de la batería tienen una similar estructura pero entre ellos varían la disponibilidad de arcos entre nodos. Anexo II. Batería 20-400 66 66 ANEXO II. BATERÍA 20-400 A continuación se muestran los datos de la batería de problemas en forma de tabla proporcionada por el tutor (González-R, 2015). En esta tabla se contemplan los problemas con una densidad de 20 terminales por calle. Donde cada columna de la tabla significa que: Origen: es el comienzo del arco, cuando este valor sea positivo es un arco que comienza en un router. En caso contrario el origen será en un terminal. Destino: Es el final del arco, cuando este valor es positivo, es un arco entre routers y cuando sea negativo es un arco hacia concentrador. Distancia: es la longitud del arco. Los datos para el 20-400-1 son: Origen Destino Distancia Origen Destino Distancia 1 -3 122 4 -2 183 1 -1 0 4 -1 122 1 2 183 4 1 122 1 4 122 4 3 183 1 7 186 4 5 291 1 17 285 4 7 64 2 -5 32 4 8 472 2 -2 122 4 11 59 2 -1 183 4 14 333 2 1 183 5 -4 350 2 3 122 5 -3 291 2 13 334 5 -2 474 2 16 32 5 3 474 2 17 102 5 4 291 2 19 196 5 6 64 3 -5 90 5 8 181 3 -4 124 5 10 63 3 -3 183 5 11 350 3 -2 0 5 20 458 3 2 122 5 26 281 3 4 183 6 5 64 3 5 474 6 7 291 3 11 124 6 10 1 3 13 212 7 -3 64 3 14 150 7 -1 186 3 16 90 7 1 186 3 19 318 7 4 64 4 -4 59 7 6 291 Origen Destino Distancia Origen Destino Distancia 8 4 472 16 15 150 8 5 181 16 19 228 8 9 63 17 -1 285 8 20 277 17 1 285 8 22 247 17 2 102 8 26 100 17 18 196 9 8 63 18 17 196 9 10 181 18 19 102 9 22 310 19 -5 228 10 5 63 19 -2 318 10 6 1 19 2 196 10 9 181 19 3 318 11 -4 0 19 16 228 11 -3 59 19 18 102 11 -2 124 20 5 458 11 3 124 20 8 277 11 4 59 20 21 247 11 5 350 20 25 158 11 12 212 20 26 177 11 14 274 20 28 76 12 -4 212 21 20 247 12 11 212 21 22 277 12 13 124 21 23 207 13 -5 302 21 25 89 13 -2 212 21 28 171 13 2 334 22 8 247 13 3 212 22 9 310 13 12 124 22 21 277 13 16 302 22 23 484 14 -4 274 23 21 207 14 -3 333 23 22 484 14 -2 150 23 24 89 14 3 150 24 23 89 14 4 333 24 25 207 14 11 274 25 20 158 14 15 90 25 21 89 15 -5 150 25 24 207 15 14 90 25 28 82 15 16 150 26 5 281 16 -5 0 26 8 100 16 -2 90 26 20 177 16 2 32 26 27 76 16 3 90 27 26 76 16 13 302 27 28 177 Anexo II. Batería 20-400 68 68 Origen Destino Distancia Origen Destino Distancia 28 20 76 -18 17 130.6799927 28 21 171 -19 1 67.26000214 28 25 82 -19 2 115.7399979 28 27 177 -19 17 217.7399979 -1 2 39.08999634 -20 1 76.54000092 -1 17 62.91000366 -20 2 106.4599991 -2 2 92.92001343 -20 17 208.4599991 -2 17 9.079986572 -21 1 109.6500015 -3 1 137.8699951 -21 2 73.34999847 -3 2 45.13000488 -21 17 175.3499985 -3 17 147.1300049 -22 2 15.88999939 -4 1 83.36000061 -22 17 86.11000061 -4 2 99.63999939 -23 2 47.27000427 -4 17 201.6399994 -23 17 54.72999573 -5 1 98.30999756 -24 1 82.86000061 -5 2 84.69000244 -24 2 100.1399994 -6 2 75.16000366 -24 17 202.1399994 -6 17 26.83999634 -25 2 12.32000732 -7 2 27.16000366 -26 3 147.3099976 -7 17 74.83999634 -26 14 2.690002441 -8 2 52.11000061 -27 3 58.33999634 -9 1 126.5100021 -27 4 241.3399963 -9 2 56.48999786 -27 11 182.3399963 -10 2 50.22000122 -27 14 91.66000366 -11 1 118.2200012 -28 5 79.55999756 -11 2 64.77999878 -28 8 101.4400024 -11 17 166.7799988 -29 5 151.9200134 -12 1 72.66999817 -29 8 29.07998657 -12 2 110.3300018 -29 26 129.0799866 -13 2 35.08000183 -30 8 81.21002197 -13 17 66.91999817 -30 26 18.78997803 -14 1 201.9499969 -31 4 213.7700043 -14 2 18.94999695 -31 5 77.22999573 -14 17 83.05000305 -32 8 104.9000244 -15 1 94.83999634 -32 20 172.0999756 -15 2 88.16000366 -32 26 4.900024414 -15 17 190.1600037 -33 8 175.7399902 -16 1 247.8500061 -33 20 101.2600098 -16 2 64.8500061 -33 26 75.73999023 -16 17 37.1499939 -34 4 10.61999989 -17 1 151.3800049 -34 11 48.38000011 -17 2 31.61999512 -35 5 54.82000732 -17 17 133.6199951 -35 8 126.1799927 -18 2 28.67999268 -36 3 126.0799866 Origen Destino Distancia Origen Destino Distancia -36 14 23.92001343 -53 20 85.4699707 -37 5 52.51998901 -53 26 91.5300293 -38 3 46.72000122 -54 5 21.45001221 -38 4 229.7200012 -55 5 163.1900024 -38 11 170.7200012 -55 8 17.80999756 -38 14 103.2799988 -55 26 117.8099976 -39 3 34.1499939 -56 8 10.75 -39 4 217.1499939 -56 26 89.25 -39 11 158.1499939 -57 3 7.949996948 -39 14 115.8500061 -58 8 93.94000244 -40 8 114.7199707 -58 26 6.059997559 -40 20 162.2800293 -59 8 103.1400146 -40 26 14.7199707 -59 26 3.140014648 -41 4 240.3200073 -60 5 89.27999878 -41 5 50.67999268 -60 8 91.72000122 -41 8 231.6799927 -61 8 69.92999268 -42 8 133.9899902 -61 26 30.07000732 -42 20 143.0100098 -62 4 14.52999973 -42 26 33.98999023 -62 11 73.52999973 -43 5 25.94000244 -63 4 66.55000305 -44 20 20.65997314 -63 11 7.550003052 -45 3 149.2200012 -64 3 10.94999695 -45 4 33.77999878 -64 4 172.0500031 -45 11 25.22000122 -64 11 113.0500031 -46 3 143.5299988 -64 14 160.9499969 -46 4 39.47000122 -65 5 35.20999146 -46 11 19.52999878 -65 8 145.7900085 -47 5 203.1600037 -66 5 159.2900085 -47 8 22.16000366 -66 8 21.70999146 -47 26 77.83999634 -66 26 121.7099915 -48 3 73.16000366 -67 5 30.20001221 -48 14 76.83999634 -68 8 145.8200073 -49 4 231.2599945 -68 20 131.1799927 -49 5 59.74000549 -68 26 45.82000732 -49 8 240.7400055 -69 3 54.94000244 -50 8 236.0100098 -69 11 69.05999756 -50 20 40.98999023 -70 5 128.2799988 -50 26 136.0100098 -70 8 52.72000122 -51 3 125.5499992 -71 5 6.559997559 -51 4 57.45000076 -71 8 187.5599976 -51 11 1.549999237 -72 5 77.05999756 -52 8 35.29000854 -73 3 72.19999695 -52 26 64.70999146 -73 4 110.8000031 -53 8 191.5300293 -73 11 51.80000305 Anexo II. Batería 20-400 70 70 Origen Destino Distancia Origen Destino Distancia -74 26 59.55999756 -94 26 44.78997803 -75 5 242.2399902 -95 8 111.6699829 -75 8 61.23999023 -95 20 165.3300171 -75 20 215.7600098 -95 26 11.66998291 -75 26 38.76000977 -96 3 69.33000183 -76 8 63.60998535 -96 11 54.66999817 -77 4 6.050000191 -97 5 39.13999939 -77 11 65.05000019 -98 4 178.2400055 -78 20 33.79998779 -98 5 112.7599945 -78 26 143.2000122 -98 11 237.2400055 -79 20 53.34002686 -99 3 13.63999939 -79 26 123.6599731 -99 4 196.6399994 -80 3 69.77999878 -99 11 137.6399994 -80 11 193.7799988 -99 14 136.3600006 -80 14 80.22000122 -100 5 73.01998901 -81 3 33.55999756 -101 5 117.9299927 -81 11 90.44000244 -101 8 63.07000732 -82 5 7.239990234 -102 8 195.6900024 -83 8 72.23999023 -102 20 81.30999756 -84 4 22.5 -102 26 95.69000244 -84 11 81.5 -103 5 27.17999268 -85 4 90.76999664 -104 8 29.75 -85 11 149.7699966 -104 26 70.25 -86 5 64.60998535 -105 4 2.210000038 -86 8 116.3900146 -105 11 56.78999996 -86 26 216.3900146 -106 8 159.2000122 -87 3 36.71000671 -106 20 117.7999878 -87 4 219.7100067 -106 26 59.20001221 -87 11 160.7100067 -107 5 220.1000061 -87 14 113.2899933 -107 8 39.1000061 -88 8 8.769989014 -107 20 237.8999939 -88 26 91.23001099 -107 26 60.8999939 -89 3 96.16000366 -108 3 110.5500031 -89 11 220.1600037 -108 4 72.44999695 -89 14 53.83999634 -108 11 13.44999695 -90 5 99.74000549 -109 3 88.5 -91 3 86.33999634 -109 14 61.5 -91 14 63.66000366 -110 14 29.82000732 -92 8 50.59997559 -111 4 173.2700043 -92 26 49.40002441 -111 5 117.7299957 -93 3 81.51000214 -111 11 232.2700043 -93 11 42.48999786 -112 5 142.5100098 -94 8 144.789978 -112 8 38.48999023 -94 20 132.210022 -112 26 138.4899902 Origen Destino Distancia Origen Destino Distancia -113 5 20.14001465 -137 8 138.8099976 -114 20 10.36999512 -137 20 138.1900024 -115 4 39.61999893 -137 26 38.80999756 -115 11 19.38000107 -138 7 77.30999756 -116 8 93.69000244 -139 7 17.12999916 -116 26 6.309997559 -140 6 135.1499939 -117 5 0.75 -141 6 1.440002441 -118 8 110.5100098 -142 6 217.5899963 -118 26 10.51000977 -142 7 73.41000366 -119 3 135.1300011 -143 7 40.09999847 -119 4 47.86999893 -144 6 0.619995117 -119 11 11.13000107 -145 7 56.52000046 -120 5 89.3999939 -146 6 115.1300049 -120 8 91.6000061 -146 7 175.8699951 -121 3 127.9599915 -147 7 35.29999924 -121 14 22.04000854 -148 7 44.74000168 -122 8 113.7000122 -149 7 36.68000031 -122 26 13.70001221 -150 6 6.350006104 -123 5 93.92001343 -151 6 97.32000732 -123 8 87.07998657 -151 7 193.6799927 -124 4 205.1600037 -152 6 99.07000732 -124 5 85.83999634 -152 7 191.9299927 -125 4 99.76999664 -153 7 8.710000038 -126 20 68.96002197 -154 6 166.7699966 -127 5 119.1099854 -154 7 124.2300034 -127 8 61.89001465 -155 6 241.1300011 -128 8 4.079986572 -155 7 49.86999893 -128 26 95.92001343 -156 6 54.47999573 -129 3 99.93000031 -157 7 121.0400009 -129 4 83.06999969 -158 7 17.88999939 -129 11 24.06999969 -159 6 34.88000488 -129 14 249.9300003 -160 6 60.3999939 -130 8 21.55999756 -161 7 65.66000366 -130 26 78.44000244 -162 6 47.00999451 -131 20 11.23999023 -163 6 202.2099991 -132 3 77.76998901 -163 7 88.79000092 -132 14 72.23001099 -164 9 33.35998535 -133 3 33.58999634 -165 9 76.82000732 -133 11 90.41000366 -166 10 55.41000366 -134 20 12.64001465 -167 9 46.32000732 -135 3 96.93000031 -167 10 134.6799927 -135 4 86.06999969 -168 10 25.67001343 -135 11 27.06999969 -169 9 42.07000732 -136 3 30.33000183 -170 9 107.7099915 Anexo II. Batería 20-400 72 72 Origen Destino Distancia Origen Destino Distancia -170 10 73.29000854 -200 21 44.78997803 -171 9 26.57998657 -201 21 14.30999756 -172 10 77.33999634 -202 23 3.429992676 -173 15 68.67999268 -203 21 46.54998779 -173 16 81.32000732 -204 23 12.17999268 -174 16 31.33999634 -205 21 144.5200195 -175 15 43.29998779 -205 22 132.4799805 -175 16 106.7000122 -206 21 62.76000977 -176 15 49.23001099 -207 21 95.67999268 -177 15 45.3999939 -208 21 45.46002197 -178 15 18.10998535 -209 22 86.26000977 -178 16 131.8900146 -210 21 76.58001709 -179 16 43.97000122 -211 22 68.51000977 -180 15 75.11999512 -212 21 125.5999756 -180 16 74.88000488 -212 23 81.40002441 -181 18 97.75 -213 21 193.2800293 -181 19 4.25 -213 23 13.7199707 -182 18 5.130004883 -214 21 4.25 -182 19 96.86999512 -214 23 211.25 -183 18 77.91999817 -215 21 25.76000977 -183 19 24.08000183 -216 21 57.59997559 -184 18 61.3500061 -216 23 149.4000244 -184 19 40.6499939 -217 21 12.15002441 -185 18 8.25 -217 23 219.1500244 -185 19 93.75 -218 21 43.33001709 -186 21 162.75 -218 22 233.6699829 -186 22 114.25 -219 21 68.19000244 -187 21 220.7700195 -219 23 138.8099976 -187 22 56.22998047 -220 21 134.5200195 -188 21 138.4500122 -220 23 72.47998047 -188 22 138.5499878 -221 22 10.32998657 -189 21 115.2999878 -222 21 98.10998535 -190 21 73.78997803 -222 22 178.8900146 -191 21 174.5999756 -223 21 9.020019531 -191 22 102.4000244 -224 22 119.9899902 -192 22 0.359985352 -225 21 33.84002686 -193 21 116.7000122 -226 21 179.0300293 -194 22 16.26998901 -226 23 27.9699707 -195 21 116.7800293 -227 21 143.6099854 -195 23 90.2199707 -227 23 63.39001465 -196 23 52.15002441 -228 21 199.8099976 -197 21 31.86999512 -228 22 77.19000244 -198 21 79.21002197 -229 22 31.98001099 -199 21 99.42999268 -230 21 137.710022 Origen Destino Distancia Origen Destino Distancia -230 23 69.28997803 -259 1 55.20999908 -231 21 124.3200073 -259 4 66.79000092 -232 23 24.59997559 -259 7 130.7900009 -233 21 95.57000732 -260 1 164.7799988 -233 23 111.4299927 -260 4 42.77999878 -234 21 11.16998291 -260 7 21.22000122 -235 22 72.30999756 -261 4 19.8500061 -236 21 181.7000122 -261 7 44.1499939 -236 23 25.29998779 -262 1 119.6600037 -237 25 69.79998779 -262 4 2.339996338 -238 24 160.0900269 -262 7 66.33999634 -238 25 46.90997314 -263 1 42.54999924 -239 24 95.16998291 -263 4 79.45000076 -240 24 58.36999512 -263 7 143.4500008 -240 25 148.6300049 -264 4 8.940002441 -241 25 44.59997559 -264 7 55.05999756 -242 24 206.2000122 -265 1 44.33000183 -242 25 0.799987793 -265 4 77.66999817 -243 25 14.47998047 -266 1 90.33999634 -244 24 17.33001709 -266 4 31.66000366 -244 25 189.6699829 -266 7 95.66000366 -245 24 194.4199829 -267 1 15.67000008 -245 25 12.58001709 -267 4 106.3299999 -246 24 95.78997803 -268 1 29.12000084 -246 25 111.210022 -268 4 92.87999916 -247 24 125.25 -269 1 150.5800018 -247 25 81.75 -269 4 28.58000183 -248 25 41.14001465 -269 7 35.41999817 -249 24 97.41998291 -270 1 118.0199966 -249 25 109.5800171 -270 4 3.980003357 -250 24 107.0300293 -270 7 67.98000336 -250 25 99.9699707 -271 1 38.52000046 -251 27 30.30999756 -271 4 83.47999954 -251 28 146.6900024 -271 7 147.4799995 -252 27 39.25 -272 3 6.650001526 -253 27 49.11999512 -272 16 83.34999847 -254 27 88.01000977 -273 2 238.5800018 -254 28 88.98999023 -273 3 116.5800018 -255 27 9.770019531 -273 13 95.41999817 -255 28 167.2299805 -273 16 206.5800018 -256 28 63.46002197 -274 2 33.70999908 -257 28 6.820007324 -274 3 88.29000092 -258 27 41.84002686 -274 16 1.709999084 -258 28 135.1599731 -275 13 31.25