Problemas de diseño de redes con restricciones de saltos (hop constraints)

Universidad de Valladolid Facultad de Ciencias Trabajo Fin De Grado Grado en Estadística Problemas de diseño de redes con restricciones de saltos (hop constraints) Alumno: Andrés Bravo Núñez Tutor: Jesús Sáez Aguado Problemas de diseño de redes con restricciones de saltos (hop constraints) Andrés Bravo Núñez Índice general Lista de figuras iii Lista de tablas iv Resumen ix Introducción 1 Objetivosdeltrabajo................................. 1 Herramientasutilizadas ............................... 2 1. Resolución Exacta 4 1.1. Formulación de flujos multi-producto . . . . . . . . . . . . . . . . . . . . . 4 1.2. Formulaciones basadas en restricciones de Miller-Tucker-Zemlin . . . . . . 8 1.2.1. Elevando las restricciones . . . . . . . . . . . . . . . . . . . . . . . 10 1.2.2. Restricciones topológicas mejoradas . . . . . . . . . . . . . . . . . . 12 1.2.3. Modelos de Sherali y Driscoll . . . . . . . . . . . . . . . . . . . . . 16 2. Heurísticas 20 2.1. Heurísticadeahorros.............................. 21 2.2. Algoritmos de segundo orden . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.3. Vecindarios basados en un modelo de programación dinámica . . . . . . . . 24 2.3.1. Representación de un árbol mediante el nivel de los vértices . . . . 24 2.3.2. Un modelo de programación dinámica para el problema HMST . . . 24 2.3.3. Vecindarios ............................... 27 i Índice general Índice general 3. Metaheurísticas 29 3.1. Recocido Simulado (Simulated annealing)................... 30 3.2. GRASP (Greedy randomized adaptive search procedure)........... 32 4. Resultados Computacionales 35 4.1. Resultados de los modelos exactos . . . . . . . . . . . . . . . . . . . . . . . 38 4.2. Resultados de las Heurísticas . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.3. Resultados de las Metaheurísticas . . . . . . . . . . . . . . . . . . . . . . . 46 4.3.1. SA.................................... 46 4.3.2. GRASP ................................. 48 5. Conclusiones 51 A. Tablas de resultados extendidas 54 A.1.ModelosExactos ................................ 54 A.2. Resultados de los modelos exactos . . . . . . . . . . . . . . . . . . . . . . . 54 A.2.1.Modelosdeflujo ............................ 54 A.2.2. Modelos con restricciones MTZ . . . . . . . . . . . . . . . . . . . . 56 A.2.3. Modelos con restricciones elevadas . . . . . . . . . . . . . . . . . . . 58 A.2.4. Modelos con restricciones topológicas mejoradas . . . . . . . . . . . 59 A.2.5. Modelos con restricciones de Sherali y Driscoll . . . . . . . . . . . . 61 A.3.Heurísticas.................................... 63 A.3.1. Heurística de ahorros . . . . . . . . . . . . . . . . . . . . . . . . . . 63 A.3.2. Algoritmos de segundo orden . . . . . . . . . . . . . . . . . . . . . 66 A.3.3. Vecindarios basados en un modelo de programación dinámica . . . . 68 A.4.Metaheurísticas................................. 74 A.4.1. Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . 74 A.4.2.GRASP ................................. 80 Apéndices 54 Bibliografía 84 Andrés Bravo Núñez ii Índice de figuras 2.1. Ejemplo de una transición (adaptado de [18]) . . . . . . . . . . . . . . . . 26 2.2. Movimiento simple (adaptado de [18]) . . . . . . . . . . . . . . . . . . . . . 27 2.3. Intercambio (adaptado de [18]) . . . . . . . . . . . . . . . . . . . . . . . . 27 iii Índice de cuadros 4.1. Archivos en OR-Library para el problema del mínimo árbol de Steiner . . . 35 4.2. Problemas seleccionados para probar los modelos exactos y las heurísticas . 37 4.3. Soluciones obtenidas con los modelos MCF 1.1, HopMCF 1.8 y MCF* 1.3 1.4 ........................................ 39 4.4. Soluciones obtenidas con los modelos MTZ 1.10 y EMTZ 1.12 . . . . . . . 40 4.5. Soluciones obtenidas con los modelos L1EMTZ 1.22 y L2EMTZ 1.26 . . . . 40 4.6. Soluciones obtenidas con los modelos MTZ/ITEF 1.27, IMTZ/ITEF 1.30 yREL-M1.31.................................. 41 4.7. Soluciones obtenidas con los modelos HMST-SD 1.32 y HMST-SD/ITEF 1.33 ....................................... 42 4.8. Soluciones obtenidas con la heurística de ahorros EW . . . . . . . . . . . . 43 4.9. Soluciones obtenidas con los algoritmos de segundo orden . . . . . . . . . . 44 4.10. Soluciones obtenidas con los vecindarios basados en un modelo de programacióndinámica ................................ 46 4.11. Soluciones obtenidas con Simulated Annealing . . . . . . . . . . . . . . . . 48 4.12. Soluciones obtenidas con GRASP . . . . . . . . . . . . . . . . . . . . . . . 49 A.1. Soluciones obtenidas con los modelos con los modelos MCF, HopMCF y MCF∗...................................... 56 A.2. Soluciones obtenidas con los modelos MTZ y EMTZ . . . . . . . . . . . . . 57 A.3. Soluciones obtenidas con los modelos L1EMTZ y L2EMTZ . . . . . . . . . 59 A.4. Soluciones obtenidas con los modelos MTZ/ITEF, IMTZ/ITEF y REL-M . 61 A.5. Soluciones obtenidas con los modelos HMST-SD y HMST-SD/ITEF . . . . 63 A.6. Soluciones obtenidas con la heurística de ahorros de EW . . . . . . . . . . 66 A.7. Soluciones obtenidas con los algoritmos de segundo orden . . . . . . . . . . 68 A.8. Soluciones obtenidas con los vecindarios basados en un modelo de programacióndinámica ................................ 74 A.9. Soluciones obtenidas con Simulated Annealing . . . . . . . . . . . . . . . . 80 A.10.Soluciones obtenidas con GRASP . . . . . . . . . . . . . . . . . . . . . . . 83 iv Dedicado a mi familia v Introducción Herramientas utilizadas Heurísticas: Desarrollaremos deferentes métodos que buscan encontrar una solución próxima al óptimo ya sea construyendo una solución desde cero o realizando una búsqueda en el entorno de una solución conocida. Metaheurísticas: Se desarrollaran un conjunto de métodos que tratan de mejorar los métodos heurísticos introduciendo cierta aleatoriedad en los mismos. Resultados: Se mostrarán los resultados obtenidos con los diferentes métodos propuestos y se comentarán los mismos con el fin de facilitar la interpretación. Conclusiones: se expondrá el conjunto de conclusiones obtenidas a lo largo del trabajo y se realizará una recomendación sobre como resolver este problema en un caso real. Herramientas utilizadas Se han utilizado las siguientes programas: El entorno de modelado y resolución de problemas de optimización: Xpress-Mosel (rellenar la información de la versión) El lenguaje de programación R Xpress-Mosel ha sido utilizado para la resolución exacta y R para las heurístecas y metaheurística. La elección de este conjunto de programas, se debe principalmente a que su uso está muy extendido y a la facilidad de acceso, ya sea por su gratuidad o debido a que ofertan una versión para estudiantes. Los cáculos han sido realizados cuando ha sido posible en un ordenador con las siguientes especificaciones:Intel®Core™i5-4200U 1.65GHz con 8 GB de RAM. En caso de imposibilidad debido a límites en la licencia estudiantil de Xpress-Mosel se ha usado un servidor cedido por la Universidad de Valladolid para este propósito. Andrés Bravo Núñez 2 Introducción Herramientas utilizadas Andrés Bravo Núñez 3 Capítulo 1 Resolución Exacta La resolución exacta nos ofrece la mejor solución que es, la que prefeririamos tener siempre que podamos. Para obtener esta solución en el problema HMST necesitamos un modelo matemático con restricciones. Geir Dahl, Luis Gouveia y Cristina Requejo definen el problema de la siguiente manera[9]: Dado G= (V, E)un grafo con un conjunto de nodos V={0,1, . . . , n}y un conjunto de aristas E,cecostes asociados a cada arista e∈Ey un número natural H, deseamos encontrar en el grafo un árbol generador Tcon coste mínimo tal que el camino único desde el nodo raiz (nodo 0 a partir de ahora) a cualquier otro no incluya más de Hsaltos (aristas). A continuación, se mostrarán una selección de modelos exactos para este problema. La razón por la que se exponen más de un modelo exácto es que las relajaciones de los mismos, pueden aportar cotas más o menos ajustadas según los parámetros o características del problema. Que un modelado del problema tenga una relajación con una cota más ajustada implica por lo general, un menor tiempo para encontrar la solución óptima (esto se debe a que los programas de optimización usan algoritmos de tipo ramificación y poda). Cabe decir, que para la evaluación de los modelos exactos se han usado las relajaciones que usa Xpress-Mosel por defecto y no los recomendados en la literatura [7] [17] [3]. 1.1. Formulación de flujos multi-producto En este apartado, se describirá una formulación de flujos multi-producto para HMST que utiliza arcos dirigidos (La arista {i, j}es remplazada por los arcos (i, j)y(j, i)) y algunas variantes surgidas de la misma. Las variables de decisión son Xij((i, j)∈A)que indican si el arco (i, j)del conjunto de arcos Ase incluye en la solución e Yijk((i, j)∈ A;k∈V\ {0};k6=i)que muestran si el camino único del nodo raíz hasta el nodo k atraviesa el arco (i, j). 4 Capítulo 1. Resolución Exacta 1.1. Formulación de flujos multi-producto Modelo MCF Multicommodity Flow[15] minimizar X (i,j)∈A cijXij (1.1a) sujeto a X i∈V\{j} Xij = 1, j ∈V\ {0}(1.1b) X i∈V\{k} Yijk −X i∈V\{0} Yjik =     −1, j = 0 0, j 6= 0, k j ∈V\ {0, k} 1, j =k (1.1c) X (i,j)∈A ≤H(1.1d) Yijk ∈ {0,1},(i, j)∈A;k∈V(1.1e) Yijk ≤Xi,j,(i, j)∈A;k∈V\ {0}(1.1f) Xij ∈ {0,1},(i, j)∈A(1.1g) Las restricciones (1.1f) relacionan los dos conjuntos de variables. Obligan a que si el arco (i, j)esta en un camino de tamaño Hal nodo k entonces esta en el conjunto solución. Las restricciones (1.1c) indican que si un arco entra (o sale) en un nodo debe haber un arco saliente (o entrante) excepto para el nodo k, en el que hay un arco entrante más, y el nodo raíz, en el que hay un arco saliente más. Las restricciones (1.1d) marcan que no puede haber más de Harcos del nodo raíz al nodo k. En conjunto las restricciones (1.1c)-(1.1e) hacen que los conjuntos de arcos definidos por Y.k incluyan los caminos de tamaño H (aunque también se incluyen paseos de tamaño y otros conjuntos de arcos) pero gracias a las otras restriccionnes solo los H-caminos pueden formar parte de la solución. Estas restricciones se pueden sustituir por otras que obliguen a que solo los H-caminos esten en la solución. De una manera más general: Modelo MCF General[15] minimizar X (i,j)∈A cijXij (1.2a) sujeto a X i∈V\{j} Xij = 1, j ∈V\ {0}(1.2b) Y.k ∈Fk,(i, j)∈A;k∈V(1.2c) Yijk ≤Xi,j, k ∈V\ {0}(1.2d) Xij ∈ {0,1},(i, j)∈A(1.2e) Andrés Bravo Núñez 5 Capítulo 1. Resolución Exacta 1.1. Formulación de flujos multi-producto Donde Y.k es el vector de componentes Yijk((i, j)∈A;k∈V\ {0};k6=i)yFkes el conjunto de todos los H-caminos de 0ak. Idealmente, se buscan restricciones que definan el conjunto más pequeño que contenga los caminos de tamaño H y esto es, la envolvente convexa para cada Fk,conv(Fk). Actualmente se conocen formulaciones de este tipo para H= 2 yH= 3: Modelo MCF*H= 2 [7] minimizar X (i,j)∈A cijXij (1.3a) sujeto a X i∈V\{j} Xij = 1, j ∈V\ {0}(1.3b) X0j≥Xjk,(j, k)∈A(1.3c) Xij ∈ {0,1},(i, j)∈A(1.3d) Modelo MCF*H= 3 [15] minimizar X (i,j)∈A cijXij (1.4a) sujeto a X i∈V\{j} Xij = 1, j ∈V\ {0}(1.4b) X i∈V\{k} Yijk −X i∈V\{0} Yjik =     −1, j = 0 0, j 6= 0, k j ∈V\ {0, k} 1, j =k (1.4c) Yjkk ≥X i∈V\0 Yijk, j ∈V\0, k;k∈V\0(1.4d) Xij ∈ {0,1},(i, j)∈A(1.4e) Yijk ∈ {0,1},(i, j)∈A;k∈V(1.4f) Para H > 4encontrar la envolvente convexa se vuelve complicado ya que encontrar la envolvente convexa es en si mismo un problema NP-Hard. Sea Wkel conjunto de H-paseos de 0 a k. Está demostrado que sustituir en estos problemas conv(Fk)por conv(Wk)lleva a la misma solución óptima[9]. Encontrar una descripción de conv(wk)es más sencillo pero genera un conjunto exponencial de restricciones[8] por lo cual no es práctico. Sin embargo encontrar el camino más corto en Wkse puede modelar en un grafo acíclico expandido con facilidad. El grafo expandido GE= (VE, AE) es el grafo original replicado Hveces. VEse define como: VE= (0,0) ∪ {(i, h):1≤h≤H−1and V\ {0}} ∪ (k, H)(1.5) Andrés Bravo Núñez 6 Capítulo 1. Resolución Exacta 1.1. Formulación de flujos multi-producto Es decir (i, h), implica que en el grafo original el nodo ies visitado en el salto h. Los arcos AEson definidos por: AE={((0,0),(j, 1)) : j∈V\ {0}}∪ {((i, h),(j, h + 1)) : (i, j)∈A, i 6= 0, i 6=kand 1< h < H −2}∪ {((i, H −1),(k, H)) : i∈V\ {0}and 1< h < H −2}∪ {((k, h),(k, h + 1)) : 1 < h < H −1}. (1.6) Los arcos de la forma ((k, h),(k, h + 1)) equivaldrían a bucles en el nodo ken el grafo original y serían descartados a efectos de la solución. Si asociamos una variable Zijk a cada arco ((i, h −1),(j, h)) de GEpodemos escribir un modelo para encontrar el H-camino de menor coste de 0aH. Además las variables Zijk pueden reinterpretarse en Gcomo indicadores de si el arco (i, j)es el h-ésimo arco en el camino del nodo raíz al nodo k. El modelo resultante es el siguiente: Modelo Hop-Path(k),k∈V\ {0}[17] minimizar X (i,j)∈A H X q=1 cijZijq + n X i=1 H X q=2 0Ziiq (1.7a) sujeto a X j∈V ZjkH = 1 (1.7b) X j∈V Zjih −X j∈V\{0} Zij,h+1 = 0 i∈V\ {0};h= 2, . . . , H −1(1.7c) Z0i1−X j∈V Zij2= 0,(0, i)∈A(1.7d) Z0j1∈ {0,1},(0, j)∈A(1.7e) Zijh ∈ {0,1},(i, j)∈A;i6= 0; h= 2, . . . , H or i=j=k. (1.7f) Las restricciones (1.7d) muestran que el arco (0, i)es el primer arco del camino solamente si existe un arco saliendo de ien h= 2. Las restricciones (1.7c) obligan a que si un arco entra en ien la posición hotro debe salir de ien h+ 1. Por último (1.7b) hace que solamente un arco pueda entrar en ken la posición H. Una vez tenemos esto podemos combinar esta idea en el modelo 1.2. Para ello, debemos añadir a las Zun indíce más por cada camino que buscamos, esto es un nuevo indice w en V y además algunas condiciones w∈V\{0}ya que no tiene sentido buscar un camino de la raíz a sí misma: Andrés Bravo Núñez 7 Capítulo 1. Resolución Exacta 1.2. Formulaciones basadas en restricciones de MTZ Modelo HopMCF [17] minimizar X (i,j)∈A cijXij (1.8a) sujeto a X i∈V\{j} Xij = 1, j ∈V\ {0}(1.8b) X j∈V ZjkHw = 1 (1.8c) X j∈V Zjihw −X j∈V\{0} Zij,h+1,w = 0 i∈V\ {0};h= 2, . . . , H −1(1.8d) Z0i1w−X j∈V Zij2w= 0,(0, i)∈A(1.8e) Z0j1w∈ {0,1},(0, j)∈A, w ∈V\ {0}(1.8f) Zijhw ∈ {0,1},(i, j)∈A;w∈V\ {0};i6= 0; h= 2, . . . , H or i=j=k. (1.8g) Xij ∈ {0,1},(i, j)∈A(1.8h) Z0j1w≤X0j,(0, j)∈A;w∈V\ {0}(1.8i) H X h=2 Zijhw ≤Xij,(i, j)∈A;i6= 0; w∈V\ {0}(1.8j) Como conclusión a este apartado, lo esperable es que para H= 2,3los modelos 1.3 y 1.4 sean los más rápidos en encontrar la solución óptima y para H≥4lo sea el modelo 1.8 o el modelo 1.1. En principio el modelo 1.1 dará mejores resultados que el modelo 1.8 cuanto mayor sea H[7]. 1.2. Formulaciones basadas en restricciones de MillerTucker-Zemlin Consideremos un conjunto de variables ui(i∈V)que especifican la posición del nodo i en la solución (considerando como origen el nodo raíz). Las restricciones de Miller-TuckerZemlin[25] son unas conocidas restricciones con forma: ui−uj+n∗xij <=n−1(1.9) Su principal función es la eliminación de subtours, es decir, evitan que aparezcan ciclos secundarios en la solución. Esto se entiende mejor en el problema al que se aplican estas restricciones originalmente: el TSP (Traveling Salesman Problem o Problema del Viajante). En el TSP se trata de minimizar el coste de la ruta que pasa por cada nodo a lo Andrés Bravo Núñez 8 Capítulo 1. Resolución Exacta 1.2. Formulaciones basadas en restricciones de MTZ sumo una vez. Sin estas restricciones, un optimizador podría encontrar una solución con dos rutas inconexas que en conjunto cumplan las restricciones de pasar por cada nodo una vez. En cuanto a nuestro problema, el HMST, podemos adaptar estás restricciones para evitar la existencia de ciclos. Para entender esto mejor podemos ejemplificarlo con la siguiente formulación: Modelo MTZ(Miller-Tucker-Zemlin)[16] minimizar X (i,j)∈A cijXij (1.10a) sujeto a X i∈V Xij = 1, j ∈V\ {0}(1.10b) nXij +ui≤uj+ (n−1), i, j ∈V\ {0}(1.10c) 1≤ui≤H, i ∈V\ {0}(1.10d) Xij ∈ {0,1},(i, j)∈A(1.10e) Las restricciones 1.10b hacen que solo un arco entre en cada nodo, exceptuando la raiz. Las restricciones 1.10c evitan la existencia de ciclos. Para observar esto basta con suponer que hay un ciclo y aplicando las restricciones en dicho ciclo llegaremos a una contradicción del tipo ui+ 1 ≤ui. Por último las restricciones 1.10d garantizan que los caminos de la raíz al resto de nodos contienen como máximo Harcos. Si nos fijamos en las restricciones 1.10c las variables uino tienen porque marcar de manera precisa la posición del nodo ien el camino. Imaginemos un problema con H= 3 y un camino con 2 nodos. No hace falta que los valores del las u sean 1 para el primer nodo y 2 para el segundo, también podrian ser 2 y 3 o 1 y 3 respectivamente. Lo importante es que las uicumplan lo siguiente: ui−uj≤(H−1) i, j ∈V\ {0}(1.11) Esta desigualdad es redundante con las restricciones 1.10d y puede integrarse en 1.10c para dar una nueva formulación: Modelo EMTZ(Extended Miller-Tucker-Zemlin)[16] minimizar X (i,j)∈A cijXij (1.12a) sujeto a X i∈V Xij = 1, j ∈V\ {0}(1.12b) HXij +ui≤uj+ (H−1), i, j ∈V\ {0}(1.12c) Xij ∈ {0,1},(i, j)∈A(1.12d) Andrés Bravo Núñez 9 Capítulo 1. Resolución Exacta 1.2. Formulaciones basadas en restricciones de MTZ Esta formulación 1.12, puede tener unas cotas más ajustadas con su relajación lineal que la formulación 1.10 ya que toda solución que cumpla 1.12c cumplirá 1.10c. Para demostrarlo basta con añadir (n−H)Xij a cada lado de 1.12c: (n−H)Xij +HXij +ui≤(n−H)Xij +uj+ (H−1) i, j ∈V\ {0}(1.13) que es equivalente a: nXij +ui≤(n−H)Xij +uj+ (H−1) i, j ∈V\ {0}(1.14) como Xij puede tomar únicamente los valores {0,1}el lado derecho de la anterior desigualdad cumple: (n−H)Xij +uj+(H−1) ≤(n−H)+uj+ (H−1) = uj+(n−1) i, j ∈V\ {0}(1.15) y sustitutendo de vuelta en 1.14: nXij +ui≤uj+ (n−1) i, j ∈V\ {0}(1.16) que equivale a las restricciones 1.10c del modelo MTZ 1.10. 1.2.1. Elevando las restricciones Para reforzar el modelo 1.12, es decir, que las cotas de sus relajaciones sean más ajustadas, necesitamos hacer uso de técnicas de elevamiento de restricciones [27][34]. El elevamiento, es una técnica por la cual, una restricción válida para un subconjunto de la región de soluciones, nos referiremos a ella como restricción semilla, es modificada para que su validez sea global. Habitualmente, la restricción semilla es derivada bajo la asunción de que ciertas variables están fijas. Posteriormente esta restricción es relajada hasta que sea globalmente válida. Intentaremos realizar una descripción más matemática aunque informal. Tenemos un conjunto de soluciones factibles a nuestro problema de programación entera S⊆ {0,1}n (n son el número de variables que componen la solución) y además sabemos que existen soluciones con la variable xa= 1 (si no sospecharamos esto no intentaríamos elevar las restricción) o en otras palabras S∩ {x:xa= 1} 6=∅. Ahora supongamos que tenemos una restricción de la forma: n X i=1;i6=a αixi≤β(1.17) Que es válida para S∩{x:xa= 0}aunque tambien es válida para S∩{x:xa= 1}y para Spuesto que simplemente no incluye xa. Pero como sabemos que S∩ {x:xa= 1} 6=∅ podemos pensar que existe un cierto hueco β−Pn i=1;i6=aαixique podemos ocupar con un nuevo término αaxa. Lo que planteamos es elevar la restricción 1.17 para que sea Andrés Bravo Núñez 10 Capítulo 1. Resolución Exacta 1.2. Formulaciones basadas en restricciones de MTZ válida en un espacio con una dimensión más (puesto que hemos añadido una variable). La restricción elevada tendrá la forma: n X i=1;i6=a αixi+αaxa≤β(1.18) Por último debemos hallar el valor del nuevo coeficiente αa. Siguiendo con la idea de aprovechar el hueco αavaldrá: αa=β−max{ n X i=1;i6=a αixi:x∈S, xa= 1}(1.19) Por lo tanto todo se reduce a resolver otro problema de programación entera lo cual es difícil. Sin embargo, estos problemas pueden ser fáciles de resolver (por su tamaño o por otros motivos) y aportar una ventaja al ajustar más la definición del problema al conjunto S. De vuelta al problema HMST y el modelo EMTZ 1.12 podemos aplicar esta idea para mejorar la formulación. Existen elevaciones de las restricciones de Miller-Tucker-Zemlin [10] que se han adapatado a nuestro problema [16].Las restricciones 1.12c puede elevarse a: (H−2)Xji +HXij +ui≤uj+ (H−1), i, j ∈V\ {0};H≥2(1.20) Donde H−2se sostiene de: αa= (H−1) −max{HXij +ui−uj, i, j ∈V\ {0};xji = 1}(1.21) Puesto que si xji = 1 entonces xij = 0 y además uj+1 = ui(Hdebe ser mayor o igual a 2) la solución a ese problema de maximización es 1 y por tanto αa= (H−2). Sustituyendo 1.12c por 1.20 obtenemos la nueva formulación: Modelo L1EMTZ(Lift-1 Extended Miller-Tucker-Zemlin)[16] minimizar X (i,j)∈A cijXij (1.22a) sujeto a X i∈V Xij = 1, j ∈V\ {0}(1.22b) (H−2)Xji +HXij +ui≤uj+ (H−1), i, j ∈V\ {0}(1.22c) Xij ∈ {0,1},(i, j)∈A(1.22d) Otra restricción para la que se ha propuesto un elevamiento es la siguiente: n X k=1;k6=i Xkj +HXij +ui≤uj+ (H−1) i, j ∈V\ {0}(1.23) Andrés Bravo Núñez 11 Capítulo 1. Resolución Exacta 1.2. Formulaciones basadas en restricciones de MTZ Xj∈V\ {0}X0j≤(H−1) −(H−2)w0l,(1.33u) XjXji +Xj∈V\ {0}Xij ≥1 + wic, i ∈V\ {0}(1.33v) XjXji +Xj∈V\ {0}Xij ≤(H−1) −(H−2)w0l, i ∈V\ {0}(1.33w) Xj∈V\ {0}X0j≥1−wil, i ∈V\ {0}(1.33x) Xij ≤wic, i, j ∈V\ {0}(1.33y) Xij +wil +wjl ≤2, j ∈V\ {0}(1.33z) Xi0= 0,(1.33aa) Xij +Xji ≤1, i < j (1.33ab) X j6=i Xij ≤H−1,(1.33ac) wic ∈ {0,1},(1.33ad) wil ∈ {0,1},(1.33ae) Andrés Bravo Núñez 18 Capítulo 1. Resolución Exacta 1.2. Formulaciones basadas en restricciones de MTZ Andrés Bravo Núñez 19 Capítulo 2 Heurísticas En el capítulo anterior se vieron diferentes formulaciones que nos permiten alcanzar la solución óptima del problema HMST. Sin embargo, ya que estamos ante un problema NP-Hard el tiempo que puede llevar solucionar problemas de una embergadura moderada (entendida como número de arcos) puede hacer esta opción impracticable. Además cabe la posibilidad de que por motivos económicos u de otra índole no se tenga acceso a un software de optimización y por tanto haya que recurrir a métodos heurísticos. La manera de enfrentar esta problemática es mediante el uso de métodos herísticos. Es decir utilizando algorítmos que nos permitan encontrar soluciones factibles que sean relativamente buenas. Se suelen diferenciar dos tipos de heuríticas: Heurísticas de Construcción: Construir paso a paso una solución factible siguiendo unas reglas. Herísticas de Mejora: Dada una solución factible inicial realizar pequeñas mejoras sucesivas hasta que no sea posible ninguna mejora. Habitualmente estas heurísticas se combinan de manera que existe una fase de construcción y una de mejora. Encontrar una solución factible para el problema HMST es trivial, basta con conectar todos los nodos directamente a la raíz. Por tanto las heurísticas desarrolladas pertenecen al grupo de las heurísticas de mejora. Mostraremos tres aproximaciones diferentes:(i) una heurística derivada e la heurística de Essau-Williams para el problema del mínimo arbol generador con capacidades (en el que se limíta el número máximo de nodos en un subárbol) [14],(ii) diferentes versiones de un algorítmo de segundo orden [14] y (iii) algorítmos de busqueda local en vecindarios derivados de un modelo de programación dinámica para el problema HMST [18]. 20 Capítulo 2. Heurísticas 2.1. Heurística de ahorros 2.1. Heurística de ahorros Vamos a utilizar una modificación de la heurística de ahorros de Esau-Williams [11]. Se comienza con una configuración de estrella (todos los nodos conectados directamente a la raíz). Se calcula el ahorro Sijw que se consigue al intercambiar un arco (w, 0) por otro (i, j)siendo Sijw =cw0−cij si lleva a una solución factible y Sijw =−∞ si no. Se realiza el intercambio de ahorro máximo y se vuelven a calcular los ahorros nuevamente. El algoritmo finaliza cuando no hay ahorros mayores a 0. Se puede ver el pseudocódigo del algorítmo en 1. Algorithm 1 HMST Esau-Williams [14] 1: arcos = set_configuracion_estrella(nodos,raiz) 2: loop 3: for w/arcos(w, 0) = 1 do 4: nodo1 =w 5: for i, j/arcos(i, j)=0 do 6: nodo2 = i 7: nodo3 = j 8: arcos(i,j) = 1 9: arcos(w,0) = 0 10: {H se refiere al número de saltos máximo permitido} 11: if esFactible(arcos,raiz,H) then 12: ahorros(i, j, w) = c(w, 0) −c(i, j) 13: end if 14: arcos(i,j) = 0 15: arcos(w,0) = 1 16: end for 17: end for 18: if max(ahorro)<= 0 then 19: break 20: end if 21: cambioi,cambioj,cambiow = indices_de(ahorro,max(ahorro)) 22: arcos(cambioi,cambioj) = 1 23: arcos(cambiow,0) = 0 24: resetear_ahorros 25: end loop 2.2. Algoritmos de segundo orden Los algorítmos de segundo orden son una clase de algorítmos que aplican una heurística base (e.g HMST Esau-Williams 1) iterativamente a versiones modificadas del problema. Andrés Bravo Núñez 21 Capítulo 2. Heurísticas 2.2. Algoritmos de segundo orden Estas modificaciones implican fijar parte de la solución, en el contexto del problema HMST se obliga la inclusión o exclusión ciertos arcos. En cada paso se prueban todas las modificaciones generadas por una regla y se fijan las modificaciones que llevan a la mejor solución. Este proceso se repite hasta que ninguna modificación mejora la mejor solución anterior. La idea es aumentar las posibilidades de econtrar una buena solución al aumentar el número de condiciones iniciales sobre las que se aplica la heurística base. Los algorítmos de segundo orden fueron propuestos inicialmente para el problema del arbol generador mínimo con capacidades(minimizar el coste del árbol generador con una restricción sobre la cantidad de nodos en los subárboles)[21] y posteriormente se adapto al HMST [14]. Procedemos a describir una versión general para este tipo de algorítmos. Sean S1 el conjunto de arcos a fijar y S2 el conjunto de arcos a inhibir en una modificación concreta. Tras una pasada del algorítmo de segundo orden, se fijaran las modificaciones que hayan dado la mejor solución, es decir, los elementos de S1 se incluyen en SP1 (con P de permante) y los elementos de S2 en SP2. HEUR(S1,S2,SP1,SP2) implica la ejecución de la heurística base sobre el problema modificado según los conjuntos S1, S2, SP1 y SP2 (fijandose los arcos en S1∪SP1e inhibiendose los incluidos en S2∪SP2). Podemos ver una versión en pseudocódigo del algoritmo en 2. En el contexto del problema HMST la manera de inhibir un arco es establecer su coste en infinito (o un coste lo suficientemente alto para que resulte prohibitivo incluirlo) y la manera de forzar su inclusión es darle un coste lo suficientemente bajo (si todos los costes son positivos 0 resultaría suficiente). Algunas definiciones concretas para los conjuntos S2 y SP2 son: Inhibición simple [14]. S2 contendrá en cada pasada cada uno de los arcos que pertenezcan a la solución actual y que no contengan la raíz. La inhibición que de mejor resultado pasará a formar parte de SP2. Con este esquema el bucle interior del algoritmo 2 realizará n (número de nodos del problema) pasadas. Inhibición pareada [14]. Igual que la inhibición simple pero considerando en S2 pares de arcos en vez de arcos individuales. Esto lleva a que el bucle interior 2 realize n2 pasadas. y en cuanto a S1 y SP1 tenemos: Inclusión limitada [14]. S1 contendrá en cada pasada el arco de menor coste incidente a cada nodo o el arco de menor coste incidente a cada tal que el otro extremo este más cerca de la raiz. La inclusión que lleve a la mejor solución se incluirá en SP1. El bucle interior realizará 2n pasadas como máximo. Andrés Bravo Núñez 22 Capítulo 2. Heurísticas 2.2. Algoritmos de segundo orden Inclusión general [14]. Se puede pensar que cualquier arco que no esté en la solución es candidato para estar en S1. Como la cantidad de arcos de este tipo es muy elevada solo se evaluan los z arcos de menor coste incidentes en cada nodo. El arco que lleve a la mejor solución es fijado en S1. Cabe destacar que si se fuerza la inclusión de arcos se necesita comprobar que estos puedan llevar a una solución factible. Es decir, que no existan ni ciclos ni caminos excesivamente largos. Algorithm 2 Algoritmo de segundo orden 1: S1 = ∅ 2: S2 = ∅ 3: SP1 = ∅ 4: SP2 = ∅ 5: solucion_actual = HEUR(S1,S2,SP1,SP2) 6: coste = COSTE(solucion_actual) 7: loop 8: flag = 0 9: {El número de iteraciones del bucle depende del número posible de modificaciones que podamos realizar con la regla que elijamos} 10: for i= 0, . . . do 11: modificar S1 y/o S2 12: solucion_prueba = HEUR(S1,S2,SP1,SP2) 13: if COSTE(solucion_prueba) <coste then 14: flag = 1 15: solucion_actual = solucion_prueba 16: coste = COSTE(solucion_actual) 17: A1 = S1 18: A2 = S2 19: end if 20: end for 21: if flag=0 then 22: break 23: end if 24: SP1 = SP1 ∪A1 25: SP2 = SP2 ∪A2 26: end loop Andrés Bravo Núñez 23 Capítulo 2. Heurísticas 2.3. Vecindarios basados en programación dinámica 2.3. Vecindarios basados en un modelo de programación dinámica 2.3.1. Representación de un árbol mediante el nivel de los vértices Una representación de algunas soluciones factibles (incluyendo la óptima) se puede realizar utilizando la definición del nivel de un vertice propuesta por Gruber et al. [20]. El nivel de un nodo se define como la máxima distancia, con respecto al número de arcos, que puede tener dicho nodo de la raiz. Si tenemos esta asignación podemos reconstruir el árbol generador al que pertenece. Sea n(i)el nivel del nodo i: Para cada nodo i∈V\ {0},(1) Determinar j∗tal que min{cij :n(j) = 0, . . . , n(i)−1}=cij∗ (2) Insertar el arco (i, j∗) (2.1) Esta manera de representar un árbol ya nos da una idea rudimentaria de un vecindario basado en cambiar el nivel de diferentes nodos. Para que tengamos una manera sistemática de definir un vecindario y recorrelo, necesitamos el modelo de programación dinámica. 2.3.2. Un modelo de programación dinámica para el problema HMST La programación dinámica es una técnica para resolver problemas que tengan subestructuras óptimas y subproblemas que se solapen [6]. Un problema tiene subestructuras óptimas si se puede obtener su solución óptima mediante soluciones óptimas de sus subproblemas. Un problema tiene supbroblemas que se solapan si es divisible en subproblemas que se repiten, es decir, si dividimos el problema en los subproblemas más pequeños posibles existirán muchas repeticiones. Un ejemplo clásico de este tipo de problemas es generar el n-ésimo término de la serie de Fibonacci. Lo que necesitamos para un modelo de programación dinámica es la solución óptima de los problemas más simples y alguna regla para generar la solución de problemas más grandes. En el caso de la secuencia de Fibonacci: fibonacci(n) =      0if n= 0 1if n= 1 fibonacci(n−1) + fibonacci(n−2) if n > 1 (2.2) Para el problema que nos ocupa es fácil comprobar que existe una subestructura óptima. Supongamos que conocemos la solución óptima de un problema HMST con máximo Andrés Bravo Núñez 24 Capítulo 2. Heurísticas 2.3. Vecindarios basados en programación dinámica número de saltos H. Si eliminamos los vértices con nivel H obtendremos la solución óptima del problema sin estos vértices y máximo número de saltos H-1. Necesitamos ser capaces de conocer el coste de añadir los vértices de nivel k a una solución con vértices con nivel máximo k-1. Sea Sklos vértices que tienen nivel k. El coste de añadir los vértices en Ska otro conjunto de vértices Sque no los contenga es: coste(Sk, S) = X i∈Sk ci(S),i, S 6=∅ coste(Sk,∅) = X i∈Sk c0,i, coste(∅, S) = 0 (2.3) Donde i(S)indica el nodo en Smás cercano al nodo ien Sk. Sea z(S, k)el coste del árbol óptimo construido con los vértices en Scon un número máximo de saltos k. Un estado queda definido por el conjunto de vértices Sy el número máximo de saltos k. Si estamos en un estado (S, k)queremos determinar Sktal que la suma de los costes de coste(Sk, S/setminusSkyz(S/setminusSk, k −1) sea minimo. Escrito de otra manera: z(S, ∅)=0, k = 1, . . . , n z(S, 1) = coste(S, ∅) = X i∈S c0,i, S ⊆V\ {0} z(S, k) = min{coste(Sk, S/setminusSk+z(S/setminusSk, k −1)}, k= 2, . . . , H, S ⊆V\ {0}, Sk⊆S (2.4) Este problema tiene una gran cantidad de estados y requiere un tiempo O(H3n)para resolver una instancia del problema HMST lo cual lo hace no apto para ser utilizado. Sin embargo podemos añadir restricciones a las transiciones entre estados que reduzcan los estados vecinos lo suficiente para que su exploración sea computacionalmente abordable. En concreto dos restricciones: 1. Restricción sobre el espacio de estados. Dado un entero d > 0y una solución inicial Sinicial que podemos particionar como {S1, . . . , SH}(cada elemento de la partición contiene los nodos en cada nivel) solo se consideraran los estados (S, k)tal que |S\ {S1∪ · · · ∪ Sk}| +|{S1∪ · · · ∪ Sk} \ S|<=d, para k= 1, . . . , H −1. Dicho en una manera más intuitiva: si existiera una pared entre cada nivel de los vértices solo podriamos pasar d vértices por cada pared. Andrés Bravo Núñez 25 Capítulo 2. Heurísticas 2.3. Vecindarios basados en programación dinámica 2. Restriccion sobre la transición de estados. Dada una solución inicial Sinicial que podemos particionar como {S1, . . . , SH}solo se restringen las transiciones desde un estado (S∗, k −1) a un estado (S, k)tal que Sneq{S1, . . . , Sk}. Sea N1yN1∗los vértices (el conjunto de los vértices no el número de los mismos) nuevos en Sy S∗respectivamente en relación a los que existen en {S1, . . . , Sk}y{S1, . . . , Sk−1}. Sea N2yN2∗los vértices que desaparecen en SyS∗frente a los que había en {S1, . . . , Sk}y{S1, . . . , Sk−1}. Solo se permiten las transiciones que cumplen al menos una de las condiciones siguientes: 1. S∗={S1, . . . , Sk−1} 2. N1 = N1∗yN2 = N2∗(2.5) Se intentará mostrar la explicación de estas restricciones utilizando para demostrar la validez/invalidez de la transición ilustrada en la figura 2.1. Figura 2.1: Ejemplo de una transición (adaptado de [18]) Si suponemos d= 1 las transiciones de la figura 2.1 cumplen la primera de las restricciones 1. Para k= 1 tenemos que el vértice rojo abandona el primer nivel es decir |S\S1|= 1 (aqui Sse refiere solo a los vértices originalmente en el nivel 1) y nada entre por tanto |S1\S|= 0. En el caso de k= 2 solo la bola verde abandona el conjunto de los niveles 1 y 2, es decir, |S\S1∪S2|= 1 los intercambios internos como el vértice rojo no afectan a la comprobación. Es fácil comprobar que para k= 3 también se cumple. Para comprobar la restricción sobre las transiciones 2, nos referiremos por Sia los elementos en el nivel ioriginalmente y por S∗ ia los elementos en el nivel itras los cambios. Empezamos por el estado (S∗ 1,1) que transiciona a ({S∗ 1∪S∗ 2},2). Lo primero que comprobamos es si se aplican las restricciones, como {S∗ 1∪S∗ 2} 6={S1∪S2}(ya que el vértice verde no está en {S∗ 1∪S∗ 2}) si que se aplican. La primera parte de la ecuación 2.5 no se cumple ya que {S∗ 1} 6={S∗ 1}(por el vértice rojo). La segunda parte 2.5 no se cumple tampoca ya que en el primer estado (S∗ 1,1) está saliendo el vértice rojo y en cambio en ({S∗ 1∪S∗ 2},2) es el verde, es decir no es el mismo vértice como obliga la restricción. Por tanto este intercambio no es posible con en estas restricciones lo cual implica que no existe una relación de vecindad entre la solución previa a los intercambios y la posterior a los mismos. Andrés Bravo Núñez 26 Capítulo 2. Heurísticas 2.3. Vecindarios basados en programación dinámica 2.3.3. Vecindarios Si definimos una clase de intercambios tambien tendríamos un vecindario de estados que podemos explorar en busca de mejores soluciones. En este trabajo vamos a abordar los desarrollados por Gouveia et al. [18] aunque no son los únicos que existen. El primer vecindario se conforma por los estados que distan del estado actual (recordemos que un estado es un reparto de los vértices en los diferentes niveles) por un movimiento simple. Definimos un movimiento simple por el cambio de nivel de un vértice. Este vecindario tiene tamaño O(nH). Se puede ver un ejemplo de este movimiento en la figura 2.2. Figura 2.2: Movimiento simple (adaptado de [18]) El segundo vecindario se conforma por los estados que difieren del estado actual por un intercambio. Un intercambio implica que dos vértices intercambian sus niveles. Este vecindario tiene tamaño O(n2). Se puede ver un ejemplo de este movimiento en la figura 2.3. Figura 2.3: Intercambio (adaptado de [18]) Por último podemos pensar en un vecindario en la que un estado es vecino si se puede llegar mediante un movimiento simple o un intercambio. Este vecindario tiene tamaño O(n2)aunque como es obvio es ligeramente más grande que el vecindario de intercambios. Andrés Bravo Núñez 27 Capítulo 3. Metaheurísticas 3.2. GRASP Andrés Bravo Núñez 34 Capítulo 4 Resultados Computacionales En este capítulo, se mostrarán los resultados obtenidos mediante el uso del ordenador tanto para los modelos exáctos como para los algoritmos heurísticos. El conjunto de datos que se ha utilizado pertenece a la OR-Library [5][4]. En concreto se han utilizado los datos pertenecientes al problema del mínimo árbol de Steiner. Estos datos contienen coordenadas de puntos en dos dimensiones. Se ha decidido que en principio toda conexión es posible y que los costes de las aristas sean las distancias euclideas entre los puntos. Los datos estan agrupados en archivos con problemas numerados con la misma cantidad de puntos como se indica en la tabla 4.1. archivo número de puntos archivo número de puntos estein10 10 estein60 60 estein20 20 estein70 70 estein30 30 estein80 80 estein40 40 estein90 90 estein50 50 estein100 100 Cuadro 4.1: Archivos en OR-Library para el problema del mínimo árbol de Steiner Debido a la gran cantidad de problemas posibles que se pueden generar con los datos (combinando el número del problema, el nodo raíz y la cantidad máxima de saltos H), se ha decidido escoger un subconjunto de problemas para probar las heurísticas. Este subconjunto esta indicado en la tabla 4.2. 35 Capítulo 4. Resultados Computacionales archivo problema raíz H archivo problema raíz H estein10.txt 3 3 2 estein50.txt 3 3 2 estein10.txt 3 3 3 estein50.txt 3 3 3 estein10.txt 3 3 4 estein50.txt 3 3 4 estein10.txt 3 3 5 estein50.txt 3 3 5 estein10.txt 3 8 2 estein50.txt 3 8 2 estein10.txt 3 8 3 estein50.txt 3 8 3 estein10.txt 3 8 4 estein50.txt 3 8 4 estein10.txt 3 8 5 estein50.txt 3 8 5 estein10.txt 4 3 2 estein50.txt 4 3 2 estein10.txt 4 3 3 estein50.txt 4 3 3 estein10.txt 4 3 4 estein50.txt 4 3 4 estein10.txt 4 3 5 estein50.txt 4 3 5 estein10.txt 4 8 2 estein50.txt 4 8 2 estein10.txt 4 8 3 estein50.txt 4 8 3 estein10.txt 4 8 4 estein50.txt 4 8 4 estein10.txt 4 8 5 estein50.txt 4 8 5 estein20.txt 3 3 2 estein60.txt 3 3 2 estein20.txt 3 3 3 estein60.txt 3 3 2 estein20.txt 3 3 4 estein60.txt 3 3 2 estein20.txt 3 3 5 estein60.txt 3 3 2 estein20.txt 3 8 2 estein60.txt 3 3 2 estein20.txt 3 8 3 estein60.txt 3 3 2 estein20.txt 3 8 4 estein60.txt 3 3 2 estein20.txt 3 8 5 estein60.txt 3 3 2 estein20.txt 4 3 2 estein60.txt 3 3 2 estein20.txt 4 3 3 estein60.txt 3 3 2 estein20.txt 4 3 4 estein60.txt 3 3 2 estein20.txt 4 3 5 estein60.txt 3 3 2 estein20.txt 4 8 2 estein60.txt 3 3 2 estein20.txt 4 8 3 estein60.txt 3 3 2 estein20.txt 4 8 4 estein60.txt 3 3 2 estein20.txt 4 8 5 estein60.txt 3 3 2 estein30.txt 3 3 2 estein70.txt 3 3 2 estein30.txt 3 3 3 estein70.txt 3 3 2 estein30.txt 3 3 4 estein70.txt 3 3 2 estein30.txt 3 3 5 estein70.txt 3 3 2 estein30.txt 3 8 2 estein70.txt 3 3 2 estein30.txt 3 8 3 estein70.txt 3 3 2 estein30.txt 3 8 4 estein70.txt 3 3 2 estein30.txt 3 8 5 estein70.txt 3 3 2 estein30.txt 4 3 2 estein70.txt 3 3 2 Andrés Bravo Núñez 36 Capítulo 4. Resultados Computacionales estein30.txt 4 3 3 estein70.txt 3 3 2 estein30.txt 4 3 4 estein70.txt 3 3 2 estein30.txt 4 3 5 estein70.txt 3 3 2 estein30.txt 4 8 2 estein70.txt 3 3 2 estein30.txt 4 8 3 estein70.txt 3 3 2 estein30.txt 4 8 4 estein70.txt 3 3 2 estein30.txt 4 8 5 estein70.txt 3 3 2 estein40.txt 3 3 2 estein80.txt 3 3 2 estein40.txt 3 3 3 estein80.txt 3 3 2 estein40.txt 3 3 4 estein80.txt 3 3 2 estein40.txt 3 3 5 estein80.txt 3 3 2 estein40.txt 3 8 2 estein80.txt 3 3 2 estein40.txt 3 8 3 estein80.txt 3 3 2 estein40.txt 3 8 4 estein80.txt 3 3 2 estein40.txt 3 8 5 estein80.txt 3 3 2 estein40.txt 4 3 2 estein80.txt 3 3 2 estein40.txt 4 3 3 estein80.txt 3 3 2 estein40.txt 4 3 4 estein80.txt 3 3 2 estein40.txt 4 3 5 estein80.txt 3 3 2 estein40.txt 4 8 2 estein80.txt 3 3 2 estein40.txt 4 8 3 estein80.txt 3 3 2 estein40.txt 4 8 4 estein80.txt 3 3 2 estein40.txt 4 8 5 estein80.txt 3 3 2 Cuadro 4.2: Problemas seleccionados para probar los modelos exactos y las heurísticas Por la gran cantidad de problemas que se han realizado se mostrarán en el texto principal solo el primer cuarto de problemas corresponidiente a cada archivo. Estos problemas siempre son el tercer problema del archivo indicado y su raíz es el vértice 3. El resto se podrán encontrar en el apéndice. Cuando los tiempos de ejecución han sido demasiado largos se ha decidido no realizar las pruebas en los archivos con más grandes. Normalmete con los mayores a 40 puntos aunque hay excepciones. Con el fin de reducir los tamaños de los problemas, y por tantos los tiempos de los diferentes algoritmos, se ha aplicado un procedimiento de eliminación de arcos [15]. Si cij > c0jentonces la solución óptima no utiliza el arco (i, j)y si cij =c0j(i6= 0), entonces hay una solución óptima sin el arco (i, j). Es decir se pueden eliminar las aristas que cumplan cij >=c0j. Esta eliminación provoca que para una misma cantidad de puntos si la raíz es un punto más centrado se eliminen más arcos que si fuera un punto más periférico [9]. Para tener en cuenta este hecho en la tabla A.6 del apéndice se mostrará Andrés Bravo Núñez 37 Capítulo 4. Resultados Computacionales 4.1. Resultados de los modelos exactos una medida de centralidad del nodo raíz de cada problema. La cercanía de un nodo se define como la inversa de la suma de los caminos más cortos al resto de nodos 4.1. C(x)=( 1 Pv∈Vd(x, v)) donde d(x, v)es la distancia directa entre x y v (4.1) En nuestro caso hemos utilizado la cercanía del nodo raiz pero usando los caminos directos entre la misma medida del nodo que de mayor resultado 4.2. Cmodificada(x) = 1 Pv∈Vd(x, v) donde d(x, v)es la distancia directa entre x y v (4.2) Por último se ha restado el mínimo y se ha divido por el rango para que la medida tome valores entre 0 y 1. De esta manera si el valor es 1 entonces el nodo tiene la máxima cercanía modificada de la red y si es 0 la menor. 4.1. Resultados de los modelos exactos Para probar los modelos exactos se ha limitado el tiempo de resolución a 300 segundos, es decir que si no se encuentra la solución óptima en ese tiempo el software devuelve la mejor solución que ha encontrado. Además para acortar el tiempo de espera solo se han resuelto los problemas con un tamaño menor a 40 puntos. Los resultados de los modelos basados en flujos multi-producto se pueden ver en la tabla 4.3 y A.1. Podemos observar que todos los problemas se resuelven de manera óptima salvo algún caso de los problemas con 40 puntos. Entre estos cuatro modelos el MCF parace ser el que da mejores resultados aunque el MCF* tiene mejores tiempos cuando H es 2 o 3. Esto está acorde a lo que se predijo en el capítulo 1.1. Andrés Bravo Núñez 38 Capítulo 4. Resultados Computacionales 4.1. Resultados de los modelos exactos MCF HopMCF MCF* H=2 MCF* H=3 p raíz H sol t(s) sol t(s) sol t(s) sol t(s) estein10.txt 3 3 2 2.703 0.007 2.703 0.007 2.703 0.004 —– —– 3 3 3 2.417 0.01 2.417 0.053 —– —– 2.417 0.019 3 3 4 2.33 0.009 2.33 0.098 —– —– —– —– 3 3 5 2.33 0.009 2.33 0.129 —– —– —– —– estein20.txt 3 3 2 3.482 0.121 3.482 0.031 3.482 0.006 —– —– 3 3 3 2.938 0.486 2.938 1.6 —– —– 2.938 0.483 3 3 4 2.715 0.153 2.715 2.36 —– —– —– —– 3 3 5 2.631 0.196 2.631 3.149 —– —– —– —– estein30.txt 3 3 2 6.498 2.566 6.498 0.103 6.498 0.011 —– —– 3 3 3 4.815 13.017 4.815 5.081 —– —– 4.815 2.992 3 3 4 4.344 5.65 4.344 9.139 —– —– —– —– 3 3 5 4.133 89.024 4.133 27.064 —– —– —– —– estein40.txt 3 3 2 6.923 3.335 6.923 0.575 6.923 0.015 —– —– 3 3 3 5.801 39.977 5.801 126.602 —– —– 5.801 15.863 3 3 4 5.252 45.947 5.696 299.815 —– —– —– —– 3 3 5 4.888 41.892 4.888 86.834 —– —– —– —– Cuadro 4.3: Soluciones obtenidas con los modelos MCF 1.1, HopMCF 1.8 y MCF* 1.3 1.4 En cuanto a los modelos que incluyen restricciones de Miller-Tucker-Zemlin los más básicos tienen sus resultados en las tablas 4.4 y A.2. Modelo MTZ Modelo EMTZ problema raiz H solución tiempo solución tiempo estein10.txt 3 3 2 2.703 0.007 2.703 0.037 3 3 3 2.417 0.01 2.417 0.035 3 3 4 2.33 0.007 2.33 0.004 3 3 5 2.33 0.008 2.33 0.005 estein20.txt 3 3 2 3.482 0.025 3.482 1.51 3 3 3 2.938 0.333 2.938 7.1 3 3 4 2.715 1.599 2.715 3.765 3 3 5 2.631 0.619 2.631 4.037 Andrés Bravo Núñez 39 Capítulo 4. Resultados Computacionales 4.1. Resultados de los modelos exactos estein30.txt 3 3 2 6.498 0.08 6.654 299.828 3 3 3 4.815 299.525 4.895 299.629 3 3 4 4.344 299.855 4.434 299.59 3 3 5 4.177 299.755 4.264 299.547 estein40.txt 3 3 2 6.923 0.05 7.053 299.702 3 3 3 5.801 95.639 6.008 299.686 3 3 4 5.254 299.135 5.404 299.686 3 3 5 4.888 27.303 4.888 299.67 Cuadro 4.4: Soluciones obtenidas con los modelos MTZ 1.10 y EMTZ 1.12 Parece que el modelo MTZ tiene un mejor comportamiento que el modelo EMTZ, aún así, no superan el comportamiento del modelo MCF. Los resultados para los modelos con elevaciones se encuentran en las tablas 4.5 y A.3. Modelo L1EMTZ Modelo L2EMTZ problema raiz H solución tiempo solución tiempo estein10.txt 3 3 2 2.703 0.087 2.341 0.007 3 3 3 2.417 0.032 2.417 0.016 3 3 4 2.33 0.006 2.33 0.006 3 3 5 2.33 0.005 2.33 0.006 estein20.txt 3 3 2 3.482 6.089 2.304 0.038 3 3 3 2.938 23.829 2.938 1.229 3 3 4 2.715 8.964 2.715 1.611 3 3 5 2.631 5.619 2.631 2.381 estein30.txt 3 3 2 6.654 299.965 6.498 3.651 3 3 3 4.857 299.49 4.815 44.088 3 3 4 4.47 300.005 4.409 299.125 3 3 5 4.271 299.44 4.139 299.425 estein40.txt 3 3 2 7.053 299.665 6.923 4.845 3 3 3 5.999 299.63 5.84 300.145 3 3 4 5.352 299.661 5.32 299.46 3 3 5 4.888 110.717 4.888 136.226 Cuadro 4.5: Soluciones obtenidas con los modelos L1EMTZ 1.22 y L2EMTZ 1.26 Ambos modelos superan al modelo del que derivan (el EMTZ) pero no al modelo de Andrés Bravo Núñez 40 Capítulo 4. Resultados Computacionales 4.1. Resultados de los modelos exactos flujos MCF. Los resultados de los modelos con mejoras topológicas están en las tablas 4.6 y A.4. MTZ/ITEF IMTZ/ITEF REL-M p raíz H solución tiempo solución tiempo solución tiempo estein10.txt 3 3 2 2.703 0.006 2.703 0.01 2.703 0.004 3 3 3 2.417 0.005 2.417 0.007 2.417 0.004 3 3 4 2.33 0.004 2.33 0.004 2.33 0.004 3 3 5 2.33 0.004 2.33 0.005 2.33 0.004 estein20.txt 3 3 2 3.482 0.044 3.482 0.014 3.482 0.013 3 3 3 2.938 0.761 2.938 0.365 2.938 0.549 3 3 4 2.715 0.91 2.715 2.25 2.715 0.442 3 3 5 2.631 0.838 2.631 0.932 2.631 0.916 estein30.txt 3 3 2 6.498 0.115 6.498 0.062 6.498 0.029 3 3 3 4.815 299.946 4.815 133.949 4.815 1.357 3 3 4 4.344 299.764 4.344 299.331 4.344 14.669 3 3 5 4.211 299.42 4.133 300.041 4.133 53.253 estein40.txt 3 3 2 6.923 0.141 6.923 0.1 6.923 0.025 3 3 3 5.801 162.265 5.801 43.198 5.801 13.337 3 3 4 5.27 299.983 5.306 299.666 5.252 38.877 3 3 5 4.888 78.516 4.892 299.181 4.888 38.421 Cuadro 4.6: Soluciones obtenidas con los modelos MTZ/ITEF 1.27, IMTZ/ITEF 1.30 y REL-M 1.31 Los modelos se comportan de manera similar entre ellos aunque el que da mejores resultados es el REL-M. Esto coincide con los resultados de la fuente [3]. A pesar de ello el modelo MCF parece ser el mejor hasta el momento. Finalmente los resultados para los modelos que usan las ideas de Sherali y Driscoll se encuentran en las tablas 4.7 y A.5.Ambos modelos dan buenos resultados pero a pesar de ello no son mejores que el modelo de flujos MCF. De todos los modelos propuestos aquellos que parecen resolver los problemas de una manera más rápida son el MCF y el MCF* para H=2 o H=3. A pesar de que en este caso los modelos exactos den buenos resultados las cosas pueden cambiar para tamaños de problema más grandes para lo que se requeriria la aplicación de algun método heurístico o metaheurístico. Andrés Bravo Núñez 41 Capítulo 4. Resultados Computacionales 4.2. Resultados de las Heurísticas HMST-SD HMST-SD/ITEF problema raiz H solución tiempo solución tiempo estein10.txt 3 3 2 2.703 0.006 2.703 0.005 3 3 3 2.417 0.012 2.417 0.008 3 3 4 2.33 0.007 2.33 0.005 3 3 5 2.33 0.007 2.33 0.005 estein20.txt 3 3 2 3.482 0.013 3.482 0.02 3 3 3 2.938 1.801 2.938 1.471 3 3 4 2.715 2.747 2.715 1.293 3 3 5 2.631 1.833 2.631 1.79 estein30.txt 3 3 2 6.498 0.038 6.498 0.072 3 3 3 4.815 4.378 4.815 4.87 3 3 4 4.344 78.109 4.344 104.717 3 3 5 4.133 148.076 4.152 299.28 estein40.txt 3 3 2 6.923 0.015 6.923 0.063 3 3 3 5.801 4.516 5.801 10.828 3 3 4 5.252 61.218 5.252 63.672 3 3 5 4.888 41.453 4.888 99.718 Cuadro 4.7: Soluciones obtenidas con los modelos HMST-SD 1.32 y HMST-SD/ITEF 1.33 4.2. Resultados de las Heurísticas En primer lugar comprobamos los resultados que se obtienen con la heurística de ahorros 1. archivo problema raiz H solución tiempo estein10.txt 3 3 2 2.794 0.149 estein10.txt 3 3 3 2.561 0.010 estein10.txt 3 3 4 2.561 0.010 estein10.txt 3 3 5 2.561 0.009 estein20.txt 3 3 2 4.232 0.264 estein20.txt 3 3 3 3.260 0.323 estein20.txt 3 3 4 2.844 0.324 estein20.txt 3 3 5 2.750 0.330 estein20.txt 3 8 2 4.594 0.193 estein30.txt 3 3 2 8.723 1.540 estein30.txt 3 3 3 5.555 1.744 Andrés Bravo Núñez 42 Capítulo 4. Resultados Computacionales 4.2. Resultados de las Heurísticas estein30.txt 3 3 4 4.696 1.790 estein30.txt 3 3 5 4.323 1.866 estein40.txt 3 3 2 7.785 3.702 estein40.txt 3 3 3 6.144 4.410 estein40.txt 3 3 4 5.478 4.673 estein40.txt 3 3 5 5.289 4.508 estein50.txt 3 3 2 12.380 11.141 estein50.txt 3 3 3 7.909 13.915 estein50.txt 3 3 4 7.096 14.931 estein50.txt 3 3 5 6.316 15.424 estein60.txt 3 3 2 15.564 24.450 estein60.txt 3 3 3 9.257 31.494 estein60.txt 3 3 4 7.913 34.068 estein60.txt 3 3 5 7.028 36.266 estein70.txt 3 3 2 17.388 39.710 estein70.txt 3 3 3 10.522 51.737 estein70.txt 3 3 4 7.668 57.647 estein70.txt 3 3 5 7.226 58.183 estein80.txt 3 3 2 17.185 73.249 estein80.txt 3 3 3 9.898 101.079 estein80.txt 3 3 4 8.755 96.262 estein80.txt 3 3 5 8.147 94.073 Cuadro 4.8: Soluciones obtenidas con la heurística de ahorros EW En las tablas 4.8 y A.6 podemos comprobar que la heurística de ahorros consigue soluciones iniciales de una calidad alta (en los casos que hemos comprobado relativamente cercanas al óptimo) aunque invierte una buena cantidad de tiempo. Esto puede resultar un problema para las heurísticas de búsqueda que se basan en aplicar heurísticas de manera repetida como los algorítmos de segundo orden 2 descritos en el apartado 2.2. Por este motivo se ha decidido aplicar las diferentes versiones de algoritmos de segundo orden únicamente a los problemas con 40 vértices o menos. Los resultados se pueden ver en las tablas 4.9 y A.7. Inhib. simple Inhib. pareada Incl. limitada Incl. general p raiz H sol t sol t sol t sol t estein10.txt 3 3 2 2.794 0.077 2.794 0.435 2.794 0.151 2.794 0.175 3 3 3 2.561 0.068 2.561 0.775 2.561 0.137 2.561 0.115 3 3 4 2.561 0.054 2.561 0.754 2.561 0.13 2.561 0.118 3 3 5 2.561 0.054 2.561 0.804 2.561 0.166 2.561 0.151 Andrés Bravo Núñez 43 Capítulo 4. Resultados Computacionales 4.3. Resultados de las Metaheurísticas Andrés Bravo Núñez 50 Capítulo 5 Conclusiones En este documento se ha realizado un repaso a los diferentes métodos que existen para resolver el problema del mínimo árbol generador con restricciones de salto (HMST, Hop-constrained minimun spanning tree problem). Se ha mostrado que los métodos de resolución exacta pueden resolver problemas de un tamaño moderado (con un número de nodos <= 40) en un tiempo razonable (inferior a 5 minutos). Con las pruebas realizadas los modelos más rápidos parecen ser los modelos de flujo multi-producto aunque esto no asegura que con instancias reales vayan a serlo. Sin embargo los métodos de resolución exacta tienen su límite. No solo porque para instancias grandes sus tiempos son prohibitivos si no que ademas el software que los aplica también puede tener un coste prohibitivo. Por ello es necesario realizar una evaluación de los métodos heurísticos y metaheurísticos disponibles. En el caso de las heurísticas nos econtramos con una heurística de construcción que da unos resultados bastante buenos. En cuanto a los métodos de búsqueda local aquellos basados en la repetición de heurísticas de construcción tardan tiempos muy elevados y en cambio los que aprovechan una solución ya existente proporcionan mejores resultados. Los mejores métodos para nuestro problema han resultado ser los métodos metaheurísticos que hemos probado: Simulated Annealing y GRASP. Siendo GRASP el mejor entre ambos aunque a cambio de invertir más tiempo. A pesar de que se ha realizado un esfuerzo para crea un documento completo existen muchas heurísticas y modelos exactos que no han sido evaluados y podrían dar buenos resultados. Otro camino que se puede seguir resulta de hibridar diferentes metaheurísticas. Si alguien se enfrentara a este problema en la vida real las recomendaciones variarian según el tamaño del problema y el tiempo disponible para resolverlo. Si el tamaño del problema es pequeño los métodos exactos pueden ser una buena opción. En otro caso si hay suficiente tiempo recomendaría aplicar GRASP y si no Simulated Annealing. 51 Capítulo 5. Conclusiones Andrés Bravo Núñez 52 Apéndices Apéndice A Tablas de resultados extendidas A.1. Modelos Exactos A.2. Resultados de los modelos exactos A.2.1. Modelos de flujo MCF HopMCF MCF∗H= 2 MCF∗H= 3 p raíz H sol t sol t sol t sol t estein10.txt 3 3 2 2.703 0.007 2.703 0.007 2.703 0.004 —– —– 3 3 3 2.417 0.01 2.417 0.053 —– —– 2.417 0.019 3 3 4 2.33 0.009 2.33 0.098 —– —– —– —– 3 3 5 2.33 0.009 2.33 0.129 —– —– —– —– 3 8 2 2.687 0.007 2.687 0.007 2.687 0.004 —– —– 3 8 3 2.42 0.01 2.42 0.054 —– —– 2.42 0.02 3 8 4 2.384 0.009 2.384 0.109 —– —– —– —– 3 8 5 2.365 0.015 2.365 0.128 —– —– —– —– 4 3 2 2.152 0.008 2.152 0.007 2.152 0.004 —– —– 4 3 3 1.944 0.021 1.944 0.054 —– —– 1.944 0.02 4 3 4 1.834 0.01 1.834 0.101 —– —– —– —– 4 3 5 1.826 0.01 1.826 0.126 —– —– —– —– 4 8 2 2.726 0.012 2.726 0.006 2.726 0.004 —– —– 4 8 3 2.216 0.069 2.216 0.074 —– —– 2.216 0.034 4 8 4 2.034 0.04 2.034 0.12 —– —– —– —– 4 8 5 1.929 0.021 1.929 0.133 —– —– —– —– estein20.txt 54 Apéndice A. Tablas de resultados extendidas A.2. Resultados de los modelos exactos 3 3 2 3.482 0.121 3.482 0.031 3.482 0.006 —– —– 3 3 3 2.938 0.486 2.938 1.6 —– —– 2.938 0.483 3 3 4 2.715 0.153 2.715 2.36 —– —– —– —– 3 3 5 2.631 0.196 2.631 3.149 —– —– —– —– 3 8 2 3.558 0.103 3.558 0.032 3.558 0.006 —– —– 3 8 3 2.923 0.371 2.923 1.742 —– —– 2.923 0.531 3 8 4 2.659 0.101 2.659 2.347 —– —– —– —– 3 8 5 2.586 0.101 2.586 2.997 —– —– —– —– 4 3 2 3.741 0.272 3.741 0.033 3.741 0.006 —– —– 4 3 3 3.029 2.068 3.029 1.867 —– —– 3.029 2.559 4 3 4 2.787 1.669 2.787 2.82 —– —– —– —– 4 3 5 2.651 0.404 2.651 3.501 —– —– —– —– 4 8 2 4.088 0.533 4.088 0.031 4.088 0.006 —– —– 4 8 3 3.112 1.378 3.112 1.933 —– —– 3.112 0.961 4 8 4 2.815 3.255 2.815 2.633 —– —– —– —– 4 8 5 2.682 1.156 2.682 5.366 —– —– —– —– estein30.txt 3 3 2 6.498 2.566 6.498 0.103 6.498 0.011 —– —– 3 3 3 4.815 13.017 4.815 5.081 —– —– 4.815 2.992 3 3 4 4.344 5.65 4.344 9.139 —– —– —– —– 3 3 5 4.133 89.024 4.133 27.064 —– —– —– —– 3 8 2 5.601 2.15 5.601 0.105 5.601 0.01 —– —– 3 8 3 4.485 2.22 4.485 4.835 —– —– 4.485 2.383 3 8 4 4.108 2.465 4.108 7.862 —– —– —– —– 3 8 5 3.958 3.565 3.958 23.516 —– —– —– —– 4 3 2 6.587 5.86 6.587 0.116 6.587 0.012 —– —– 4 3 3 5.059 35.313 5.059 7.471 —– —– 5.059 3.938 4 3 4 4.547 26.148 4.547 13.991 —– —– —– —– 4 3 5 4.301 41.172 4.301 54.158 —– —– —– —– 4 8 2 6.193 3.935 6.193 0.25 6.193 0.011 —– —– 4 8 3 4.814 18.259 4.814 11.264 —– —– 4.814 3.272 4 8 4 4.394 15.269 4.394 19.899 —– —– —– —– 4 8 5 4.214 21.878 4.214 55.801 —– —– —– —– estein40.txt 3 3 2 6.923 3.335 6.923 0.575 6.923 0.015 —– —– 3 3 3 5.801 39.977 5.801 126.602 —– —– 5.801 15.863 3 3 4 5.252 45.947 5.696 299.815 —– —– —– —– 3 3 5 4.888 41.892 4.888 86.834 —– —– —– —– 3 8 2 7.671 7.555 7.671 0.485 7.671 0.021 —– —– 3 8 3 6.24 192.172 6.831 299.4 —– —– 6.24 128.091 3 8 4 5.421 116.287 5.421 69.855 —– —– —– —– 3 8 5 5.112 18.819 5.112 84.62 —– —– —– —– Andrés Bravo Núñez 55 Apéndice A. Tablas de resultados extendidas A.2. Resultados de los modelos exactos 4 3 2 7.058 37.047 7.058 0.565 7.058 0.022 —– —– 4 3 3 5.37 130.947 5.37 57.601 —– —– 5.37 17.784 4 3 4 4.855 251.053 4.855 115.872 —– —– —– —– 4 3 5 4.748 300.93 5.009 300.025 —– —– —– —– 4 8 2 6.572 15.844 6.572 0.545 6.572 0.017 —– —– 4 8 3 5.159 67.156 5.159 39.293 —– —– 5.159 11.629 4 8 4 4.73 86.734 4.73 62.221 —– —– —– —– 4 8 5 4.536 299.785 4.814 299.435 —– —– —– —– Cuadro A.1: Soluciones obtenidas con los modelos con los modelos MCF, HopMCF y MCF∗ A.2.2. Modelos con restricciones MTZ Modelo MTZ Modelo EMTZ problema raiz H solución tiempo solución tiempo estein10.txt 3 3 2 2.703 0.007 2.703 0.037 3 3 3 2.417 0.01 2.417 0.035 3 3 4 2.33 0.007 2.33 0.004 3 3 5 2.33 0.008 2.33 0.005 3 8 2 2.687 0.005 2.687 0.056 3 8 3 2.42 0.007 2.42 0.033 3 8 4 2.384 0.007 2.384 0.013 3 8 5 2.365 0.009 2.365 0.009 4 3 2 2.152 0.015 2.152 0.035 4 3 3 1.944 0.017 1.944 0.033 4 3 4 1.834 0.025 1.834 0.029 4 3 5 1.826 0.038 1.826 0.076 4 8 2 2.726 0.01 2.726 0.072 4 8 3 2.216 0.041 2.216 0.082 4 8 4 2.034 0.059 2.034 0.053 4 8 5 1.929 0.052 1.929 0.053 estein20.txt 3 3 2 3.482 0.025 3.482 1.51 3 3 3 2.938 0.333 2.938 7.1 3 3 4 2.715 1.599 2.715 3.765 3 3 5 2.631 0.619 2.631 4.037 3 8 2 3.558 0.017 3.558 1.665 3 8 3 2.923 0.475 2.923 5.785 3 8 4 2.659 0.42 2.659 0.715 3 8 5 2.586 0.517 2.586 1.398 4 3 2 3.741 0.035 3.741 4.515 4 3 3 3.029 0.533 3.029 8.143 Andrés Bravo Núñez 56 Apéndice A. Tablas de resultados extendidas A.2. Resultados de los modelos exactos 4 3 4 2.787 0.957 2.787 6.554 4 3 5 2.651 0.653 2.651 1.547 4 8 2 4.088 0.034 4.088 37.183 4 8 3 3.112 1.456 3.112 40.364 4 8 4 2.815 4.494 2.815 36.422 4 8 5 2.682 4.24 2.682 15.738 estein30.txt 3 3 2 6.498 0.08 6.654 299.828 3 3 3 4.815 299.525 4.895 299.629 3 3 4 4.344 299.855 4.434 299.59 3 3 5 4.177 299.755 4.264 299.547 3 8 2 5.601 0.035 5.601 112.964 3 8 3 4.485 2.98 4.485 299.652 3 8 4 4.108 6.63 4.108 193.171 3 8 5 3.958 7.559 3.958 106.593 4 3 2 6.587 0.085 6.753 299.936 4 3 3 5.073 299.105 5.163 299.717 4 3 4 4.547 299.78 4.551 299.701 4 3 5 4.301 299.771 4.394 299.452 4 8 2 6.193 0.045 6.293 299.639 4 8 3 4.814 120.717 4.848 299.702 4 8 4 4.394 195.092 4.475 299.702 4 8 5 4.214 108.447 4.214 299.593 estein40.txt 3 3 2 6.923 0.05 7.053 299.702 3 3 3 5.801 95.639 6.008 299.686 3 3 4 5.254 299.135 5.404 299.686 3 3 5 4.888 27.303 4.888 299.67 3 8 2 7.671 0.07 8.238 299.811 3 8 3 6.29 300.01 6.56 299.702 3 8 4 5.569 299.691 5.612 299.639 3 8 5 5.241 299.46 5.259 299.608 4 3 2 7.058 0.105 7.809 299.686 4 3 3 5.373 299.265 5.719 299.639 4 3 4 4.931 299.665 5.084 299.577 4 3 5 4.818 299.615 4.678 299.577 4 8 2 6.572 0.07 7.117 299.577 4 8 3 5.191 299.225 5.319 299.733 4 8 4 4.845 299.615 4.994 299.561 4 8 5 4.562 299.53 4.618 299.498 Cuadro A.2: Soluciones obtenidas con los modelos MTZ y EMTZ Andrés Bravo Núñez 57 Apéndice A. Tablas de resultados extendidas A.2. Resultados de los modelos exactos A.2.3. Modelos con restricciones elevadas Modelo L1EMTZ Modelo L2EMTZ problema raiz H solución tiempo solución tiempo estein10.txt 3 3 2 2.703 0.087 2.341 0.007 3 3 3 2.417 0.032 2.417 0.016 3 3 4 2.33 0.006 2.33 0.006 3 3 5 2.33 0.005 2.33 0.006 3 8 2 2.687 0.197 2.362 0.016 3 8 3 2.42 0.17 2.42 0.042 3 8 4 2.384 0.027 2.384 0.023 3 8 5 2.365 0.012 2.365 0.024 4 3 2 2.152 0.082 1.752 0.043 4 3 3 1.944 0.304 1.944 0.053 4 3 4 1.834 0.043 1.834 0.052 4 3 5 1.826 0.078 1.826 0.048 4 8 2 2.726 0.54 1.566 0.005 4 8 3 2.216 1.414 2.216 0.238 4 8 4 2.034 0.825 2.034 0.232 4 8 5 1.929 1.191 1.929 0.107 estein20.txt 3 3 2 3.482 6.089 2.304 0.038 3 3 3 2.938 23.829 2.938 1.229 3 3 4 2.715 8.964 2.715 1.611 3 3 5 2.631 5.619 2.631 2.381 3 8 2 3.558 6.225 2.304 0.106 3 8 3 2.923 14.269 2.923 0.702 3 8 4 2.659 5.069 2.659 1.582 3 8 5 2.586 1.94 2.586 1.41 4 3 2 3.741 12.474 2.364 0.082 4 3 3 3.029 25.958 3.029 1.98 4 3 4 2.787 7.855 2.787 1.721 4 3 5 2.651 3.175 2.651 0.857 4 8 2 4.088 114.048 2.492 0.133 4 8 3 3.112 174.938 3.112 5.744 4 8 4 2.815 38.942 2.815 4.558 4 8 5 2.682 13.399 2.682 6.202 estein30.txt 3 3 2 6.654 299.965 3.842 3.651 3 3 3 4.857 299.49 4.815 44.088 3 3 4 4.47 300.005 4.409 299.125 3 3 5 4.271 299.44 4.139 299.425 Andrés Bravo Núñez 58 Apéndice A. Tablas de resultados extendidas A.2. Resultados de los modelos exactos 3 8 2 5.601 299.33 3.647 3.485 3 8 3 4.493 299.496 4.485 9.004 3 8 4 4.108 207.022 4.108 20.684 3 8 5 3.958 108.732 3.958 32.628 4 3 2 6.753 299.29 3.911 1.035 4 3 3 5.238 299.83 5.059 25.358 4 3 4 4.575 299.585 4.584 299.885 4 3 5 4.41 299.445 4.31 299.276 4 8 2 6.326 299.315 3.901 2.805 4 8 3 4.909 299.867 4.814 75.925 4 8 4 4.432 299.762 4.406 300 4 8 5 4.225 299.397 4.214 226.18 estein40.txt 3 3 2 7.053 299.665 4.401 4.845 3 3 3 5.999 299.63 5.84 300.145 3 3 4 5.352 299.661 5.32 299.46 3 3 5 4.888 110.717 4.888 136.226 3 8 2 8.238 299.91 4.322 0.13 3 8 3 6.639 299.685 6.384 299.76 3 8 4 5.708 299.601 5.576 299.61 3 8 5 5.227 299.778 5.151 299.48 4 3 2 7.809 300.155 4.11 0.415 4 3 3 5.793 299.495 5.423 300.125 4 3 4 5.114 299.55 4.895 299.34 4 3 5 4.671 299.89 4.811 299.415 4 8 2 7.386 299.371 4.285 3.275 4 8 3 5.415 299.48 5.473 299.075 4 8 4 4.99 299.741 4.869 299.576 4 8 5 4.744 299.496 4.741 299.576 Cuadro A.3: Soluciones obtenidas con los modelos L1EMTZ y L2EMTZ A.2.4. Modelos con restricciones topológicas mejoradas MTZ/ITEF IMTZ/ITEF REL-M p raíz H solución tiempo solución tiempo solución tiempo estein10.txt 3 3 2 2.703 0.006 2.703 0.01 2.703 0.004 3 3 3 2.417 0.005 2.417 0.007 2.417 0.004 3 3 4 2.33 0.004 2.33 0.004 2.33 0.004 3 3 5 2.33 0.004 2.33 0.005 2.33 0.004 3 8 2 2.687 0.007 2.687 0.004 2.687 0.005 Andrés Bravo Núñez 59 Apéndice A. Tablas de resultados extendidas A.3. Heurísticas estein70.txt 4 8 5 7.598 55.111 0.418 estein80.txt 3 3 2 17.185 73.249 0.636 estein80.txt 3 3 3 9.898 101.079 0.636 estein80.txt 3 3 4 8.755 96.262 0.636 estein80.txt 3 3 5 8.147 94.073 0.636 estein80.txt 3 8 2 17.846 66.973 0.630 estein80.txt 3 8 3 10.293 93.106 0.630 estein80.txt 3 8 4 8.962 99.351 0.630 estein80.txt 3 8 5 8.117 92.665 0.630 estein80.txt 4 3 2 15.840 65.126 0.678 estein80.txt 4 3 3 9.454 90.533 0.680 estein80.txt 4 3 4 8.122 91.802 0.680 estein80.txt 4 3 5 7.575 93.931 0.680 estein80.txt 4 8 2 17.590 77.820 0.372 estein80.txt 4 8 3 11.828 93.903 0.372 estein80.txt 4 8 4 8.730 101.754 0.372 estein80.txt 4 8 5 8.056 104.619 0.372 Cuadro A.6: Soluciones obtenidas con la heurística de ahorros de EW A.3.2. Algoritmos de segundo orden Inhib. simple Inhib. pareada Incl. limitada Incl. general p raiz H sol t sol t sol t sol t estein10.txt 3 3 2 2.794 0.077 2.794 0.435 2.794 0.151 2.794 0.175 3 3 3 2.561 0.068 2.561 0.775 2.561 0.137 2.561 0.115 3 3 4 2.561 0.054 2.561 0.754 2.561 0.13 2.561 0.118 3 3 5 2.561 0.054 2.561 0.804 2.561 0.166 2.561 0.151 3 8 2 2.748 0.178 2.748 1.439 2.748 0.341 2.748 0.395 3 8 3 2.516 0.093 2.516 1.599 2.516 0.165 2.516 0.15 3 8 4 2.481 0.074 2.481 1.576 2.481 0.185 2.481 0.22 3 8 5 2.481 0.135 2.481 1.569 2.481 0.176 2.481 0.164 4 3 2 2.29 0.19 2.29 1.919 2.222 0.489 2.222 0.661 4 3 3 2.113 0.304 2.113 3.027 2.207 0.145 2.038 0.707 4 3 4 2.095 0.093 1.997 3.989 2.03 0.335 1.929 0.854 4 3 5 1.922 0.227 1.922 4.172 1.927 0.186 1.92 0.556 4 8 2 2.726 0.164 2.726 3.656 2.726 0.297 2.726 0.584 4 8 3 2.406 0.396 2.406 12.595 2.359 0.789 2.359 1.466 4 8 4 2.267 0.372 2.106 11.168 2.334 0.669 2.202 1.312 4 8 5 2.037 0.367 2.037 13.579 2.078 0.4 2.037 1.287 estein20.txt Andrés Bravo Núñez 66 Apéndice A. Tablas de resultados extendidas A.3. Heurísticas 3 3 2 4.196 5.24 4.196 292.91 4.128 32.796 3.942 46.809 3 3 3 3.185 11.916 3.185 710.892 3.185 27.136 3.185 35.257 3 3 4 2.834 8.695 2.834 658.621 2.842 19.369 2.844 18.555 3 3 5 2.75 5.095 2.75 436.188 2.75 9.421 2.75 19.027 3 8 2 3.706 12.798 3.653 575.362 4.08 22.841 3.927 41.841 3 8 3 3.074 13.066 3.01 888.366 3.108 21.652 3.074 50.04 3 8 4 2.659 9.253 2.659 786.274 2.66 22.793 2.659 36.649 3 8 5 2.586 9.466 2.586 717.321 2.6 23.051 2.586 36.247 4 3 2 4.105 9.307 3.943 667.356 4.178 12.971 4.079 50.099 4 3 3 3.078 22.925 3.078 1071.65 3.102 37.515 3.043 67.338 4 3 4 2.834 11.015 2.812 1326.059 2.835 18.992 2.835 46.073 4 3 5 2.663 12.208 2.663 854.877 2.68 10.253 2.663 48.104 4 8 2 4.298 23.701 4.293 1420.233 4.39 53.023 4.537 42.483 4 8 3 3.417 17.27 3.209 2796.237 3.269 57.387 3.383 112.072 4 8 4 2.844 27.414 2.844 1341.345 3.137 11.438 3.041 59.04 4 8 5 2.682 13.635 2.682 915.486 2.682 22.954 2.682 60.39 estein30.txt 3 3 2 7.06 179.743 7.06 8888.381 7.362 313.846 7.333 617.896 3 3 3 4.908 128.159 4.815 11902.568 4.908 357.712 4.908 585.789 3 3 4 4.462 176.668 4.424 13224.491 4.604 210.2 4.58 583.558 3 3 5 4.214 200.428 4.214 14970.705 4.323 134.978 4.251 612.124 3 8 2 5.885 121.526 5.83 8263.928 5.885 463.989 5.902 399.382 3 8 3 4.485 139.785 —– —– 4.485 636.093 4.485 842.206 3 8 4 4.135 142.732 —– —– 4.168 172.367 4.168 347.631 3 8 5 3.958 148.905 —– —– 4.014 255.723 4.007 557.931 4 3 2 7.118 116.931 —– —– 7.735 334.606 7.289 780.021 4 3 3 5.293 147.356 —– —– 5.321 477.618 5.31 583.693 4 3 4 4.808 40.504 —– —– 4.808 128.694 4.776 406.251 4 3 5 4.473 122.089 —– —– 4.41 278.249 4.476 399.801 4 8 2 6.444 122.83 —– —– 6.426 601.184 6.322 947.214 4 8 3 4.865 62.131 —– —– 4.82 130.482 4.82 319.836 4 8 4 4.537 71.041 —– —– 4.561 269.264 4.493 334.915 4 8 5 4.223 75.552 —– —– 4.253 197.249 4.251 546.678 estein40.txt 3 3 2 7.27 465.09 —– —– 7.39 1177.95 7.249 2680.158 3 3 3 5.944 590.438 —– —– 5.937 2151.278 5.967 2531.725 3 3 4 5.373 371.862 —– —– 5.373 1155.617 5.444 1241.656 3 3 5 5.052 643.573 —– —– 5.134 1426.866 5.024 3103.015 3 8 2 8.406 763.42 —– —– 8.574 1809.719 8.736 3600.817 3 8 3 6.368 1150.813 —– —– 6.371 3009.947 6.581 2204.802 3 8 4 5.681 592.834 —– —– 5.692 1669.016 5.801 2386.245 3 8 5 5.218 638.753 —– —– 5.305 2196.148 5.355 2418.307 Andrés Bravo Núñez 67 Apéndice A. Tablas de resultados extendidas A.3. Heurísticas 4 3 2 7.594 526.519 —– —– 8.215 1832.205 8.286 1054.125 4 3 3 5.949 559.558 —– —– 5.967 2733.495 5.969 1296.702 4 3 4 5.648 284.685 —– —– 5.511 1678.076 5.417 3228.537 4 3 5 5.039 629.654 —– —– 5.267 1726.569 5.052 1984.876 4 8 2 6.706 1161.175 —– —– 6.876 2925.949 6.695 4242.579 4 8 3 5.201 954.45 —– —– 5.432 1130.477 5.262 5833.209 4 8 4 4.789 1170.29 —– —– 4.852 1616.106 4.856 4425.28 4 8 5 4.607 168.077 —– —– 4.55 989.558 4.55 4074.715 Cuadro A.7: Soluciones obtenidas con los algoritmos de segundo orden A.3.3. Vecindarios basados en un modelo de programación dinámica Mov. simple Intercambio Ambos p raíz H solución tiempo solución tiempo solución tiempo estein10.txt 3 3 2 2.703 0.088 (0.193) 2.794 0.099 (0.15) 2.703 0.079 (0.138) 3 3 3 2.465 0.004 (0.011) 2.561 0.003 (0.015) 2.465 0.008 (0.009) 3 3 4 2.465 0.01 (0.019) 2.561 0.003 (0.01) 2.465 0.009 (0.009) 3 3 5 2.465 0.014 (0.025) 2.561 0.004 (0.01) 2.465 0.011 (0.01) 3 8 2 2.691 0.002 (0.017) 2.717 0.007 (0.01) 2.687 0.008 (0.011) 3 8 3 2.42 0.005 (0.021) 2.485 0.008 (0.014) 2.42 0.006 (0.018) 3 8 4 2.384 0.005 (0.02) 2.449 0.009 (0.013) 2.384 0.009 (0.011) 3 8 5 2.384 0.01 (0.021) 2.449 0.008 (0.068) 2.384 0.01 (0.012) 4 3 2 2.221 0.003 (0.021) 2.222 0.008 (0.011) 2.152 0.021 (0.022) 4 3 3 2.084 0.005 (0.014) 2.207 0.003 (0.012) 1.969 0.033 (0.011) 4 3 4 2.026 0.004 (0.023) 2.03 0.022 (0.018) 1.961 0.027 (0.024) 4 3 5 1.857 0.006 (0.025) 1.922 0.01 (0.056) 1.853 0.03 (0.013) 4 8 2 2.726 0.001 (0.029) 2.726 0.003 (0.026) 2.726 0.004 (0.018) 4 8 3 2.451 0.001 (0.022) 2.406 0.007 (0.022) 2.406 0.011 (0.024) Andrés Bravo Núñez 68 Apéndice A. Tablas de resultados extendidas A.3. Heurísticas 4 8 4 2.294 0.004 (0.021) 2.438 0.004 (0.02) 2.147 0.029 (0.02) 4 8 5 2.057 0.006 (0.038) 2.037 0.011 (0.022) 2.011 0.024 (0.022) estein20.txt 3 3 2 3.557 0.015 (0.262) 3.833 0.244 (0.285) 3.482 0.078 (0.256) 3 3 3 3.143 0.039 (0.314) 3.241 0.159 (0.458) 3.073 0.178 (0.283) 3 3 4 2.725 0.059 (0.329) 2.844 0.069 (0.298) 2.725 0.15 (0.48) 3 3 5 2.631 0.055 (0.321) 2.75 0.077 (0.363) 2.631 0.157 (0.341) 3 8 2 3.617 0.019 (0.241) 4.07 0.171 (0.209) 3.558 0.099 (0.201) 3 8 3 3.079 0.017 (0.299) 3.079 0.218 (0.314) 3.079 0.067 (0.276) 3 8 4 2.686 0.014 (0.339) 2.686 0.078 (0.323) 2.686 0.073 (0.306) 3 8 5 2.674 0.031 (0.329) 2.674 0.139 (0.344) 2.674 0.139 (0.347) 4 3 2 3.832 0.021 (0.284) 4.259 0.159 (0.264) 3.741 0.088 (0.262) 4 3 3 3.167 0.03 (0.37) 3.288 0.209 (0.359) 3.029 0.297 (0.353) 4 3 4 2.831 0.074 (0.381) 2.835 0.242 (0.391) 2.831 0.164 (0.365) 4 3 5 2.676 0.062 (0.424) 2.68 0.092 (0.377) 2.676 0.154 (0.391) 4 8 2 4.242 0.014 (0.311) 4.652 0.358 (0.311) 4.088 0.208 (0.29) 4 8 3 3.373 0.026 (0.41) 3.375 0.423 (0.403) 3.296 0.295 (0.432) 4 8 4 3.063 0.045 (0.421) 3.036 0.349 (0.436) 3.063 0.105 (0.412) 4 8 5 2.873 0.041 (0.428) 2.786 0.182 (0.406) 2.786 0.204 (0.406) estein30.txt 3 3 2 6.678 0.054 (1.416) 7.579 0.925 (1.42) 6.59 0.603 (1.339) 3 3 3 5.07 0.109 (1.863) 5.206 1.62 (1.943) 4.908 0.932 (1.828) 3 3 4 4.696 0.056 (1.885) 4.604 0.669 (1.904) 4.604 0.723 (1.851) 3 3 5 4.25 0.152 (1.911) 4.323 0.404 (1.9) 4.232 0.778 (1.893) Andrés Bravo Núñez 69 Apéndice A. Tablas de resultados extendidas A.3. Heurísticas 3 8 2 5.643 0.041 (1.215) 5.966 0.69 (1.283) 5.635 0.334 (1.214) 3 8 3 4.687 0.042 (2.075) 4.643 0.812 (1.578) 4.643 0.833 (1.79) 3 8 4 4.242 0.083 (1.851) 4.21 0.615 (1.785) 4.21 0.625 (1.827) 3 8 5 4.053 0.121 (1.639) 4.053 0.725 (1.623) 4.053 0.45 (1.621) 4 3 2 6.746 0.076 (1.315) 7.259 1.375 (1.329) 6.699 0.307 (1.304) 4 3 3 5.387 0.078 (1.708) 5.392 1.334 (1.695) 5.286 0.966 (1.644) 4 3 4 4.794 0.118 (1.818) 4.808 0.33 (1.831) 4.779 0.673 (1.84) 4 3 5 4.509 0.082 (1.838) 4.509 0.461 (1.768) 4.509 0.425 (1.808) 4 8 2 6.345 0.081 (1.213) 6.613 0.745 (1.178) 6.193 0.557 (1.177) 4 8 3 4.82 0.152 (1.563) 5.036 0.587 (1.594) 4.82 0.344 (1.796) 4 8 4 4.628 0.078 (1.651) 4.628 0.621 (1.712) 4.628 0.381 (1.622) 4 8 5 4.373 0.085 (1.873) 4.373 0.374 (1.7) 4.373 0.371 (1.76) estein40.txt 3 3 2 6.923 0.116 (3.898) 7.218 2.173 (4.013) 6.923 0.447 (3.918) 3 3 3 6.048 0.175 (4.836) 6.094 2.912 (4.472) 6.045 1.647 (4.53) 3 3 4 5.431 0.238 (4.677) 5.455 1.831 (4.533) 5.407 3.45 (4.774) 3 3 5 5.243 0.327 (4.897) 5.287 2.028 (4.603) 5.239 3.496 (4.582) 3 8 2 7.936 0.208 (4.065) 8.595 1.911 (3.899) 7.671 1.614 (4.295) 3 8 3 6.585 0.17 (5.217) 6.451 5.201 (5.105) 6.542 4.157 (5.268) 3 8 4 5.769 0.743 (7.928) 5.806 2.721 (5.256) 5.716 2.57 (5.546) 3 8 5 5.468 0.64 (5.844) 5.378 5.261 (5.569) 5.398 4.168 (5.927) 4 3 2 7.133 0.343 (4.559) 7.284 3.249 (4.24) 7.078 1.264 (4.429) 4 3 3 5.591 0.564 (5.158) 5.776 2.805 (5.127) 5.591 1.255 (5.523) Andrés Bravo Núñez 70 Apéndice A. Tablas de resultados extendidas A.3. Heurísticas 4 3 4 5.408 0.319 (5.319) 5.288 9.825 (5.335) 5.009 7.949 (5.82) 4 3 5 5.365 0.477 (5.403) 5.008 10.292 (5.547) 4.903 4.588 (5.648) 4 8 2 6.64 0.145 (4.394) 6.793 2.793 (4.41) 6.574 1.331 (4.504) 4 8 3 5.257 0.415 (5.292) 5.407 2.149 (5.271) 5.205 3.333 (5.354) 4 8 4 4.916 0.123 (5.333) 4.871 2.523 (5.373) 4.862 2.077 (5.689) 4 8 5 4.553 0.313 (5.321) 4.499 6.131 (5.52) 4.486 2.727 (5.602) estein50.txt 3 3 2 9.424 0.644 (11.166) 10.475 9.382 (11.253) 9.31 3.259 (11.755) 3 3 3 7.228 0.894 (14.03) 7.442 21.487 (14.11) 7.179 9.266 (17.547) 3 3 4 6.697 1.765 (14.915) 6.75 14.422 (14.852) 6.456 19.909 (15.666) 3 3 5 6.27 0.88 (15.825) 6.249 6.916 (15.443) 6.239 5.851 (16.004) 3 8 2 9.553 0.548 (12.617) 10.841 10.178 (10.321) 9.415 3.528 (10.363) 3 8 3 7.184 0.931 (14.473) 7.253 16.482 (13.734) 7.039 10.684 (13.698) 3 8 4 6.726 1.106 (16.077) 6.784 6.26 (14.405) 6.716 5.403 (14.607) 3 8 5 6.234 1.807 (15.76) 6.075 13.804 (14.98) 5.937 25.55 (15.767) 4 3 2 8.735 0.722 (11.021) 10.412 10.934 (10.155) 8.681 1.786 (10.182) 4 3 3 7.129 1.059 (14.128) 7.127 13.039 (13.646) 6.783 10.843 (13.844) 4 3 4 6.389 0.992 (15.393) 6.231 16.457 (14.66) 6.197 17.743 (15.47) 4 3 5 5.909 1.035 (14.65) 5.973 11.751 (14.474) 5.896 6.391 (14.777) 4 8 2 8.368 0.613 (9.005) 9.514 14.241 (8.824) 8.125 2.913 (9.139) 4 8 3 6.588 1.474 (12.256) 6.759 17.661 (11.842) 6.43 9.676 (11.85) 4 8 4 5.822 1.987 (12.366) 6.001 10.709 (12.297) 5.778 8.453 (12.199) 4 8 5 5.569 1.161 (13.534) 5.493 26.167 (12.797) 5.293 16.319 (12.843) Andrés Bravo Núñez 71 Apéndice A. Tablas de resultados extendidas A.3. Heurísticas estein60.txt 3 3 2 11.072 1.014 (24.45) 13.331 28.937 (23.484) 10.744 11.478 (23.412) 3 3 3 8.263 1.643 (32.189) 8.408 44.596 (30.188) 7.995 13.794 (30.428) 3 3 4 7.332 2.538 (35.298) 7.372 73.022 (33.519) 6.991 29.82 (33.626) 3 3 5 6.905 0.891 (34.823) 6.892 14.212 (32.809) 6.62 17.829 (32.744) 3 8 2 9.441 0.986 (19.09) 10.075 22.082 (18.553) 9.198 12.308 (19.075) 3 8 3 7.53 0.892 (24.499) 7.441 30.28 (23.298) 7.371 28.539 (24.18) 3 8 4 6.768 0.625 (24.911) 6.773 8.464 (24.585) 6.722 9.302 (24.664) 3 8 5 6.109 0.859 (26.123) 6.083 18.664 (26.028) 6.083 15.706 (26.165) 4 3 2 10.853 1.456 (24.193) 12.107 27.522 (24.593) 10.623 5.082 (24.448) 4 3 3 7.769 1.381 (31.229) 7.812 21.006 (30.935) 7.667 15.961 (30.941) 4 3 4 7.318 1.011 (36.174) 7.132 58.579 (31.338) 7.073 46.138 (31.451) 4 3 5 6.582 1.677 (34.988) 6.546 47.252 (32.106) 6.566 16.598 (32.387) 4 8 2 10.555 0.915 (30.763) 12.006 20.354 (21.758) 10.376 12.36 (21.688) 4 8 3 7.52 2.395 (29.764) 7.73 44.044 (28.453) 7.423 28.03 (28.297) 4 8 4 6.781 3.074 (31.521) 6.858 47.103 (29.297) 6.641 21.256 (29.441) 4 8 5 6.163 3.128 (30.504) 6.208 47.364 (29.555) 6.126 30.202 (29.717) estein70.txt 3 3 2 11.7 2.231 (47.152) 13.997 56.347 (39.74) 11.658 10.318 (40.003) 3 3 3 8.48 4.693 (54.768) 9.143 118.809 (52.098) 8.289 45.014 (52.61) 3 3 4 7.579 2.351 (60.326) 7.532 37.05 (57.516) 7.532 41.867 (57.917) 3 3 5 7.108 1.437 (61.602) 7.077 51.653 (58.029) 7.077 45.262 (58.238) 3 8 2 10.471 2.049 (39.112) 11.649 42.376 (38.35) 10.164 22.064 (38.276) Andrés Bravo Núñez 72 Apéndice A. Tablas de resultados extendidas A.3. Heurísticas 3 8 3 8.217 1.955 (49.67) 8.001 79.94 (49.715) 7.807 58.716 (50.203) 3 8 4 7.294 3.405 (63.285) 7.291 83.315 (50.764) 6.923 84.504 (51.082) 3 8 5 6.751 2.725 (55.894) 6.671 81.35 (53.297) 6.671 49.122 (54.951) 4 3 2 12.302 2.542 (41.716) 13.744 53.056 (41.866) 11.842 19.478 (42.27) 4 3 3 8.912 2.979 (54.48) 9.147 69.769 (54.983) 8.824 44.937 (54.773) 4 3 4 7.827 3.732 (58.811) 7.867 94.952 (57.48) 7.573 95.095 (58.72) 4 3 5 7.249 4.28 (60.627) 7.356 47.077 (62.219) 7.239 22.506 (68.496) 4 8 2 12.027 1.874 (39.231) 13.837 62.797 (39.16) 11.819 13.594 (39.085) 4 8 3 9.027 2.005 (51.245) 8.996 61.169 (52.802) 8.865 32.272 (51.24) 4 8 4 7.935 4.718 (51.671) 8.203 87.003 (51.822) 7.823 28.129 (55.898) 4 8 5 7.376 4.553 (54.831) 7.359 61.087 (54.309) 7.32 40.832 (54.646) estein80.txt 3 3 2 12.309 3.46 (67.567) 13.593 111.768 (69.195) 11.986 29.032 (65.798) 3 3 3 9.418 3.09 (91.039) 9.281 149.724 (86.785) 9.207 105.776 (87.477) 3 3 4 8.216 10.305 (103.238) 8.014 216.074 (91.318) 7.893 126.901 (92.313) 3 3 5 8.103 2.842 (94.591) 8.014 148.326 (93.138) 8.008 98.941 (93.875) 3 8 2 12.161 3.56 (64.775) 14.705 89.06 (64.011) 12.027 24.141 (64.497) 3 8 3 9.151 3.72 (88.768) 9.255 133.154 (87.826) 8.988 53.763 (88.119) 3 8 4 8.63 4.127 (91.114) 8.508 249.467 (90.968) 8.408 126.023 (90.954) 3 8 5 7.732 6.206 (93.516) 7.796 111.09 (94.433) 7.719 67.338 (93.448) 4 3 2 11.382 3.365 (63.863) 13.371 107.332 (77.912) 11.11 36.188 (64.509) 4 3 3 8.575 5.464 (91.6) 8.741 108.814 (91.315) 8.41 52.87 (90.735) 4 3 4 7.674 4.769 (91.76) 7.736 76.168 (92.44) 7.65 81.44 (101.658) Andrés Bravo Núñez 73 Apéndice A. Tablas de resultados extendidas A.4. Metaheurísticas 4 3 5 7.184 6.455 (93.482) 7.269 57.064 (94.254) 7.043 66.42 (94.577) 4 8 2 12.433 2.553 (84.381) 14.722 114.545 (76.657) 12.101 33.809 (77.444) 4 8 3 9.34 6.194 (90.348) 10.078 267.286 (94.18) 8.913 110.927 (91.267) 4 8 4 8.419 3.64 (101.176) 8.257 157.318 (106.832) 8.145 127 (101.307) 4 8 5 7.6 6.013 (104.378) 7.457 152.043 (109.584) 7.443 82.128 (117.054) Cuadro A.8: Soluciones obtenidas con los vecindarios basados en un modelo de programación dinámica A.4. Metaheurísticas A.4.1. Simulated Annealing problema raiz H solución tiempo estein10.txt 3 3 2 2.703 28.226 (0.281) 3 3 3 2.485 27.805 (0.02) 3 3 4 2.485 30.03 (0.017) 3 3 5 2.457 31.005 (0.019) 3 8 2 2.691 25.548 (0.012) 3 8 3 2.49 29.058 (0.023) 3 8 4 2.384 29.786 (0.022) 3 8 5 2.384 30.039 (0.022) 4 3 2 2.153 26.28 (0.023) 4 3 3 2.153 30.031 (0.021) 4 3 4 2.153 31.207 (0.025) 4 3 5 1.864 30.303 (0.025) Andrés Bravo Núñez 74 Apéndice A. Tablas de resultados extendidas A.4. Metaheurísticas 4 8 2 2.835 20.887 (0.034) 4 8 3 2.289 25.78 (0.043) 4 8 4 2.22 28.368 (0.037) 4 8 5 2.261 29.841 (0.04) estein20.txt 3 3 2 3.578 53.665 (0.495) 3 3 3 3.122 59.621 (0.595) 3 3 4 2.725 63.263 (0.6) 3 3 5 2.715 64.045 (0.649) 3 8 2 3.558 55.801 (0.368) 3 8 3 3.075 61.468 (0.538) 3 8 4 2.688 61.825 (0.576) 3 8 5 2.713 65.166 (0.579) 4 3 2 3.741 52.712 (0.425) 4 3 3 3.159 58.067 (0.577) 4 3 4 2.937 60.726 (0.617) 4 3 5 2.753 62.129 (0.617) 4 8 2 4.098 51.972 (0.539) 4 8 3 3.308 57.805 (0.808) 4 8 4 2.861 59.714 (0.835) 4 8 5 2.872 64.989 (0.863) estein30.txt Andrés Bravo Núñez 75 Apéndice A. Tablas de resultados extendidas A.4. Metaheurísticas 4 8 5 4.223 64.326 4.22 114.691 estein40.txt 3 3 2 6.923 95.624 6.923 189.595 3 3 3 5.832 173.803 5.815 202.096 3 3 4 5.365 188.782 5.356 186.392 3 3 5 5.146 169.919 5.018 192.047 3 8 2 7.671 113.516 7.671 113.248 3 8 3 6.284 181.188 6.286 173.984 3 8 4 5.608 207.232 5.517 206.953 3 8 5 5.182 225.347 5.254 223.886 4 3 2 7.058 96.574 7.058 103.099 4 3 3 5.37 175.799 5.374 173.709 4 3 4 4.872 223.054 4.874 218.524 4 3 5 4.657 215.838 4.656 239.461 4 8 2 6.572 115.242 6.572 111.673 4 8 3 5.179 177.705 5.159 184.368 4 8 4 4.789 188.855 4.791 212.113 4 8 5 4.486 183.312 4.486 204.774 estein50.txt 3 3 2 9.181 313.094 9.181 334.978 3 3 3 7.021 553.313 7.023 495.187 3 3 4 6.374 628.686 6.342 525.594 3 3 5 6.036 620.198 5.984 527.441 3 8 2 9.343 295.25 9.343 253.349 3 8 3 6.954 534.053 6.954 483.705 3 8 4 6.243 557.458 6.226 481.755 3 8 5 5.912 565.708 5.908 494.036 4 3 2 8.681 273.877 8.681 244.041 4 3 3 6.759 462.782 6.673 434.43 4 3 4 5.973 584.17 6.015 531.58 4 3 5 5.687 526.519 5.607 513.091 4 8 2 8.114 241.47 8.098 219.416 4 8 3 6.271 436.928 6.271 407.962 4 8 4 5.758 528.721 5.719 456.348 4 8 5 5.279 506.807 5.293 454.898 estein60.txt 3 3 2 10.744 727.454 10.744 619.865 3 3 3 7.963 1045.591 7.871 1158.104 3 3 4 6.921 1368.802 6.826 1350.078 3 3 5 6.41 1314.271 6.41 1480.899 3 8 2 9.163 606.112 9.163 620.577 3 8 3 7.161 1265.547 7.15 1348.005 3 8 4 6.419 1100.761 6.366 1147.966 Andrés Bravo Núñez 82 Apéndice A. Tablas de resultados extendidas A.4. Metaheurísticas 3 8 5 5.984 1120.965 6.004 1145.276 4 3 2 10.623 640.185 10.623 615.615 4 3 3 7.664 1120.826 7.661 1251.491 4 3 4 6.796 1408.968 6.624 1473.604 4 3 5 6.284 1352.41 6.3 1563.407 4 8 2 10.376 675.998 10.376 620.784 4 8 3 7.212 1201.393 7.212 1335.666 4 8 4 6.332 1351.29 6.438 1353.985 4 8 5 6.017 1556.585 6.005 1493.665 estein70.txt 3 3 2 11.456 1118.269 11.456 1129.148 3 3 3 8.16 2441.529 8.089 2266.131 3 3 4 7.236 2281.714 7.178 2839.532 3 3 5 6.882 2656.255 6.881 2735.298 3 8 2 10.164 1366.837 10.164 1344.093 3 8 3 7.771 2166.116 7.715 2379.553 3 8 4 6.857 2506.184 6.82 2535.715 3 8 5 6.508 3148.967 6.412 2447.359 4 3 2 11.842 1785.087 11.842 1235.727 4 3 3 8.616 3266.683 8.624 2377.69 4 3 4 7.517 3738.849 7.548 2644.483 4 3 5 7.054 2707.656 7.124 3917.296 4 8 2 11.819 1459.597 11.819 1990.376 4 8 3 8.623 2881.471 8.613 3484.131 4 8 4 7.599 3932.883 7.718 4334.386 4 8 5 7.179 4212.583 7.213 3227.992 Cuadro A.10: Soluciones obtenidas con GRASP Andrés Bravo Núñez 83 Bibliografía [1] Warren P. Adams y Hanif D. Sherali. «A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems». En: SIAM Journal on Discrete Math (1990). [2] Ibrahim Akgün. «New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll’s tightened Miller-Tucker-Zemlin constraints». En: Computers and Operations Research. 2011. doi:10.1016/j.cor.2010.05.003. [3] Ibrahim Akgün y Barbaros Ç Tansel. «New formulations of the Hop-Constrained Minimum Spanning Tree problem via Miller-Tucker-Zemlin constraints». En: European Journal of Operational Research (2011). issn: 03772217. doi:10.1016/j. ejor.2011.01.051. [4] J. E. B Easley. «Or-library: Distributing test problems by electronic mail». En: Journal of the Operational Research Society (1990). issn: 14769360. doi:10.1057/ jors.1990.166. [5] J.E. Beasly. OR-Library. 2005. [6] Thomas H. Cormen y col. Introduction to Algorithms, Third Edition. 2009. isbn: 9780262033848. doi:10.1163/9789004256064_hao_introduction. arXiv: 2010(ret. 29.4.2010). [7] Geir Dahl. «The 2-hop spanning tree problem». En: Operations Research Letters (1998). issn: 01676377. doi:10.1016/S0167-6377(98)00029-7. [8] Geir Dahl, Njål Foldnes y Luis Gouveia. «A note on hop-constrained walk polytopes». En: Operations Research Letters (2004). issn: 01676377. doi:10.1016/j. orl.2003.10.008. [9] Geir Dahl, Luis Gouveia y C Requejo. «On Formulations and Methods for the Hop-Constrained Minimum Spanning Tree Problem». En: 2006, págs. 493-515. doi: 10.1007/978-0-387-30165-5_19. [10] Martin Desrochers y Gilbert Laporte. «Improvements and extensions to the MillerTucker-Zemlin subtour elimination constraints». En: Operations Research Letters (1991). issn: 01676377. doi:10.1016/0167-6377(91)90083-2. 84 Bibliografía Bibliografía [11] L. R. Esau y K. C. Williams. «On teleprocessing system design, Part II: A method for approximating the optimal network». En: IBM Systems Journal (1966). issn: 0018-8670. doi:10.1147/sj.53.0142. [12] Thomas A. Feo y Mauricio G C Resende. «A probabilistic heuristic for a computationally difficult set covering problem». En: Operations Research Letters (1989). issn: 01676377. doi:10.1016/0167-6377(89)90002-3. [13] Thomas A. Feo y Mauricio G.C. Resende. «Greedy Randomized Adaptive Search Procedures». En: Journal of Global Optimization (1995). issn: 09255001. doi:10. 1007/BF01096763. [14] Manuela Fernandes, Luis Gouveia y Stefan Voss. «Determining Hop-Constrained Spanning Trees with Repetitive Heuristics». En: Journal of Telecommunications and Information Technology (2007). [15] Luis Gouveia. «Multicommodity flow models for spanning trees with hop constraints». En: European Journal of Operational Research (1996). issn: 03772217. doi:10.1016/0377-2217(95)00090-9. [16] Luis Gouveia. «Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with hop constraints». En: Computers and Operations Research (1995). issn: 03050548. doi:10.1016/0305-0548(94)00074-I. [17] Luis Gouveia. «Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints». En: INFORMS Journal on Computing (1998). issn: 10919856. doi:10.1287/ijoc.10.2.180. [18] Luis Gouveia, Ana Paias y Dushyant Sharma. «Restricted dynamic programming based neighborhoods for the hop-constrained minimum spanning tree problem». En: Journal of Heuristics (2011). issn: 13811231. doi:10.1007/s10732-009-9123-5. [19] Luís Gouveia y Dushyant Sharma. «Local Search Heuristics for the Hop-Constrained Minimum Spanning Tree Problem». En: (2007). [20] Martin Gruber, Jano van Hemert y Günther Raidl. «Neighborhood Searches for the Bounded Diameter Minimum Spanning Tree Problem Embedded in a VNS, EA, and ACO». En: GECCO 2006 - Genetic and Evolutionary Computation Conference. Vol. 2. 2006. doi:10.1145/1143997.1144185. [21] Maurice Karnaugh. «A New Class of Algorithms for Multipoint Network Optimization». En: IEEE Transactions on Communications (1976). issn: 00906778. doi: 10.1109/TCOM.1976.1093334. [22] S. Kirkpatrick, C. D. Gelatt y M. P. Vecchi. «Optimization by simulated annealing». En: Science (1983). issn: 00368075. doi:10.1126/science.220.4598.671. [23] Joseph B. Kruskal. «On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem». En: Proceedings of the American Mathematical Society (1956). issn: 00029939. doi:10.2307/2033241. Andrés Bravo Núñez 85 Bibliografía Bibliografía [24] Nicholas Metropolis y col. «Equation of state calculations by fast computing machines». En: The Journal of Chemical Physics (1953). issn: 00219606. doi:10.1063/ 1.1699114. [25] C. E. Miller, A. W. Tucker y R. A. Zemlin. «Integer Programming Formulation of Traveling Salesman Problems». En: Journal of the ACM (1960). issn: 00045411. doi:10.1145/321043.321046. [26] J. Mockus y col. «Bayesian discrete and global optimization». En: Kluwer Academic Publisher (1997). issn: 00401706. doi:10.1007/978-1-4757-2627-5. [27] Manfred W. Padberg. «On the facial structure of set packing polyhedra». En: Mathematical Programming (1973). issn: 00255610. doi:10.1007/BF01580121. [28] Marcelo Paris y Celso C. Ribeiro. «Reactive GRASP: An Application to a Matrix Decomposition Problem in TDMA Traffic Assignment». En: INFORMS Journal on Computing (2000). issn: 10919856. [29] R. C. Prim. «Shortest Connection Networks And Some Generalizations». En: Bell System Technical Journal (1957). issn: 15387305. doi:10.1002/j.1538-7305. 1957.tb01515.x. [30] Mauricio G C Resende y José Luis Gonzáles Velarde. «Greedy randomized adaptive search procedures (GRASP)». En: Encyclopedia of optimization (2003). doi:doi: 10.1088/1475-7516/2007/08/005. [31] Hanif D. Sherali y Warren P. Adams. «A hierarchy of relaxations and convex hull characterizations for mixed-integer zero-one programming problems». En: Discrete Applied Mathematics (1994). issn: 0166218X. doi:10.1016/0166-218X(92)00190W. [32] Hanif D. Sherali, Warren P. Adams y Patrick J. Driscoll. «Exploiting Special Structures in Constructing a Hierarchy of Relaxations for 0-1 Mixed Integer Problems». En: Operations Research (1998). issn: 0030-364X. doi:10.1287/opre.46.3.396. [33] Hanif D. Sherali y Patrick J. Driscoll. «On Tightening the Relaxations of MillerTucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems». En: Operations Research (2003). issn: 0030-364X. doi:10.1287/opre.50.4.656.2865. [34] Laurence Wolsey. «Technical Note–Facets and Strong Valid Inequalities for Integer Programs». En: Operations Research 24 (abr. de 1976), págs. 367-372. doi:10. 1287/opre.24.2.367. [35] Kathleen A. Woolston y Susan L. Albin. «The design of centralized networks with reliability and availability constraints». En: Computers and Operations Research 15.3 (ene. de 1988), págs. 207-217. issn: 03050548. doi:10.1016/0305-0548(88)900330.url:http://linkinghub.elsevier.com/retrieve/pii/0305054888900330. Andrés Bravo Núñez 86