Estudio experimental de diferentes modelos matemáticos para resolver el problema TSP

Trabajo Fin de Grado Grado en Ingeniería de las Tecnologías Industriales Estudio Experimental de diferentes modelos matemáticos para resolver el problema TSP Autor: Ana Corral Sánchez Tutor: José Manuel García Sánchez Dep. Organización Industrial y Gestión de Empresas I Universidad de Sevilla Sevilla, 2020 Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 2 Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 3 Proyecto Fin de Carrera Ingeniería de las Tecnologías Industriales Estudio Experimental de diferentes modelos matemáticos para resolver el problema TSP Autor: Ana Corral Sánchez Tutor: José Manuel García Sánchez Profesor titular Dpto. de Organización Industrial y Gestión de Empresas I Escuela Técnica Superior de Ingeniería Universidad de Sevilla Sevilla, 2020 Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 4 Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 5 El tribunal nombrado para juzgar el Proyecto arriba indicado, compuesto por los siguientes miembros: Presidente: Vocales: Secretario: Acuerdan otorgarle la calificación de: El Secretario del Tribunal Sevilla, 2020 Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 6 Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 7 INDICE GENERAL INDICE GENERAL ................................................................................................................. 7 ÍNDICE DE FIGURAS ............................................................................................................. 9 ................................................................................................................................................. 9 ÍNDICE DE TABLAS ............................................................................................................ 10 ............................................................................................................................................... 10 1. OBJETIVO DEL TRABAJO ........................................................................................... 11 2. INTRODUCCIÓN .......................................................................................................... 12 3. El PROBLEMA DEL VIAJANTE GENERALIZADO .................................................... 13 ........................................................................................................................................... 13 3.1. Historia del TSP ...................................................................................................... 13 3.2. Definición del TSP .................................................................................................. 14 3.3. Aplicaciones en la vida real ..................................................................................... 15 3.3.1. Logística y distribución .................................................................................... 15 3.3.2. Secuencia de Genomas ..................................................................................... 17 3.3.3. Placas de circuitos y Microchips ...................................................................... 18 3.3.4. Otras aplicaciones ............................................................................................ 19 4. MÉTODOS DE RESOLUCIÓN DEL TSP ...................................................................... 20 4.1. Métodos exactos ...................................................................................................... 20 4.2. Métodos aproximados .............................................................................................. 22 4.3. Formulación general TSP......................................................................................... 23 5. LOS MODELOS MATEMÁTICOS ................................................................................ 26 5.1. Modelo 1: Modelo MTZ .......................................................................................... 27 5.1.1. Elementos y variables ...................................................................................... 27 5.1.2. Restricciones.................................................................................................... 28 5.1.3. Función Objetivo ............................................................................................. 29 5.2. Modelo 2: Modelo DL ............................................................................................. 30 5.2.1. Elementos y Variables...................................................................................... 30 5.2.2. Restricciones.................................................................................................... 31 5.2.3. Función Objetivo ............................................................................................. 32 5.3. Modelo 3: Modelo intermedio .................................................................................. 32 5.3.1. Elementos y Variables...................................................................................... 32 5.3.2. Restricciones.................................................................................................... 33 5.3.3. Función Objetivo ............................................................................................. 34 5.4. Modelo 4: Modelo de Sarin...................................................................................... 35 Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 8 5.4.1. Elementos y Variables...................................................................................... 35 5.4.2. Restricciones.................................................................................................... 36 5.4.3. Función Objetivo ............................................................................................. 37 5.5. Comentarios sobre los modelos ................................................................................ 37 6. LOS PROBLEMAS ........................................................................................................ 39 6.1. Introducción de los problemas ................................................................................. 39 6.2. Problemas simétricos ............................................................................................... 40 6.3. Problemas asimétricos ............................................................................................. 42 7. LINGO ........................................................................................................................... 43 7.1. Introducción a Lingo................................................................................................ 43 7.2. Ampliación de Lingo ............................................................................................... 45 7.2.1. Los conjuntos ................................................................................................... 45 7.2.2. Restricciones.................................................................................................... 46 7.2.3. Interfaz con el usuario ...................................................................................... 48 7.3. Conversión de los ficheros (“.txt”) a Lingo .............................................................. 50 7.3.1. De Ficheros de Texto a Excel ........................................................................... 50 7.3.2. De Excel a Lingo ............................................................................................. 53 7.4. Los Modelos finales en Lingo .................................................................................. 54 7.4.1. Modelo MTZ ................................................................................................... 55 ....................................................................................................................................... 55 7.4.2. Modelo DL ...................................................................................................... 55 7.4.3. Modelo Intermedio........................................................................................... 56 7.4.4. Modelo de Sarin ............................................................................................... 56 8. EXPERIMENTACIÓN ................................................................................................... 57 8.1. Experimentación Problemas Asimétricos ................................................................. 59 8.2. Experimentación Problemas Simétricos ................................................................... 64 9. CONCLUSIÓN ............................................................................................................... 68 10. BIBLIOGRAFÍA ......................................................................................................... 69 Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 9 ÍNDICE DE FIGURAS Figura Nombre Página Figura 1 Rutas de Alemania, problema del TSP 14 Figura 2 Hamilton Icosian Game 15 Figura 3 Recorridos de un vendedor 17 Figura 4 Rutas escolares en la ciudad de Valencia 18 Figura 5 Mapeo de Radiación Híbrida 19 Figura 6 Ejemplo de ejercicio con la Fuerza Bruta 22 Figura 7 Ejemplo método del Vecino más próximo 23 Figura 8 Problema del TSP de ejemplo, datos 25 Figura 9 Problema del TSP de ejemplo, solución 1 25 Figura 10 Ejemplo de problema en fichero de texto 40 Figura 11 Fichero de texto con enunciado de Problema asimétrico 42 Figura 12 Ejemplo de modelo matemático 45 Figura 13 Ejemplo de modelo matemático simple en Lingo 46 Figura 14 Aplicación de las funciones en Lingo 48 Figura 15 Aplicación de los signos en Lingo 48 Figura 16 Inicio de Lingo, interfaz con el usuario 49 Figura 17 Ejecución de Lingo, interfaz con el usuario 49 Figura 18 Solución de Lingo, interfaz con el usuario 50 Figura 19 Paso 1 para la conversión de enunciados 51 Figura 20 Paso 2 para la conversión de enunciados 52 Figura 21 Paso 3 para la conversión de enunciados 53 Figura 22 Paso 4 para la conversión de enunciados 53 Figura 23 Paso 5 para la conversión de enunciados 54 Figura 24 Paso 6 para la conversión de enunciados 55 Figura 25 Modelo MTZ en Lingo 56 Figura 26 Modelo DL en Lingo 56 Figura 27 Modelo Intermedio en Lingo 57 Figura 28 Modelo de Sarin en Lingo 57 Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 16 • Vendedores: En cuanto a vendedores, el problema TSP se implementa de tal forma que el viajante es un vendedor, y quiere recorrer el máximo número de puntos distintos sin pasar por los mismos, vendiendo así el mayor número posible de su producto, y con el objetivo a su vez de ahorrar lo máximo en costes, ya sea de tiempo, como de distancia o gasolina. Para ello, antes de partir, se crean rutas óptimas en el mapa de puntos interesados para cumplir con el objetivo. Dependiendo del número de ciudades, se obtendrá una gran cantidad de rutas diferentes que tomar, decidiéndose por la que mayor beneficio le proporcione. Fig.3 Recorridos de un vendedor Fuente: Elaboración Propia Un vendedor quiere vender su producto por las ciudades marcadas de Andalucía, partiendo de la ciudad origen, que es Sevilla. Traza todos los diferentes caminos posibles a realizar, y se da cuenta que no sabe bien qué ruta hacer para poder ahorrar lo máximo en tiempo, y en distancia, lo cual le ahorraría en combustible. En este tipo de casos, en la vida real, las compañías realizan un estudio con el uso de herramientas apropiadas, para detallar qué recorrido sería el óptimo. • Envíos postales: El problema TSP juega un papel importante en los problemas postales generales, donde las casas o calles están muy alejadas unas de otras, o donde solo es necesario visitar un subconjunto de casas como en la entrega de paquetes. Por ello, en este ámbito se ha adoptado recientemente el problema TSP en softwares para el uso en las aplicaciones postales. Un ejemplo es la empresa Rapidis [4], que emplea un módulo heurístico de Concorde para trazar rutas para sus clientes de Forbruger-Kontakt, un distribuidor de material publicitario y muestras que opera en Dinamarca y otros países. Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 17 • Secuencias: Cuando hablamos de secuencia, nos referimos al orden en el cual n trabajos tienen que ser procesados de tal forma que se minimice el costo total de producción. • Rutas de transporte laborales o escolares: Muy similar a lo que sucede con el vendedor o el cartero, pero en este caso surge con la necesidad de crear la ruta óptima a la hora de recoger a trabajadores o alumnos en sus respectivas casas o paradas, para llevarlas al trabajo o colegio. Fig.4 Rutas escolares en la Ciudad de Valencia Fuente: Routing Maps, empresa de Rutas 3.3.2. Secuencia de Genomas El problema TSP también juega un papel importante en la secuencia de genomas, ya que nos proporciona una herramienta para construir las secuencias a partir de datos experimentales sobre la proximidad de pares individuales de marcadores. Cada cromosoma, situado en el mapa del genoma, tiene una secuencia de marcadores con cierta estimación de la distancia entre los marcadores adyacentes. Estos marcadores de los mapas son conocidos como segmentos de ADN, y pueden detectarse en un laboratorio de forma fiable. La capacidad de reconocer estos segmentos permite a los investigadores a utilizarlos para poder comparar y combinar mapas físicos creados en diferentes laboratorios [4]. El problema TSP entra en juego, a la hora de tener información sobre del orden en el que aparecen los marcadores en el genoma. Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 18 El mapeo de radiación híbrida (RH), desarrollada por Goss y Harris [4], es una de las técnicas principales para poder obtener datos sobre la posición relativa de los marcadores, creando los segmentos a partir de Rayos X. Fig.5 Mapeo de Radiación Híbrida Fuente: The travelling Salesman Problem, A Computational Studio [4] 3.3.3. Placas de circuitos y Microchips Esta es una de las utilidades más favorables que puede plantear el problema del viajante de comercio. La creación de placas de circuitos se enfoca en dos problemas distintos, los cuales pueden ser solucionados gracias al problema TSP. • Problemas de perforado: El fin es buscar el orden óptimo de taladrar las placas. En este caso, tomaremos las ciudades como las posiciones a perforar y las distancias entre ellas como el tiempo que necesita la máquina en trasladarse de una a otra. La ciudad origen en este caso será un punto adicional, donde permanecerá la perforadora mientras no está trabajando. • Problemas de conexión de chips: La idea principal es minimizar la cantidad de cable necesario para poder unir todos los puntos de una placa sin que haya interferencias, dando lugar así a errores. Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 19 Los chips son normalmente de tamaño bastante pequeño, es imposible poder poner más de dos cables en un único pin. Por lo tanto, en este caso, ahora tomamos las ciudades como los pins, y la cantidad de cable para unirlos como la distancia, intentando minimizarla al máximo [16]. 3.3.4. Otras aplicaciones • Inspecciones a sitios remotos: Ordenar los lugares que deberá visitar un inspector en el menor tiempo. • Aplicaciones en Internet: Supongamos que el viajante de comercio es un bit de datos, y que las ciudades son servidores de Red distribuidos por todo el planeta. Esta variante del problema del viajante de comercio puede simularse en el uso óptimo de una plataforma masiva de distribución como es Internet. • Problema de Scheduling: Este problema es más complejo de resolver, ya que se formula de tal manera que hay “T” tareas que realizar y “m” procesadores. El objetivo a la hora de utilizar el problema TSP es buscar una planificación en “m” procesadores para “T”, intentando minimizar el tiempo. Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 20 4. MÉTODOS DE RESOLUCIÓN DEL TSP Para la resolución del problema TSP, han ido evolucionando a lo largo de la historia diversas formas, estrategias y métodos. Algunos de estos métodos inicialmente eran realizados a mano, cuando el número de entidades o nodos era bastante pequeño, pero cuando empezaron a utilizarse en casos en los cuales la complejidad aumentaba exponencialmente debido al aumento de los nodos, tuvieron que poner en marcha distintos software y herramientas informáticas para su resolución. En este apartado, hablaremos de distintos métodos que se han ido llevando a cabo, y finalmente con cual de todos estos métodos nos quedaremos para poder resolver los problemas planteados en el apartado anterior. 4.1. Métodos exactos Cuando mencionamos métodos exactos, nos referimos a métodos que nos proporcionan un resultado final óptimo, es decir, la mejor solución que nos proporciona es la correcta. Para explicar un poco estos métodos, es importante mencionar que encontrar el óptimo exacto es más complicado de lo que parece, por ello muchos de los métodos que nos proporcionan un resultado exacto, serán para casos con complejidad baja, es decir, con pocos nodos que recorrer. A pesar de ello, hay métodos que son exactos y además el tiempo de ejecución se encuentra en un rango bastante aceptable para un gran número de nodos. Algunos de estos métodos podrían ser: • Método de Branch and Bound: El método de Branch and Bound o también conocido como ramificación y poda, nos proporciona una solución óptima del problema del agente viajero. Para ello hay que ir calculando la solución del modelo mediante el algoritmo Simplex, es decir, un método numérico que busca un mínimo o un máximo local de una función cualquiera, examinando en cada paso los vértices de un Simplex. A medida que el tamaño de la red aumenta, es decir, al ir aumentando el número de nodos, el tiempo de resolución también aumenta a gran escala, por lo que este método solo sería útil para redes de pequeño tamaño [15]. • Método de la fuerza bruta: El método de la fuerza bruta tan solo consiste en la exploración de todos los recorridos posibles, sin la aplicación de ningún algoritmo sistemático. Por ello, es un método, que se puede implementar y utilizar en problemas que tengan un número mínimo de nodos, ya que al contrario sería interminable. A continuación, mostramos un ejemplo de problema resolviéndose con el método de la fuerza bruta, donde los costes son las distancias entre los nodos en kilómetros, y el nodo origen es el punto A. Como se puede observar, se trazan todos los trazos posibles que Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 21 hay de un nodo a otro, y calculando todos los recorridos completos, sumando los distintos costes que implican, podría deducirse el camino y coste óptimo. Fig.6 Ejemplo de ejercicio con la Fuerza Bruta Fuente: Investigación de Operaciones, TSP. Ingeniería Industrial online [15] • Modelos matemáticos: Finalmente, en este apartado de métodos exactos, mencionaremos los modelos matemáticos. Con distintos modelos matemáticos, es decir, formulaciones de ciertas restricciones, funciones objeticos y variables, podemos conseguir un resultado del problema del TSP exacto. Si estos modelos matemáticos los resolvemos sin la utilización de ninguna herramienta informática o software, nos encontraríamos en la misma situación que los dos métodos anteriores, es decir, solo nos servirían para casos con poco número de nodos. Por el contrario, si usamos programas o aplicaciones informáticas, con este método, podríamos encontrar un resultado exacto de un problema del TSP con un gran número de ciudades. En nuestro trabajo, nos vamos a basar en estos métodos, usando cuatro modelos matemáticos diferentes, y ayudándonos de la herramienta Lingo (el cual usa un Branch and bound realmente para resolverlo), la cual nos permite que podamos hacer los problemas con una gran cantidad de ciudades, en un tiempo de ejecución bastante aceptable. Los modelos que vamos a desarrollar, y los cuales explicaremos en el siguiente apartado serán: - Modelo MTZ - Modelo DL - Modelo Intermedio - Modelo de Sarin Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 22 4.2. Métodos aproximados Cuando hablamos de métodos aproximados, nos referimos a aquellos en los que el resultado final que nos proporcionan no es exacto, si no próximo a él. Aunque no sean exactos, nos dan un óptimo bastante bueno y útil para resolver muchos problemas en la vida real. Además, estos métodos son mucho más sencillos de realizar y su tiempo de ejecución también se reduce bastante. Entre estos métodos podemos utilizar: • Métodos heurísticos: Son algoritmos que con poco esfuerzo computacional proporcionan una solución aproximada, pero no necesariamente óptima del problema [13]. Alguno de los métodos más utilizados para resolver el problema del TSP dentro de las heurísticas, son: - Métodos constructivos, son métodos deterministas en los que se suelen ir construyendo paso a paso una solución y se van eligiendo las mejores en cada iteración. Algunos ejemplos son el método del vecino más próximo o heurísticos de intersección. - Métodos de búsqueda local, o también llamados procedimientos de búsqueda. Estos procedimientos comienzan con una solución del problema y después van mejorando mientras se pueda la solución actual hasta que esta no pueda ser mejorada. La solución final se denominará óptimo local. Un ejemplo es el procedimiento de 2 intercambios. - Métodos combinados, que son los métodos en los que se combinan y mezclan los dos métodos anteriores, es decir, los de búsqueda y los constructivos. Más cercano Fig.7 Ejemplo del método del vecino más próximo Fuente: Elaboración propia v Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 23 4.3. Formulación general TSP Finalmente, como hemos explicado anteriormente, para la resolución de nuestros problemas TSP, vamos a utilizar dentro de los métodos exactos, unos modelos matemáticos con ayuda de la herramienta informática Lingo. Hablando ahora en términos del problema del viajante en sí, el objetivo es encontrar el orden en el cual se deben visitar cada una de las ciudades para poder minimizar la distancia recorrida. Todas las soluciones posibles a este problema, las llamaremos “tour”, sean las óptimas o no. Para empezar a formular estos problemas, hay que tener en cuenta que existen dos condiciones obvias que deben cumplirse siempre: • Condición 1: Exactamente una ciudad debe ser visitada inmediatamente después de la ciudad i [1]. Esta condición podría ser representada matemáticamente como: ∑𝑥𝑖𝑗 =1 𝑛 𝑗; ∀ⅈ=1…𝑛; ⅈ≠𝑗 • Condición 2: Exactamente una ciudad debe ser visitada inmediatamente antes de la ciudad j [1]. Esta condición podría ser expresada matemáticamente del siguiente modo: ∑𝑥𝑖𝑗 =1 𝑛 𝑖; ∀𝑗=1…𝑛; ⅈ≠𝑗 El valor Xij valdrá 1 cuando después de la ciudad i, el viajante vaya directamente a la ciudad j, en caso contrario, valdrá cero. A pesar de estas dos restricciones, no serían suficientes para plantear el modelo del problema TSP, y esto se puede demostrar con el siguiente ejemplo: Problema de ejemplo 1 Se nos plantea un problema en el que se quieren recorrer 7 ciudades diferentes, pasando por todas ellas, pero sin repetir y situadas de la siguiente manera: Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 24 Fig.8 Problema TSP de ejemplo, datos Fuente: Elaboración Propia Una solución que cumpla con las dos condiciones previamente descritas podría ser la siguiente: Fig.9 Problema TSP de ejemplo, solución 1 Fuente: Elaboración Propia Se puede observar a simple vista, que la solución cumple con las restricciones explicadas anteriormente. Pero si nos fijamos bien, no es lo que buscamos, ya que aparecen “subtour”. Los subtour son las rutas o los tours, que o bien no incluyen a la ciudad de origen, es decir, a la ciudad 0, o bien no incluyen a todas las ciudades, aunque empiece y acabe en cero. Para que no suceda este tipo de problemas, habría que añadir al modelo otras restricciones, que serán las que hagan las diferencias entre las distintas formulaciones que vamos a implementar en nuestro trabajo. Por otro lado, todos los modelos que vamos a estudiar tienen un mismo fin, y por lo tanto compartirán una misma función objetivo: reducir lo máximo posible los costes totales. Esta función podría ser: 𝑀ⅈ𝑛∑ 𝑛 𝑖∑𝑐𝑖𝑗𝑥𝑖𝑗 𝑛 𝑗 3 0 5 2 1 4 6 7 3 0 5 2 1 4 6 7 Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 25 Donde, el elemento Cij representa el valor exacto en cuanto a costes, que hay en ir desde la ciudad i hasta la j, y el valor Xij, es lo explicado anteriormente, es decir, valdrá 1 si se cumple que directamente después de estar en la ciudad i, se irá a la j. Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 32 R4) Esta restricción también se repite en el modelo anterior, y es para la variable que contiene la posición de las ciudades no supere al número de ciudades total. R5) También se repite en el modelo anterior, y es simplemente para que la variable de decisión Xij sea binaria. 5.2.3. Función Objetivo La función objetivo, vuelve a buscar la minimización de los costes totales en distancia: 𝑀ⅈ𝑛∑ 𝑛 𝑖∑𝑐𝑖𝑗𝑥𝑖𝑗 𝑛 𝑗 5.3. Modelo 3: Modelo intermedio Las características de este modelo son prácticamente iguales a las del modelo MTZ y el modelo DL, donde se vuelve a repetir que la diferencia está en la ecuación de eliminación de los subtours. En este caso, se hace una variación entre el modelo MTZ y el DL, por eso lo hemos llamado Modelo Intermedio, donde utiliza la restricción 3 del modelo MTZ y añade una cuarta restricción que provoca el mismo efecto que el cambio ocurrido en el modelo DL. 5.3.1. Elementos y Variables Los elementos de este modelo, al igual que ocurre en el modelo DL, son los mismos que los del modelo MTZ, ya que el cambio que hay es mínimo. Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 33 Elemento Tipo Variables asociadas Datos Ciudades/Nodos Índice i,j=1…N Ui(posición ciudad i), entero - Tramos/Arcos (i,j) - Cij (coste de i a j), entero Tabla 3. Elementos del modelo Intermedio Fuente: Elaboración propia Elementos y variables asociadas: • N: Será el número total de ciudades que existen en el problema. • Tramos: Son los recorridos que se formarán en ir de una ciudad i a una ciudad j. • Cij: Son los costes que supone ir de una ciudad i una ciudad j, recogidos en la matriz de datos. • Ui: Variable entera que implica el número de ciudades visitadas hasta la ciudad i. Básicamente esta variable indica cual es la posición de visita de la ciudad de partida i. Variables de decisión: • Xij: Es una variable binaria (valor 1 o 0), la cual dependerá de si el TRAMOS(i,j) es seleccionado o no para encontrar el óptimo. 𝑿𝒊𝒋 ={1,𝑠ⅈ 𝑠𝑒 𝑣ⅈ𝑠ⅈ𝑡𝑎 𝑙𝑎 𝑐ⅈ𝑢𝑑𝑎𝑑 𝑗 ⅈ𝑛𝑚𝑒𝑑ⅈ𝑎𝑡𝑎𝑚𝑒𝑛𝑡𝑒 𝑑𝑒𝑠𝑝𝑢é𝑠 𝑑𝑒 𝑙𝑎 𝑐ⅈ𝑢𝑑𝑎𝑑 ⅈ 0,𝑠ⅈ 𝑛𝑜 𝑠𝑒 𝑣ⅈ𝑠ⅈ𝑡𝑎 𝑙𝑎 𝑐ⅈ𝑢𝑑𝑎𝑑 𝑗 ⅈ𝑛𝑚𝑒𝑑ⅈ𝑎𝑡𝑎𝑚𝑒𝑛𝑡𝑒 𝑑𝑒𝑠𝑝𝑢é𝑠 𝑑𝑒 𝑙𝑎 𝑐ⅈ𝑢𝑑𝑎𝑑 ⅈ} 5.3.2. Restricciones En cuanto a las restricciones de este modelo, se vuelven a repetir las generales y cambia la del subtour, esta vez añadiendo simplemente una restricción nueva al modelo MTZ anterior: R1) ∑𝑥𝑖𝑗 =1 𝑛 𝑗 ; ∀ⅈ=1…𝑛; ⅈ≠𝑗 R2) ∑𝑥𝑖𝑗 =1 𝑛 𝑖 ; ∀𝑗=1…𝑛; ⅈ≠𝑗 R3) 𝑢𝑖−𝑢𝑗+𝑛𝑥𝑖𝑗 ≤𝑛−1 ; ∀𝑗,ⅈ=1…𝑛; ⅈ≠𝑗 R4) 𝑥ⅈ𝑗+𝑥𝑗ⅈ≤1 ; ∀𝑗,ⅈ=1…𝑛; ⅈ≠𝑗 Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 34 R5) 𝑢ⅈ≤𝑛 ; ∀ⅈ=1…𝑛 R6) 𝑥ⅈ𝑗∈[0,1] ; ∀𝑗,ⅈ=1…𝑛 En cuanto a la explicación de las restricciones anteriores: R1) Misma restricción y explicación que en los dos otros modelos. Para indicar que se visitará una ciudad inmediatamente después de la ciudad i. R2) Misma restricción y explicación que en los otros dos modelos. Para indicar que se ha visitado una ciudad previamente a la ciudad j. R3) Esta restricción es la de eliminación de los subtours, y es exactamente igual que la que se usó en el modelo MTZ, con su misma explicación. Lo único que varía es en la restricción siguiente. R4) Esta restricción es la que provoca la diferencia entre este modelo Intermedio y el modelo MTZ. También sirve para la eliminación de los subtours, y verdaderamente es la parte nueva que se añadió a la restricción 3 en el modelo DL, la que impedía los subtours entre dos ciudades. Lo que ocurre, es que en este modelo en vez de usar esa única restricción (𝑢𝑖−𝑢𝑗+ (𝑛−1)𝑥𝑖𝑗+(𝑛−3)𝑥𝑗𝑖 ≤𝑛−2) del modelo DL, utiliza la restricción 3 del modelo MTZ por un lado, y la otra por otro (𝑥𝑖𝑗+𝑥𝑗𝑖 ≤1). R5) Esta restricción se repite en los otros dos modelos. Es para que la variable asociada Ui no supere al número de ciudades total. R6) Finalmente, esta restricción también se repite en los otros dos modelos, y es para indicar que la variable de decisión Xij es binaria. 5.3.3. Función Objetivo La función objetivo, vuelve a buscar la minimización de los costes totales en distancia: 𝑀ⅈ𝑛∑ 𝑛 𝑖∑𝑐𝑖𝑗𝑥𝑖𝑗 𝑛 𝑗 Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 35 5.4. Modelo 4: Modelo de Sarin 5.4.1. Elementos y Variables Los elementos y las variables asociadas de este modelo son las mismas que en los tres modelos anteriores, ya que son los que se usan en todos de manera generalizada. Sin embargo, las variables de decisión sí que cambian [2]. Elemento Tipo Variables asociadas Datos Ciudades/Nodos Índice i,j=1…N Ui(posición ciudad i), entero - Tramos/Arcos (i,j) - Cij (coste de i a j), entero Tabla 4. Elementos del modelo de Sarin Fuente: Elaboración propia Elementos y variables asociadas: • N: Será el número total de ciudades que existen en el problema. • Tramos: Son los recorridos que se formarán en ir de una ciudad i a una ciudad j. • Cij: Son los costes que supone ir de una ciudad i una ciudad j, recogidos en la matriz de datos. Variables de decisión: • Xij: Es una variable binaria (valor 1 o 0), la cual dependerá de si el TRAMOS(i,j) es seleccionado o no para encontrar el óptimo. 𝑿𝒊𝒋 ={1,𝑠ⅈ 𝑠𝑒 𝑣ⅈ𝑠ⅈ𝑡𝑎 𝑙𝑎 𝑐ⅈ𝑢𝑑𝑎𝑑 𝑗 ⅈ𝑛𝑚𝑒𝑑ⅈ𝑎𝑡𝑎𝑚𝑒𝑛𝑡𝑒 𝑑𝑒𝑠𝑝𝑢é𝑠 𝑑𝑒 𝑙𝑎 𝑐ⅈ𝑢𝑑𝑎𝑑 ⅈ 0,𝑠ⅈ 𝑛𝑜 𝑠𝑒 𝑣ⅈ𝑠ⅈ𝑡𝑎 𝑙𝑎 𝑐ⅈ𝑢𝑑𝑎𝑑 𝑗 ⅈ𝑛𝑚𝑒𝑑ⅈ𝑎𝑡𝑎𝑚𝑒𝑛𝑡𝑒 𝑑𝑒𝑠𝑝𝑢é𝑠 𝑑𝑒 𝑙𝑎 𝑐ⅈ𝑢𝑑𝑎𝑑 ⅈ} Para que esta variable valga 1, la ciudad j tiene ser visitada inmediatamente después de la i. • Yij: Es una variable binaria (valor 1 o 0), la cual dependerá del CAMINO(i,j). También valdrá 1 si la ciudad j se visita después de la ciudad i, pero no es necesario que sea inmediatamente. 𝑌𝑖𝑗 ={1,𝑠ⅈ 𝑠𝑒 𝑣ⅈ𝑠ⅈ𝑡𝑎 𝑙𝑎 𝑐ⅈ𝑢𝑑𝑎𝑑 𝑗 𝑑𝑒𝑠𝑝𝑢é𝑠 𝑑𝑒 𝑙𝑎 ⅈ 𝑒𝑛 𝑐𝑢𝑎𝑙𝑞𝑢ⅈ𝑒𝑟 𝑚𝑜𝑚𝑒𝑛𝑡𝑜 0,𝑠ⅈ 𝑛𝑜 𝑠𝑒 𝑣ⅈ𝑠ⅈ𝑡𝑎 𝑙𝑎 𝑐ⅈ𝑢𝑑𝑎𝑑 𝑗 𝑑𝑒𝑠𝑝𝑢é𝑠 𝑑𝑒 𝑙𝑎 ⅈ 𝑒𝑛 𝑛ⅈ𝑛𝑔ú𝑛 𝑚𝑜𝑚𝑒𝑛𝑡𝑜} Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 36 5.4.2. Restricciones Las restricciones de este modelo [2] cambian más respecto a los otros tres modelos ya que se han introducido variables de decisión nueva. Las restricciones generales se mantienen, pero las relacionadas con la eliminación de los subtours cambia por completo, dejando de la siguiente manera la composición de las restricciones: R1) ∑𝑥𝑖𝑗 =1 𝑛 𝑗 ; ∀ⅈ=1…𝑛; ⅈ≠𝑗 R2) ∑𝑥𝑖𝑗 =1 𝑛 𝑖 ; ∀𝑗=1…𝑛; ⅈ≠𝑗 R3) 𝑦ⅈ𝑗≥𝑥ⅈ𝑗 ; ∀𝑗,ⅈ=2…𝑛; ⅈ≠𝑗 R4) 𝑦ⅈ𝑗+𝑦𝑗ⅈ=1 ; ∀𝑗,ⅈ=2…𝑛; ⅈ≠𝑗 R5) 𝑦ⅈ𝑗+𝑦𝑗𝑘+𝑦𝑘ⅈ≤2 ; ∀ⅈ,𝑗,𝑘=2…𝑛; ⅈ≠𝑗≠𝑘 R6) 𝑥ⅈ𝑗∈[0,1] ; ∀𝑗,ⅈ=1…𝑛 La explicación de todas estas restricciones es la siguiente: R1) La primera restricción es la general para todos, y se repite exactamente igual en los otros tres modelos, significando que se visitará una ciudad inmediatamente después de la ciudad i. R2) Esta restricción también se repite en los otros tres modelos anteriores, significando que se ha visitado una ciudad previamente a la ciudad j. R3) Esta restricción es la primera para la eliminación de los subtours. Como hemos explicado antes, la variable Yij mide si la ciudad j va después de la i en cualquier momento, y la variable Xij mide si va inmediatamente. Por lo tanto, si la ciudad j va después de la i, puede ser en cualquier momento por lo que Yij valdría 1, pero no tiene que ser inmediato, por lo que Xij podría valer 0. Por ello, es necesario que Yij sea siempre mayor o igual que Xij. Las dos valdrían 1 en el caso de que sea inmediato, las dos valdrían cero si aún no se ha pasado por esas ciudades o si la ciudad i no precede a la j, y finalmente Yij valdría 1 y Xij valdría 0, si la ciudad i precede a la j pero no en caso inmediato. Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 37 R4) Esta es la segunda restricción para la eliminación de los subtours, donde se conoce que si Yij valiese 1, significaría que la ciudad j va después de la i. Si esto se cumple, sería imposible que la variable Yji valiese 1, es decir, que la ciudad i fuese después de la ciudad j. Por lo tanto, sólo una de estas dos variables podría valer 1, quedando reflejado que la suma de estas dos variables tiene que ser obligatoriamente 1. R5) La quinta restricción es la última para la eliminación de los subtours, pero esta vez utiliza tres índices diferentes: i, j y k. Estos tres índices se utilizan para imponer una condición entre tres ciudades, siendo cada índice una de ellas. Significa que teniendo tres ciudades, si la ciudad i precede a la j, es decir, Yij vale 1, ya inmediatamente sabemos que la ciudad j va después de la i. Por otro lado, si la ciudad j precede a la ciudad k, es decir, Yjk vale 1, conocemos que la ciudad i es la primera, después la ciudad j y finalmente la k. Por ello, la variable Yki tendría que ser cero, provocando así que la suma máxima de estas tres variables sea 2. R6) Finalmente esta restricción es la misma que en los otros tres modelos, y es para indicar que la variable Xij es binaria. 5.4.3. Función Objetivo La función objetivo es la misma que en los tres modelos anteriores, es decir, buscar el camino total que requiera la menor distancia posible: 𝑀ⅈ𝑛∑ 𝑛 𝑖∑𝑐𝑖𝑗𝑥𝑖𝑗 𝑛 𝑗 5.5. Comentarios sobre los modelos Este apartado es simplemente para añadir que una de las restricciones que se repite en los tres primeros modelos, es decir, en el modelo MTZ, el modelo DL y el modelo Intermedio, podría cambiarse por una restricción que posiblemente disminuiría el tiempo de ejecución del problema, ya que trabaja con menos variables. Esta restricción es: 𝑢𝑖≤𝑛 ; ∀ⅈ=1…𝑛 Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 38 La cual se podría haber sustituido por: 𝑢𝑖≤𝑛−1 ; ∀ⅈ=1…𝑛 Es un simple cambio, pero al final provoca una exploración menos, por lo que podría disminuir el tiempo de ejecución y por lo tanto ser un modelo más favorable. Nosotros hemos querido desarrollar el modelo con la primera restricción ya que es más general, pero hemos experimentado con esta segunda forma solo con uno de los problemas, el br17 en concreto, para ver si el tiempo de ejecución variaba mucho, y es prácticamente el mismo. Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 39 6. LOS PROBLEMAS Antes de explicar y desarrollar los cuatro modelos que vamos a estudiar y con los cuales vamos a realizar todos los experimentos, vamos a detallar qué problemas son también los que vamos a usar, y ver las principales diferencias que hay entre ellos. A su vez explicaremos el formato en el que se encuentran, y qué datos nos están proporcionando. 6.1. Introducción de los problemas Estos enunciados a nuestros problemas están en un formato de archivo de texto (“.txt”), y todos simulan a localizaciones con ciertas ciudades dentro de ellas, las cuales querrían ser visitadas ahorrando el mayor coste posible. Dentro de ellos se encuentran los siguientes datos relevantes: • NAME: Nombre del problema, que nos orienta de su localización y dimensión. • TYPE: puede ser TSP o ATSP, diferencia que se explicará posteriormente. • DIMENSION: Dimensión del problema. Aquí se detalla la dimensión exacta de cada problema, en este caso la dimensión dependerá del número de ciudades que tenga cada problema. • DATOS COSTES: Todos los costes que existen en ir de una ciudad a otra. Esta parte del enunciado, nos la dan o bien en forma de matrices completas, o bien en matrices diagonales inferiores. Fig.10 Ejemplo de problema en fichero de texto Fuente: Elaboración propia Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 40 Los costes se encuentran en matrices, porque es la forma más sencilla de recopilar todos los datos. Cada fila de la matriz representa a una ciudad, y a su vez cada columna de la matriz representa también a cada ciudad. Para explicar mejor cómo se disponen los costes, usamos una matriz de ejemplo: (𝑎11 𝑎12 𝑎13 𝑎21 𝑎22 𝑎23 𝑎31 𝑎32 𝑎33) En esta matriz que sería de una dimensión 3x3, es decir, que tendríamos 3 ciudades, cada elemento de la matriz contiene los costes que hay entre la ciudad de su fila con la ciudad de su columna. De esta manera, por ejemplo, el elemento a12, contendría el coste que hay de ir de la ciudad 1 a la ciudad 2, o bien el elemento a32, es el coste que hay en ir de la ciudad 3 a la ciudad 2. A su vez hay que explicar, que los elementos diagonales, es decir, a11, a22 y a33, tendrían un valor igual a cero, ya que estos costes serían los que hay de ir desde una ciudad a ella misma, por lo tanto, esos costes son nulos. Por otro lado, hay una sola diferencia entre unos problemas u otros, sin tener en cuenta las diferencias de dimensión y costes propios, y esa diferencia es la que crea los dos grupos distintos de problemas con los que vamos a trabajar: Problemas simétricos y problemas asimétricos. 6.2. Problemas simétricos Cuando hablamos de problemas simétricos o también llamados los de tipo TSP, nos estamos refiriendo a aquellos en los que el coste de ir desde una ciudad i a una ciudad j es el mismo que el coste de ir desde la ciudad j a la ciudad i. Esto se ve reflejado en nuestra matriz de costes, en que los elementos opuestos tienen el mismo valor, es decir, es nuestra matriz de ejemplo anterior el valor del coste a12 será el mismo que el valor del coste a21. Por ello, a la hora del enunciado de los problemas, solo nos dan la matriz diagonal inferior para no repetir lo mismo en la matriz diagonal superior, ahorrando así un gran espacio. Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 41 Fig.11 Fichero de texto con enunciado de un TSP simétrico Fuente: Elaboración Propia Se puede comprobar con este ejemplo de problema simétrico, que únicamente nos dan la matriz diagonal inferior, ya que la otra parte de la matriz es la misma, pero de forma traspuesta, por lo que así ahorramos espacio. A su vez vemos que la diagonal está compuesta de ceros como hemos explicado antes, debido a que el coste de una ciudad a sí misma es nulo. A continuación, expondremos una tabla con todos los problemas simétricos que vamos a resolver, con su nombre y dimensión: Nombre del problema Dimensión (número de ciudades) Bays29 29 Brazil58 58 Gr17 17 Gr21 21 Gr24 24 Gr48 48 Hk48 48 Tabla 5. Listado de problemas simétricos Fuente: Elaboración propia Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 48 7.2.3. Interfaz con el usuario Una vez que ejecutamos la aplicación Lingo, lo primero que nos aparece es la siguiente ventana: Fig.16 Inicio de Lingo, interfaz con el usuario Fuente: Elaboración propia En esta página en blanco es donde comenzaremos a escribir el modelo en lenguaje Lingo que queremos solucionar, utilizando todo lo explicado anteriormente. Si queremos escribir un nuevo código solo hay que pulsar en la pestaña de la hoja en blanco, situada en la barra superior a la izquierda. En esa barra superior se encuentran varias herramientas que nos pueden servir de ayuda, pero la que vamos a explicar ya que es la más importante, es la que se necesita pulsar para que el modelo de Lingo se pueda solucionar: Fig.17 Ejecución en Lingo, interfaz con el usuario Fuente: Elaboración propia Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 49 Una vez definido el modelo con todos sus encabezados necesarios, sus elementos y variables definidas, sus restricciones y su función objetivo, solo habría que pulsar la pestaña de arriba, y Lingo nos daría en un tiempo de ejecución desconocido que dependerá de la complejidad del problema, la solución de este. Esto ocurrirá en caso de que todo esté perfectamente descrito y de que Lingo haya podido encontrar un óptimo, en caso contrario, saldrá un mensaje de error. Fig.18 Solución de Lingo, interfaz con el usuario Fuente: Elaboración propia Si todo es correcto, como hemos explicado, y Lingo encuentra para el modelo un óptimo, nos aparecerá esta pestaña a modo de resumen donde contendrá los datos principales de la resolución. Por ejemplo: • El tiempo de ejecución (Elapsed Runtime) • El óptimo encontrado (Objetive) • Número total de variables utilizadas (Variabletotal) • El tipo de modelo, en nuestro caso, MILP (Mixer Integer Linear Problems) (Solver Status- Model Class) • El tipo de método de resolución (Extended Solver Status- Solver Type) que usa, en nuestro caso un Branch and Bound. Seguidamente, después de esta pestaña, se nos abrirá otra que contiene el desarrollo de todo el problema. Aquí se detallarán todas las variables obtenidas en el modelo y sus valores, así como diversos datos que nos pueden ayudar a hacer un buen estudio del modelo. Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 50 7.3. Conversión de los ficheros (“.txt”) a Lingo Los enunciados de los diferentes problemas que vamos a desarrollar en esta experimentación se encuentran en ficheros de texto, es decir, en documentos de tipo “.txt”. Por lo tanto, necesitaremos alguna aplicación o método para realizar la conversión de dichos enunciados a nuestra herramienta de resolución Lingo. Gracias a la forma en la que nos enunciados vienen desarrollados en los ficheros, con los datos necesarios para la resolución de los problemas en forma de matriz, decidimos que la forma más sencilla para hacer el traspaso de datos sería a través de Excel. Además, esta forma es la más utilizada y estudiada en el Grado de Ingeniería de las Tecnologías Industriales, específicamente en una asignatura llamada Técnicas de Optimización que está ligeramente relacionada con este proyecto, y de la cual he obtenido muchos conocimientos para poder desarrollarlo. Primero explicaremos, el traspaso de los datos desde el fichero de texto hasta la aplicación Excel, y después explicaremos cómo se utiliza Lingo para poder extraer datos de Excel de una forma muy sencilla. 7.3.1. De Ficheros de Texto a Excel Para explicar este proceso, simplemente pondremos a modo de ejemplo el cambio de fichero a Excel de uno de los problemas. El ejemplo lo haremos con un problema asimétrico, ya que la matriz viene desarrollada al completo: Fig.19 Paso 1 para la conversión de enunciados Fuente: Elaboración propia Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 51 Se abre el fichero de texto del problema a resolver. Los datos que vamos a necesitar de aquí serán tanto la dimensión del problema como todos los costes que hay en la matriz. Una vez que el fichero de texto esté medianamente ordenado (en algunos ficheros venía la matriz peor definida), está listo para traspasarlo a Excel: Fig.20 Paso 2 para la conversión de enunciados Fuente: Elaboración propia Abrimos Excel, y lo primero que hacemos es pulsar en la barra superior a la izquierda, en la pestaña Archivo-Abrir (1). Después le daremos a examinar para poder buscar más fácilmente nuestro fichero de texto, siempre y cuando hayamos modificado previamente que se puedan abrir “Todos los archivos” (2). Si no se hace esto, solo nos dejará abrir documentos tipo Excel. Abrimos nuestro fichero de texto, y nos aparecerá lo siguiente: Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 52 Fig.21 Paso 3 para la conversión de enunciados Fuente: Elaboración propia Al abrir el fichero en Excel, lo primero que nos aparece es esta pestaña. En ella tendremos que pulsar la opción de “Delimitados”, y a continuación pulsar “Siguiente”. Lo segundo que nos aparecerá será la próxima imagen adjunta, en la que debemos de indicar cual será nuestro delimitador. Esto se refiere a qué será lo que provoque la separación en las distintas celdas de Excel. En nuestro caso, cada dato en el fichero viene separado simplemente por un espacio, por lo que nuestro delimitador será el “Espacio”: Fig.22 Paso 4 para la conversión de enunciados Fuente: Elaboración propia Posteriormente, habría que finalizar en esa misma pestaña, y automáticamente el fichero de texto se colocará en formato Excel. Cada dato del problema será una casilla del Excel, lo que nos permitirá trabajar con él. Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 53 Fig.23 Paso 5 para la conversión de enunciados Fuente: Elaboración propia Para finalizar el traspaso de los datos del Fichero de texto a Excel, únicamente sería necesario proporcionarles nombres dentro de Excel a esas ciudades y esos costes que se necesitan en Lingo. Esto es, dar nombre a la matriz completa de costes la cual la hemos llamado a todas “COSTES_NombreProblema” (en nuestro ejemplo será COSTES_br17), y por otro lado, crear un vector “CIUDADES_NombrePorblema”, que contendrá a todas las ciudades del problema (en nuestro ejemplo de llamará “CIUDADES_br17”). Todo esto se puede comprobar en la imagen colocada en la parte superior. 7.3.2. De Excel a Lingo Ahora, necesitamos que Lingo sea capaz de leer todos esos datos de Excel para que poder resolver el problema. Para ello simplemente debemos conocer una función que usa Lingo para leer datos de Excel. Esa función es @OLE, utilizándola junto con los nombres definidos anteriormente en el propio Excel, Lingo sería capaz de recoger todos esos datos que necesita. Para utilizarla correctamente, a la hora de describir los elementos y los conjuntos en Lingo en la sección SETS y DATA, debemos de escribir esta función seguida de los nombres de los datos de Excel. En el ejemplo de Lingo que vimos en el subapartado 7.2, los valores de los costes lo dábamos de manera: DATA: C= 1, 2, 3, 4, 5,6,7,8,9,10,11,12,13,14,15,16; ENDDATA Sin embargo a través de Excel, lo escribiremos de la siguiente manera: Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 54 DATA: C=@ole("Matriz_NombreProblema.xlsx","COSTES_NombreProblema"); ENDDATA Esto es, porque a todos los documentos de Excel que contienen las matrices de datos los hemos llamado Matriz_NombreProblema, y a los datos de costes los hemos llamado COSTES_NombreProblema. De igual manera se utilizará el vector de las ciudades, quedando finalmente en Lingo el siguiente código: Fig.24 Paso 6 para la conversión de enunciados Fuente: Elaboración propia 7.4. Los Modelos finales en Lingo A continuación, mostraremos cómo han quedado finalmente nuestros cuatro modelos en Lingo. Los modelos que se van a desarrollar están escritos para el primer problema desarrollado, es decir, el problema br17. De esta manera es más fácil entender la estructura, y simplemente habría que cambiar el nombre del problema por otro que se quiera resolver. - Donde pone “Matriz_br17.xlxs”, iría el nombre del Excel que contiene el enunciado del problema. - Donde pone “CIUDADES1_br17”, iría el vector ciudades explicado anteriormente, que tiene la dimensión del problema. - Donde pone “COSTES_br17” irían los datos de los costes entre las distintas ciudades del problema. - Y donde pone n, sería la dimensión del problema, que en este caso sería un 17. Lo único a cambiar en el resto de problemas es poner el nombre del problema a resolver, en lugar de br17. Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 55 7.4.1. Modelo MTZ Fig.25 Modelo MTZ en Lingo Fuente: Elaboración propia 7.4.2. Modelo DL Fig.26 Modelo DL en Lingo Fuente: Elaboración propia Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 56 7.4.3. Modelo Intermedio Fig.27 Modelo Intermedio en Lingo Fuente: Elaboración propia 7.4.4. Modelo de Sarin Fig.28 Modelo de Sarin en Lingo Fuente: Elaboración propia Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 57 8. EXPERIMENTACIÓN En este apartado desarrollaremos la experimentación llevada a cabo, así como la exposición de todos nuestros resultados con los diferentes modelos y en los diferentes problemas, para poder compararlos de una forma sencilla. Primero mostraremos la batería de problemas que hemos ejecutado, y seguidamente comenzaremos a comparar los resultados finales. Es importante mencionar que la ejecución de los problemas se ha parado al llevar una hora ya que, en caso de no hacerlo, podríamos pasarnos días esperando a que un problema se resuelva. Esta experimentación se podría hacer en cualquier periodo de tiempo determinado, siempre y cuando todos tengan el mismo, para poder hacer una comparación coherente. Debido a esto, no podríamos decir que estamos obteniendo datos totalmente exactos en todos los problemas, ya que muchos de ellos, al interrumpirlos no llegarían al óptimo real, pero si a una aproximación. Para la comparación de los diferentes modelos vamos a separar primero los problemas en simétricos y asimétricos, para ver cómo se comportan los modelos con ambos tipos de problemas. Una vez especificado en el tipo de problema en el que nos encontramos, comenzaremos a comparar por tablas, basándonos en cuatro criterios por separado: • El error: Esto lo calcularemos con la siguiente fórmula del error, para poder ver qué margen de error tenemos con la solución obtenida por nosotros y el verdadero óptimo del problema. 𝑒𝑟𝑟𝑜𝑟(%)=ó𝑝𝑡𝑖𝑚𝑜 𝑚𝑜𝑑𝑒𝑙𝑜−ó𝑝𝑡𝑖𝑚𝑜 𝑟𝑒𝑎𝑙 ó𝑝𝑡𝑖𝑚𝑜 𝑟𝑒𝑎𝑙 𝑥100 • Tiempo de ejecución: Para esta comparación, simplemente miraremos el tiempo de ejecución de cada problema. En caso de que el problema haya sido interrumpido debido a la superación de la hora, pondremos una “I” de interrumpido (lo cual supondrá que el tiempo de ejecución ha sido una hora), en caso contrario, pondremos los minutos y segundos exactos de ejecución. • Número de óptimos conseguidos: En esta tabla escribiremos el número de óptimos totales, es decir, dentro del periodo de la hora, en cuántos problemas distintos han podido cada modelo conseguir su óptimo. Si el modelo MTZ tiene un 4, significa que ha sido capaz de obtener el óptimo real de 4 de los problemas que ha ejecutado. • Lower Bound: Esta parte de la comparación la haremos solo para dos problemas de cada tipo, ya que supone una nueva experimentación con Lingo cambiando la restricción de la variable Xij binaria, por una que indique ser menor o igual a 1 (Xij<=1). Esto nos proporcionará el Lower Bound o límite inferior. Cuanto más próximo al óptimo, mejor. Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 64 8.2. Experimentación Problemas Simétricos Para este tipo de problemas realizaremos exactamente lo mismo que en el subapartado anterior, es decir, mostraremos la batería de problemas a resolver, y posteriormente haremos las cuatro comparativas distintas, mostrando los diferentes resultados y analizando cuál de los cuatro modelos es más eficaz para estos problemas. Tabla 13. Listado de problemas simétricos Fuente: Elaboración propia • Comparación según el error: Tabla 14. Comparación por error Problemas Simétricos Fuente: Elaboración propia Para comenzar la comparación en los problemas simétricos, comprobaremos el porcentaje de error total que tienen cada uno de los modelos para todos sus problemas. Nombre del problema Dimensión (número de ciudades) Bays29 29 Brazil58 58 Gr17 17 Gr21 21 Gr24 24 Gr48 48 Hk48 48 Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 65 Es el mismo procedimiento que en los problemas asimétricos, y se puede comprobar que el modelo de Sarin tiene un alto porcentaje de error. Le sigue el modelo Intermedio, donde se reduce muchísimo ese porcentaje, pero que al compararlo con los modelos MTZ y DL, con un 0% de error, también sería descartado. Por lo tanto, según esta comparación, nos quedaríamos como modelos más eficaces tanto el modelo MTZ como con el modelo DL. • Comparación según el tiempo de ejecución: Tabla 15. Comparación por tiempo Problemas Simétricos Fuente: Elaboración propia Aquí compararemos los distintos tiempos de ejecución, de la misma manera explicada en los problemas asimétricos. También se han interrumpido al transcurrir una hora de ejecución y se ha señalado con la “I” de interrumpido. Todos los modelos han ido medianamente rápido, pero al igual que antes, destacan los modelos MTZ y DL, siendo los más rápidos en cuanto a tiempo de ejecución. Esto se debe a que tres de ellos se han resuelto más rápido con el modelo MTZ, y los otros tres se han resuelto más rápido con el modelo Dl. El problema “gr48” ha sido el único en no poder resolverse en un tiempo igual o inferior a la hora por uno de estos dos modelos, el resto se han resuelto sin problemas. Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 66 • Comparación por número de óptimos conseguidos: Tabla 16. Comparación por óptimos Problemas Simétricos Fuente: Elaboración propia Esta tercera comparación se ha realizado según el número de óptimos conseguidos en el periodo de ejecución establecido. Es el mismo proceso que en los problemas asimétricos, es decir, contabilizar los óptimos de los problemas conseguidos por cada uno de los modelos. Como se puede observar en la tabla superior, se vuelve a descartar el modelo de Sarin, que a pesar de que consigue resolver con óptimos más de la mitad de los problemas, los otros modelos le han superado. Le sigue el modelo Intermedio, que logra casi un 80% de óptimos, pero los modelos MTZ y DL vuelven a ser los más eficientes, con un 100% de óptimos resueltos en el periodo de tiempo. Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 67 • Comparación según el Lower Bound: Tabla 17. Comparación por tiempo Problemas Simétricos Fuente: Elaboración propia Esta última comparación se hace con el Lower Bound, exactamente igual que como se ha realizado con los problemas asimétricos. Este Lower bound es el límite inferior, por lo que cuanto más próximo al óptimo del problema, mejor. Todos los modelos se han acercado más o menos igual, pero ha destacado el modelo Intermedio, siendo tanto en el problema “bays29” como en el problema “gr17” el que ha proporcionado una solución más próxima a sus respectivos óptimos. • Comparación final: Para la comparación final de los cuatro modelos según la resolución de seis problemas simétricos, se ha podido comprobar que los modelos que más han destacado por su inmejorable resolución, con una aproximación casi exacta a los óptimos y un tiempo de ejecución bastante bueno, han sido los modelos MTZ y DL. Estos dos modelos han sido capaces de proporcionar un óptimo exacto del total de los problemas, con un error del 0%, además de ejecutarlos en un periodo bastante rápido. Por otro lado, el modelo de Sarin una vez más ha sido el primer descartado, pero es importante mencionar que este modelo funciona mejor con los simétricos que con los asimétricos. En cuanto al modelo Intermedio, ha proporcionado muy buenos resultados, pero no ha destacado como ha ocurrido con los problemas asimétricos. Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 68 9. CONCLUSIÓN Gracias a la existencia de librerías de optimización como LINGO y utilizando cuatro modelos matemáticos de optimización diferentes (MTZ, DL, Intermedio y Sarin), en este proyecto hemos analizado la resolución de una batería de problemas TSP, de diferentes tamaños y características. La conclusión más importante es que para los problemas asimétricos sería más oportuno utilizar el modelo Intermedio, y para los problemas simétricos, el modelo MTZ o el modelo DL. Estos modelos a la hora de nuestra experimentación nos han proporcionado una optimización y un tiempo de ejecución aceptables. Este trabajo podría utilizarse en otros muchos estudios y en la resolución de diversos problemas, que como indicábamos al comienzo del trabajo, tienen muchas aplicaciones en la vida real. Por ello, por su gran demanda y aplicación, la resolución y el desarrollo de estos problemas del TSP resultan muy interesantes y de gran provecho, sobre todo mirando un horizonte en los que la tecnología permita la resolución exacta de problemas de gran tamaño. Actualmente, muchos de los rompecabezas que se pueden plantear en el día a día están relacionados con estos problemas, así como la organización de actividades o viajes, la recogida de personas o cosas, o incluso las secuencias de trabajos, por lo que supone de gran utilidad ponerlo en marcha, utilizando en caso necesario estas herramientas y modelos desarrollados. Además, se utiliza una herramienta informática muy eficaz, Lingo, con la que puede resolverse cualquier problema de optimización. Gracias a este trabajo, hemos podido exprimir al máximo esta herramienta, profundizar en ella y ver las distintas capacidades y usos que nos puede proporcionar, observando que, en problemas de bastante complejidad y tamaño es capaz de proporcionar soluciones óptimas en cuestión de segundos o minutos. Finalmente, me gustaría resaltar el esfuerzo de acometer un estudio experimental dentro del área de la optimización. La implementación, el chequeo de errores y obtener conclusiones de un análisis de este tipo han supuesto todo un reto para mí. Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 69 10. BIBLIOGRAFÍA [1] London School of Economics “Model of Solving the Travelling Salesman Problem” Autor: H.P. Wiliams [2] Operation Research Letters 33 “New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints” Autor: Subhash C. Sarin (2003) [3] Lecture Notes in Computer Science book series (LNCS) “The Traveling Salesman, Computational Solutions for TSP applications” Autor: Gerhard Reinelt (1994) [4] ProQuest Ebook Central “The Traveling Salesman Problem: A Computational Study” Priceton University Press (2007) [5] Scientia et Technica Año XXII, Vol. 22, No. 4 “An Application of the MTZ method to the solution of the Travelman Salesman Problem” Autores: Jairo Alberto Villegas Flórez, Carlos Julio Zapata Grisales¸ Gustavo Gatica Ingeniería Industrial, Universidad Tecnológica de Pereira, Pereira, Colombia. Ingeniería Industrial, Universidad Andrés Bello, Chile [6] Universidad de Santiago de Compostela, Máster Interuniversitario en Técnicas Estadísticas “Cooperación en los problemas del viajante (TSP) y de rutas de vehículos (VRP): una panorámica” Autor: Aida Calviño Martínez (2011) [7] Tesis USM, Universidad Técnica Federico Santa María “Formulaciones basadas en Flujos en redes para un problema de ruteo en Last Mile” Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 70 Autor: Álvaro Javier Correa Maldonado [8] Modelos y Optimización I “El problema del Viajante: Conceptos, Variaciones y Soluciones Alternativas” Autor: Lic. Silvia A.Ramos [9] European Journal of Operational Research 59 “The Traveling Salesman Problem: An overview of exact and approximate algorithms” Autor: Gilbert Laporte (1992) [10] Programación matemática del grado de matemáticas en la Universidad de Cádiz “El problema del viajante de Comercio o TSP” Autores: Azahara Carpintero, Juan de Dios Días Ramírez, Victoria Franco Otero. [11] Universidad Autónoma del Estado de Hidalgo URL: https://www.uaeh.edu.mx/scige/boletin/tlahuelilpan/n3/e5.html [12] Asociación Nacional de Estudiantes de Matemáticas URL: http://www.anem.es/web/2018/09/el-problema-del-viajante/ [13] Programación matemática del grado de matemáticas en la Universidad de Cádiz URL: http://knuth.uca.es/moodle/mod/page/view.php?id=3417 [14] Ingeniería de Organización: Métodos Cuantitativos de Gestión “Resolución de problemas, Librerías de Optimización Lingo” Autor: José Manuel García Sánchez [15] Ingeniería Industrial Online URL: https://www.ingenieriaindustrialonline.com/investigacion-de-operaciones/problema-del- agente-viajero-tsp/ Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 71 [16] Universidad Autónoma del Estado de Hidalgo URL: https://www.uaeh.edu.mx/scige/boletin/tlahuelilpan/n3/e5.html Estudio Experimental Problema TSP Universidad de Sevilla Ana Corral Sánchez 72