Repositorio Institucional de Documentos

Trabajo Fin de M´ aster El problema del anillo-estrella Autor: Jos´e ´ Angel Iranzo Sanz Directora: Dra. Herminia I. Calvete Fern´andez M´ aster en Modelizaci´ on Matem´ atica, Estad´ ıstica y Computaci´ on Pr´ologo Resumen Sea G= (V, E ∪A) un grafo mixto, donde V={0,1, . . . , n}es el conjunto de nodos, E={[i, j] : i, j ∈V, i 6=j}es el conjunto de ejes y A={(i, j) : i, j ∈V}es el conjunto de arcos. Cada eje e= [i, j]∈Etiene asociado un coste no negativo ce=cij y cada arco a= (i, j)∈A, que representa la asignaci´on del nodo ial nodo j, tiene asociado un coste no negativo da=dij. El problema del anillo-estrella (Ring Star Problem, RSP) consiste en dise˜nar un ciclo simple (anillo) que pasa por el nodo 0 usando los ejes de Ey asignar cada nodo no visitado por el anillo al nodo m´as cercano del anillo usando los arcos de A. El objetivo es minimizar el coste del ciclo mas el coste de las asignaciones. Este problema tiene numerosas aplicaciones pr´acticas en el campo del dise˜no urbano de redes de telecomunicaciones. Este trabajo se divide en cuatro cap´ıtulos. El primero sirve como introducci´on y justificaci´on del problema, y plantea la relaci´on del RSP con su aplicaci´on pr´actica en el dise˜no de redes de telecomunicaciones. En el segundo cap´ıtulo, se describe formalmente el problema, se detallan algunas de las formulaciones como un problema de programaci´on lineal entera que se han propuesto en la literatura y se describen los algoritmos utilizados para resolver dichos problemas. Finalmente, se revisan algunas variantes del RSP. En el tercer cap´ıtulo, se propone una transformaci´on del RSP en un problema del viajante generalizado (GTSP) que permite resolver el RSP aplicando las t´ecnicas y algoritmos existentes para el GTSP. Por ´ultimo, en el cuarto cap´ıtulo, se propone un algoritmo evolutivo para resolver de forma heur´ıstica el RSP y se muestran algunos de los resultados experimentales obtenidos a partir de una implementaci´on del algoritmo en C++, cuyo c´odigo se presenta en el anexo. Abstract Let G= (V, E ∪A) be a mixed graph, where V={0,1, . . . , n}is the node set, E={[i, j] : i, j ∈V, i 6=j}is the edge set and A={(i, j) : i, j ∈V}is the arc set. Each edge e= [i, j]∈Eis associated with a nonnegative cost ce=cij and each arc a= (i, j)∈A, which represents that node iis assigned to node j, is associated with a nonnegative cost da=dij. The Ring Star Problem (RSP) is the problem of designing a simple cycle (ring) that passes through node 0 using the edges and then assigning each non-visited node to a visited one using the arcs. The objective is to minimize the sum of ring and assignment costs. The problem has many practical applications in the design of urban optical telecommunication networks. This report is divided into four chapters. The first one introduces and justifies the problem, and discusses the use of the RSP to model real applications in the design of telecommunications networks. The second chapter states the problem, presents some of the integer linear programming formulations proposed in the literature and describes algorithms used to solve these problems. The chapter concludes with a review of some related problems. In the third chapter a transformation of the RSP into a generalized traveling salesman problem (GTSP) is proposed that allows us to solve the RSP using existing techniques and algorithms for the GTSP. Finally, in the fourth chapter an evolutionary algorithm to solve the RSP heuristically is developed and some experimental results to prove its performance are shown. The experiment is carried out with a C++ implementation of the algorithm, which is attached at the end of this report. ´ Indice 1. Introducci´on 1 1.1. Descripci´on del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2. Antecedentes .................................. 3 2. El problema del anillo-estrella (RSP) 5 2.1. Definici´on del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2. Formulaci´on basada en ciclos (Labb´e et al.) . . . . . . . . . . . . . . . . . 7 2.2.1. Algoritmo ................................ 10 2.3. Formulaci´on basada en caminos (Kedad-Sidhoum y Nguyen) . . . . . . . . 12 2.3.1. Algoritmo ................................ 13 2.4. Formulaci´on basada en el STP (Simonetti et al.) . . . . . . . . . . . . . . . 15 2.4.1. Construcci´on del grafo transformado . . . . . . . . . . . . . . . . . 15 2.4.2. Formulaci´on del CTSP asociado al RSP . . . . . . . . . . . . . . . 17 2.4.3. Algoritmo ................................ 20 2.5. Algunas variantes del RSP . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.5.1. El problema del ciclo mediano . . . . . . . . . . . . . . . . . . . . . 20 2.5.2. El problema del anillo-estrella bi-objetivo . . . . . . . . . . . . . . . 21 2.5.3. El problema del anillo-estrella con nodos de Steiner . . . . . . . . . 22 2.5.4. El problema del m-anillo-estrella . . . . . . . . . . . . . . . . . . . 24 2.5.5. El problema del anillo-estrella multidep´osito . . . . . . . . . . . . . 25 3. Una transformaci´on del RSP en el problema del viajante generalizado 27 3.1. Introducci´on................................... 27 3.2. Construcci´on del grafo del problema GTSP transformado . . . . . . . . . . 28 iii 3.3. Formulaci´on matem´atica del problema GTSP transformado . . . . . . . . . 30 4. Un algoritmo evolutivo para el RSP 33 4.1. Codificaci´on de los individuos . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.2. Poblaci´oninicial................................. 35 4.3. Operador de cruce o recombinaci´on . . . . . . . . . . . . . . . . . . . . . . 35 4.4. Operador de mutaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 4.5. Operador de b´usqueda local (2-opt) . . . . . . . . . . . . . . . . . . . . . . 37 4.6. Selecci´on de supervivientes . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 4.7. Criteriodeparada ............................... 39 4.8. Descripci´on del algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.9. Resultados experimentales . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Bibliograf´ıa 47 Anexo I: C´odigo C++ 49 iv 1 Introducci´on 1.1. Descripci´on del problema El problema del anillo-estrella (The Ring Star Problem, RSP) consiste en encontrar un ciclo simple a trav´es de un subconjunto de nodos de un grafo, de manera que se minimiza el coste total obtenido como la suma del coste del ciclo y el coste de asignaci´on de cada uno de los nodos que no est´an en el ciclo al nodo m´as cercano que s´ı lo est´a. Este problema aparece a menudo en problemas reales de dise˜no de redes de telecomunicaciones. Una red de telecomunicaciones gen´erica est´a formada por clientes, concentradores, una unidad central, una serie de enlaces que conectan cada cliente con un concentrador y una red de conexiones que interconecta los concentradores o los conecta a la unidad central. Una forma de abordar el dise˜no de estas redes consiste en utilizar ciertos clientes como concentradores, conectar cada uno de los clientes restantes a uno de los utilizados como concentradores, formando as´ı estructuras de tipo estrella, e interconectar los clientes-concentradores y la unidad central mediante una estructura de anillo. Puede verse un ejemplo de esta estructura de tipo anillo-estrella en la Figura 1.1. La estructura de tipo anillo se utiliza para dise˜nar gran parte de las redes de comunicaci´on por fibra ´optica con el fin de prevenir las p´erdidas de conexi´on causadas por un fallo puntual en alg´un punto de la red. El anillo se construye con un cable que contiene un haz de fibras ´opticas. Se selecciona un cierto subconjunto de clientes en los que se instalar´an concentradores, se interconectan los concentradores y se asigna cada cliente al concentrador m´as cercano. Cada cliente recibe dos hilos de fibra ´optica que lo conectan con la central de intercambio de datos (unidad central) a trav´es de los dos sentidos posibles del anillo. Supongamos que un cliente ique est´a en el anillo est´a comunic´andose con otros a trav´es de la porci´on del anillo que parte de la unidad central en el sentido de las agujas 1 2El problema del anillo-estrella Unidad central Clientes Figura 1.1: Ejemplo de estructura de tipo anillo-estrella de reloj. Si un eje de esa porci´on falla, es posible redirigir la informaci´on desde/hacia el cliente ia trav´es de la porci´on contraria del anillo, que no habr´ıa sido afectada por el fallo. De esta manera se garantiza un servicio de comunicaci´on continua ante eventuales fallos o rupturas de los cables de fibra ´optica que trasmiten la informaci´on. Por otro lado, la estructura anillo-estrella, en general, provoca un menor coste. En efecto, el coste total de la red de comunicaci´on depende de varios factores tales como el coste de los cables de fibra ´optica o los dispositivos necesarios para la comunicaci´on, pero, en general, el coste principal se debe a las excavaciones necesarias para enterrar los tubos con cables de fibra ´optica bajo tierra. Por tanto, las empresas de telecomunicaciones tratan de reducir este coste tanto como sea posible. Supongamos que todos los clientes salvo uno, el cliente i, est´an localizados en un anillo circular y conectados entre s´ı mediante un cable que recorre el anillo. Para conectar el nuevo cliente ia la red, puede ampliarse el anillo para que pase por el nuevo cliente, lo que obliga a conectarlo con dos de los clientes del anillo o, si la distancia a un cliente que ya est´e en el anillo es peque˜na, puede considerarse la posibilidad de conectar el nuevo cliente icon el cliente m´as cercano del anillo mediante un eje, lo que, en general, es menos costoso ya que los costes de excavaci´on son menores. En este caso, las comunicaciones del cliente ise realizan a trav´es de este eje, en el que se enterrar´ıa el tubo que contiene el cable. Si se produjera un fallo puntual en este cable, el cliente iquedar´ıa desconectado de la red, mientras que el resto de los clientes podr´ıan continuar comunicados. Generalmente, la empresa est´a m´as dispuesta a asumir los inconvenientes generados por la incomunicaci´on de un cliente que el costo de excavaci´on asociado a agrandar el anillo para la inclusi´on de un nuevo cliente. En ocasiones la situaci´on real es m´as compleja por lo que es necesario a˜nadir m´as Jos´e ´ Angel Iranzo Sanz 3 condiciones al problema para que se ajuste m´as fielmente a la realidad. Por ejemplo, en la actualidad, el cable que interconecta los concentradores contiene, en su forma est´andar, un haz de 100 fibras ´opticas que puede abastecer, a lo sumo, a 50 clientes. Si el n´umero de clientes es superior a 50 surge el problema de c´omo dise˜nar una red que llegue a todos los clientes conservando las buenas propiedades de las soluciones de tipo anillo-estrella. Una posibilidad consiste en dise˜nar una red con varios anillos-estrella conectados a una misma unidad central, cada uno de ellos con una cantidad m´axima de clientes asociados. Adem´as, con este modelo se consigue a´un mayor fiabilidad, ya que si uno de los anillos queda totalmente inutilizado, solamente los clientes de ese anillo quedan incomunicados. Este problema, que generaliza el RSP, se denomina el problema del m-anillo-estrella con restricciones de capacidad (The Capacitated m-Ring Star Problem, CmRSP). 1.2. Antecedentes Aunque algunas variantes del problema de obtenci´on de una estructura de anilloestrella hab´ıan sido consideradas con anterioridad, el RSP con las caracter´ısticas que se estudian en este trabajo fue introducido por Labb´e et al. (2004), que formulan el problema como un problema de programaci´on lineal entera y desarrollan un algoritmo de resoluci´on exacto a partir de un m´etodo de ramificaci´on y corte basado en ciertas propiedades del poliedro definido por las restricciones. Posteriormente, Kedad-Sidhoum y Nguyen (2010) proponen una nueva formulaci´on como un problema de programaci´on lineal entera, que est´a basada en caminos simples no dirigidos, y utilizan un algoritmo similar al propuesto por Labb´e et al. (2004) para su resoluci´on. Simonetti et al. (2011) proponen una nueva formulaci´on que transforma el problema en uno de tipo Steiner Tree Problem (STP). Bas´andose en el problema transformado, desarrollan un nuevo algoritmo de resoluci´on del problema basado en t´ecnicas de ramificaci´on y corte. Adem´as de los algoritmos exactos, basados en general en el uso de t´ecnicas de ramificaci´on y corte, en la literatura se ha propuesto el uso de algoritmos metaheur´ısticos para resolver el problema. P´erez et al. (2003) proponen un algoritmo que combina procedimientos de b´usqueda en entornos variables(Variable Neighbourhood Search, VNS) y de b´usqueda tab´u (Tabu Search, TS). Renaud et al. (2004) proponen un algoritmo que combina heuristicas voraces y t´ecnicas evolutivas. Dias et al. (2006) proponen un algoritmo metaheur´ıstico h´ıbrido para la resoluci´on del RSP basado en procedimientos Greedy Randomized Adaptive Search Procedures (GRASP) y General Variable Neighbourhood Search (GVNS). En la literatura se han estudiado otros problemas directamente relacionados con el 10 El problema del anillo-estrella Otra familia de desigualdades v´alidas aparece debido a que ciertas asignaciones son incompatibles. En concreto, las variables yij eyik son incompatibles cuando j6=k, es decir yij +yik ≤1∀j, k ∈V, j 6=k(2.5) An´alogamente, se dan tambi´en la siguientes desigualdades yij +yjk +yki ≤1∀i, j, k ∈Udiferentes (2.6) Finalmente, combinando las restricciones (2.3), con S={i, j, k} ⊆ U, y las restricciones (2.5) obtenemos nuevas desigualdades v´alidas para el RSP: x(δ(S)) ≥2(yij +yjk +yki)∀i, j, k ∈Udiferentes (2.7) 2.2.1. Algoritmo Para resolver el RSP, Labb´e et al. (2004) proponen un algoritmo de ramificaci´on y corte que permite encontrar un anillo, C, soluci´on ´optima del RSP. Los algoritmos de ramificaci´on y corte son usados para resolver problemas generales de programaci´on lineal entera y combinan m´etodos de ramificaci´on y acotaci´on con m´etodos de planos de corte. Los m´etodos de ramificaci´on y acotaci´on son m´etodos enumerativos que recorren impl´ıcitamente todas las soluciones enteras factibles (Nemhauser y Wolsey (1999)). Aunque el n´umero de posibles soluciones aumenta de forma exponencial con respecto al numero de variables del problema, los algoritmos de ramificaci´on y acotaci´on introducen reglas para poder descartar conjuntos de soluciones sin evaluarlas una a una. En el proceso de ramificaci´on se a˜naden restricciones al modelo que fuerzan a que una de las variables sea entera y en el proceso de acotaci´on se permite cerrar ramas cuando se tiene la garant´ıa de que las nuevas soluciones enteras que se introducir´an al ramificar no proporcionan un valor ´optimo para el problema original. Los m´etodos de corte, en cambio, son m´etodos no enumerativos que introducen sucesivos cortes sobre la regi´on factible hasta localizar la mejor soluci´on entera. Un plano de corte para un problema de programaci´on entera es una restricci´on que reduce la regi´on factible del problema relajado (sin restricciones de integridad) sin eliminar soluciones factibles para el problema original. Denotaremos por V(C) el conjunto de nodos en la soluci´on. A continuaci´on se describen los pasos del algoritmo: Paso 1: Inicializaci´on. Jos´e ´ Angel Iranzo Sanz 11 Se inicializa el contador de iteraciones, t= 0, y se calcula una cota superior zdel RSP ´optimo: Empezando por V(C) = {0}, se inserta sucesivamente un nodo i /∈V(C) que minimice L(i, λ) = λ inc(C, i) + (1 −λ)(−dec(C, i)) donde inc(C, i) es el menor de los incrementos producido en el coste del anillo Cal insertar i, y dec(C, i) es el decrecimiento producido en el coste de asignaci´on. Esta operaci´on se repite siempre y cuando L(i, λ) decrezca con una nueva inserci´on. El c´alculo se realiza para λ∈ {0.1,0.3,0.5,0.7,0.9}y se selecciona la mejor soluci´on. Los valores de λse han elegido para generar cinco anillos, cada uno de los cuales asigna un peso diferente al coste del anillo y al coste de asignaci´on. Por otro lado se resuelve el subproblema lineal inicial que se formula como: min X e∈E cexe+X a∈A daya sujeto a x(δ(0)) = 2 x(δ(i)) = 2yii ∀i∈U X j∈V yij = 1 ∀i∈U x0i≤yii ∀i∈U Se inserta su soluci´on en la lista L. Paso 2: Finalizaci´on o selecci´on de un subproblema. Si L=∅el algoritmo termina. En otro caso, se selecciona el subproblema de la lista Lcon menor valor de la funci´on objetivo y se va al Paso 3. Paso 3: Soluci´on del subproblema. Se actualiza la iteraci´on t=t+ 1. Sea zel valor de la funci´on objetivo del subproblema seleccionado. Si z≥z, se va al Paso 2. En otro caso, si la soluci´on es factible para el RSP, se toma z=z, se actualiza Cal nuevo anillo soluci´on e se vuelve al Paso 2. En otro caso, se contin´ua con el Paso 4. Paso 4: Heur´ıstica basada en Programaci´on Lineal. Si la soluci´on es fraccionaria y tes m´ultiplo de 5, se aplica el siguiente procedimiento heur´ıstico: 12 El problema del anillo-estrella Dada la soluci´on fraccionaria (x∗, y∗), se ordenan las variables x∗ ij en orden decreciente con respecto a los valores cij y se toman, uno a uno, los ejes asociados hasta obtener el anillo C∗. Si el nodo 0 no est´a en C∗, se introduce en la mejor posici´on. Finalmente, se aplica el procedimiento 2-opt desarrollado por Lin (1965) para tratar de reducir el coste del anillo C∗. Sea z∗el valor de la funci´on objetivo de la soluci´on C∗. Si z∗≤z, se toma z=z∗y se actualiza CaC∗. A continuaci´on se pasa al Paso 5. Paso 5: Generaci´on y separaci´on de restricciones. Se introducen hasta 300 restricciones de conectividad (2.1e) no satisfechas y las restricciones (2.2), (2.6) y (2.7). Si no se pueden generar restricciones se va al Paso 6 y, en otro caso, al Paso 3. Paso 6: Ramificaci´on. Se crean dos subproblemas por ramificaci´on de una variable no entera yii oxij. La primera estrategia de ramificaci´on consiste en encontrar una variable yii. Para ello, se aplica la regla de ramificaci´on fuerte con las 5 variables yii con valor fraccionario m´as cercano a 0.5. Si todas estas variables son enteras, se selecciona una variable xij usando el mismo criterio. Se insertan los dos subproblemas generados en Ly se contin´ua al Paso 2. 2.3. Formulaci´on basada en caminos (Kedad-Sidhoum y Nguyen) Esta formulaci´on es similar a la presentada por Labb´e et al. (2004) y, por tanto, se utilizar´a la misma notaci´on que en la Secci´on 2.2 para plantearla. Llamaremos sal nodo 0 y a˜nadiremos un nodo auxiliar tcopia del nodo sobteniendo as´ı un nuevo grafo G0= (V0, E0∪A0) donde V0=V∪ {t},E0=E∪ {[s, t]}∪{[t, u]:[s, u]∈E}yA0=A. As´ı, una soluci´on del RSP en Gconsiste en un camino desde shasta ten G0que asigna cada nodo que no est´a en el camino a uno que si lo est´a (excepto t). La formulaci´on como un problema de programaci´on lineal entera mixta a partir del grafo G0es similar a la anteriormente presentada basada en ciclos. La funci´on objetivo es la misma y las restricciones que estaban relacionadas con el nodo 0, ahora est´an expresadas en funci´on de sy de t. Tenemos as´ı: Jos´e ´ Angel Iranzo Sanz 13 min X e∈E0 cexe+X a∈A0 daya(2.8a) sujeto a x(δ(s)) = 1, x(δ(t)) = 1 (2.8b) x(δ(i)) = 2yii ∀i∈V0\ {s, t}(2.8c) X j∈V0 yij = 1 ∀i∈V0\ {s, t}(2.8d) x(δ(S)) ≥2X j∈S yij ∀S⊆V0\ {s, t},∀i∈S(2.8e) xe, ya∈ {0,1} ∀e∈E0, a ∈A0(2.8f) En el trabajo se se˜nala que es posible a˜nadir desigualdades v´alidas al problema relajado adaptando, cuando sea posible, las que se a˜nadieron en la Secci´on 2.2 para la formulaci´on de Labb´e et al. (2004). La ventaja principal de la formulaci´on introducida por Kedad- Sidhoum y Nguyen (2010) es que permite a˜nadir ciertas desigualdades a partir del poliedro st-camino que no se dan para la formulaci´on basada en ciclos. En particular, se dan la siguientes desigualdades st-camino blossom x(δ(H)\T)−x(T) + (1 − |T|)xst ≥1− |T|(2.9) para todo H⊆V0yT⊆δ(H) con |T|+|H∩ {s, t}| impar. 2.3.1. Algoritmo La idea general del algoritmo de ramificaci´on y corte usado por Kedad-Sidhoum y Nguyen (2010) para resolver el RSP es similar a la del algoritmo desarrollado por Labb´e et al. (2004) descrito en la Secci´on 2.2. La principal diferencia es que en el algoritmo propuesto por Kedad-Sidhoum y Nguyen (2010) se introducen las restricciones st-camino blossom (2.9). Denotaremos con V(C) el conjunto de nodos en el st-camino soluci´on C. La descripci´on del algoritmo es la siguiente: Paso 1: Inicializaci´on. Se inicializa el contador de iteraciones t= 0 y se calcula una cota superior zdel RSP ´optimo de la siguiente manera: Empezando con V(C) = {s, t}, se inserta sucesivamente un nodo i /∈V(C) que minimice L(i, λ) = λ inc(C, i) + (1 −λ)(−dec(C, i)) 14 El problema del anillo-estrella donde inc(C, i) es el menor de los incrementos producido en el coste del st-camino Cal insertar iydec(C, i) es el decrecimiento producido en el coste de asignaci´on. Esta operaci´on se repite siempre y cuando L(i, λ)<0 con un nueva inserci´on. Este proceso se realiza para λ∈ {0.1,0.3,0.5,0.7,0.9}y se selecciona la mejor soluci´on. Los valores de λse han elegido para generar cinco soluciones, cada una con pesos diferentes para el coste del anillo y el coste de asignaci´on. Por otro lado se resuelve el subproblema lineal inicial que se formula como: min X e∈E0 cexe+X a∈A0 daya sujeto a x(δ(s)) = 1, x(δ(t)) = 1 x(δ(i)) = 2yii ∀i∈V0\ {s, t} X j∈V0 yij = 1 ∀i∈V0\ {s, t} xe∈ {0,1}, ya≥0∀e∈E0, a ∈A0 Se inserta su soluci´on en la lista L. Paso 2: Finalizaci´on o selecci´on de un subproblema. Si L=∅el algoritmo termina. En otro caso, se selecciona el subproblema de la lista Lcon menor valor de la funci´on objetivo y se va al Paso 3. Paso 3: Soluci´on del subproblema. Se actualiza la iteraci´on t=t+ 1. Sea zel valor de la funci´on objetivo del subproblema seleccionado. Si z≥zse va al Paso 2. En otro caso, si la soluci´on es factible para el RSP, se toma z=z, se actualiza Cal nuevo anillo soluci´on y se vuelve al Paso 2. En otro caso, se contin´ua con el Paso 4. Paso 4: Generaci´on y separaci´on de restricciones. Se introducen restricciones de conectividad (2.8e) no satisfechas y restricciones blossom (2.9). Si no es posible generar restricciones se va al Paso 5 y, en otro caso, al Paso 3. Paso 5: Ramificaci´on. Se crean dos subproblemas por ramificaci´on de una variable no entera yii oxij. La primera estrategia de ramificaci´on consiste en encontrar una variable yii. Para ello, se aplica la regla de ramificaci´on fuerte con las 5 variables yii con valor fraccionario m´as cercano a 0.5. Si todas estas variables son enteras, se selecciona una variable Jos´e ´ Angel Iranzo Sanz 15 xij usando el mismo criterio. Se insertan los dos subproblemas generados en Ly se contin´ua con el Paso 2. 2.4. Formulaci´on basada en el STP (Simonetti et al.) Simonetti et al. (2011) proponen una transformaci´on del problema RSP en un problema de tipo STP (Steiner Tree Problem) con restricciones adicionales. El Steiner Tree Problem (STP), tambi´en conocido como Minimum Steiner Arborescence Problem, es una generalizaci´on del cl´asico problema del ´arbol de expansi´on m´ınima (Minimum Spanning Tree Problem, MSTP). Sea un grafo G= (V , A) donde cada uno de sus arcos tiene asociado un cierto coste. En el MSTP se trata de encontrar el ´arbol de m´ınimo coste que contiene todos los nodos de un grafo dado. En el STP, dado r∈V, denominado nodo ra´ız, y dado un conjunto R⊆Vde nodos, denominados nodos terminales, el objetivo del STP es encontrar el ´arbol de menor coste con ra´ız en rque contiene los nodos de R. 2.4.1. Construcci´on del grafo transformado Dado G= (V, E ∪A), el grafo del RSP definido en la Secci´on 2.1, se construye el grafo dirigido G= (V , A) sobre el que se plantea el STP. El grafo Gse estructura en dos niveles numerados como 1 y 2. Para cada nodo i∈Vse crean dos nodos en V, el nodo i1en el nivel 1 y el nodo i2 en el nivel 2. Para el nodo 0, adem´as de los nodos 01y 02, se crean en el correspondiente nivel 2 nuevas copias denotadas como 00 1y 00 2. Para cada eje [i, j]∈Econ i, j 6= 0, se crean en Alos arcos (i1, j1) y (j1, i1). Adem´as, para cada eje del tipo [0, i]∈Ese incluyen en Alos arcos (01, i1) e (i1,00 1). El resto de arcos de Ason los de la forma (i1, i2) para todo i∈V, los (j1, i2) para todo (i, j)∈Acon i6= 0 y, finalmente, los arcos (01,00 1) y (00 1,00 2). Por tanto, V={i1:i∈U}∪{i2:i∈U}∪{01,02,00 1,00 2} A={(i1, j1),(j1, i1):[i, j]∈E, i, j ∈U}∪{(01, i1),(i1,00 1) : [0, i]∈E}∪{(i1, i2) : i∈V} ∪ {(j1, i2):(i, j)∈A, i ∈U}∪{(01,00 1),(00 1,00 2)} En la Figura 2.3 se muestra un ejemplo de un grafo y su correspondiente grafo transformado en dos niveles. En el grafo transformado, los arcos cuyo nodo inicial y final est´an en el primer nivel se 16 El problema del anillo-estrella 1 23 0 (a) G= (V, E ∪A) 0130' 112111 0123 0' 22 2 22 (b) Grafo transformado G= (V , A) Figura 2.3: Ejemplo de transformaci´on del RSP en STP identifican con ejes del anillo. El resto de los arcos, es decir, los que tienen el nodo inicial en el primer nivel y el nodo final en el segundo nivel, se identifican con asignaciones de clientes que no est´an en el anillo a clientes que s´ı lo est´an. Los costes que se asignan a los arcos de Ase calculan de la siguiente manera. El coste de los arcos (01,00 1) y (i1, i2) para i1∈V1es cero. Dado un arco (i, j)∈A, el arco asociado (j1, i2)∈Atiene un coste de dij. An´alogamente, dado un eje [i, j]∈E,i, j 6= 0, los arcos asociados (i1, j1)y(j1, i1) en Atienen un coste de cij. Finalmente, para los nodos i∈V vecinos del nodo 0, el coste de los arcos (01, i1)e(i1,00 1) es c0i. En general, para cada arco a∈Allamaremos caal coste asignado a dicho arco. Se tiene, por tanto c0100 1=0 ci1i2=0 ∀i1∈V1 cj1i2=dij ∀(i, j)∈A ci1j1=ci1j1=cij ∀[i, j]∈E, i ∈U, j ∈U c01i1=ci100 1=c0i∀[0, i]∈E Para definir el problema STP asociado al RSP es necesario identificar el nodo ra´ız ry el conjunto de nodos terminales R. En este caso, el nodo ra´ız es r= 01yRes el conjunto de nodos del nivel 2 del grafo G. Adem´as, se necesita una restricci´on adicional que garantice que, en cualquier soluci´on del problema STP, para un nodo en el nivel 1 existe a los sumo un arco que parte de ese nodo y llega a otro nodo en el mismo nivel. Esta restricci´on adicional evita que puedan darse soluciones como la de la Figura 2.4. En la Figura 2.4b se muestra una soluci´on factible para el problema STP. Sin embargo, en la Figura 2.4a se observa que esta soluci´on no se identifica con ninguna soluci´on del correspondiente RSP. Este problema STP con restricciones adicionales se denomina CSTP (Constrained Steiner Tree Problem). Jos´e ´ Angel Iranzo Sanz 17 1 23 0 (a) Soluci´on no factible para el RSP 0130' 112111 0123 0' 22 2 22 (b) Soluci´on factible para el STP Figura 2.4: Ejemplo de soluci´on no factible para el RSP pero s´ı para el STP Notemos que, por la construcci´on del grafo transformado G, la ´unica forma de llegar al nodo 00 2es a trav´es del arco (00 1,00 2), es decir, incluyendo el nodo 00 1en el ´arbol soluci´on. De esta manera, la construcci´on del grafo G0junto con la restricci´on adicional garantizan que una soluci´on factible del CSTP induce, sobre los nodos del nivel 1, un camino entre los nodos 01y 00 1. La Figura 2.5 ilustra la correspondencia entre una soluci´on del RSP y una del CSTP. 1 23 0 (a) Soluci´on RSP 0130' 112111 0123 0' 22 2 22 (b) Soluci´on CTSP Figura 2.5: Ejemplo de soluci´on transformada 2.4.2. Formulaci´on del CTSP asociado al RSP Para cada arco a= (i, j)∈Adefinimos la variable binaria xa=xij que toma el valor 1 si el arco apertenece al ´arbol soluci´on y el valor 0 en otro caso. Con esta definici´on, el 18 El problema del anillo-estrella CSTP sobre Gse formula como el siguiente problema de programaci´on lineal entera: min X a∈A caxa(2.10a) sujeto a X (i,j)∈A,j∈V1 xij ≤1∀i∈V1(2.10b) X (i,j)∈A xij ≤1∀j∈V(2.10c) X i∈V\SX j∈S xij ≥1∀S⊆V\ {01}, S ∩V26=∅(2.10d) xij ∈ {0,1} ∀(i, j)∈A, i, j ∈V1(2.10e) xij ∈ {0,1} ∀(i, j)∈A, i ∈V1, j ∈V2(2.10f) La funci´on objetivo (2.10a) busca la minimizaci´on del coste del ´arbol soluci´on. Las restricciones (2.10b) limitan el n´umero de arcos que parten de un nodo en el nivel 1 a otro en el mismo nivel a uno. Las restricciones (2.10c) limitan a uno el n´umero de arcos que llegan a un nodo en la soluci´on. Las restricciones (2.10d), conocidas como cortes de Steiner, aseguran que los nodos terminales (V2=R) son alcanzados por la soluci´on. Puede verse que, debido a los costes asignados a los arcos de G, estas restricciones fuerzan la existencia de una soluci´on ´optima cuyo subgrafo inducido sobre los arcos cuyos nodos est´an en el nivel 1 es un camino. Simonetti et al. (2011) hacen notar que las restricciones (2.10f) se pueden relajar axij ≥0 en esta formulaci´on. Esto se debe a que hay un soluci´on ´optima entera del modelo siempre que se imponga que las variables de los arcos internos del nivel 1 sean enteras. Observemos tambi´en que esta formulaci´on del CSTP admite soluciones factibles que pueden contener ciclos. Sin embargo, dado que los costes de todas las variables son no negativos y que la funci´on objetivo es de m´ınimo, se observa que hay una soluci´on ´optima de tipo ´arbol de Steiner. Simonetti et al. (2011) introducen una serie de restricciones adicionales con el fin de mejorar las cotas del problema lineal relajado. Se˜nalan que por la propia construcci´on del modelo CSTP, y haciendo uso de las restricciones (2.10d), se obtienen las siguientes restricciones que son satisfechas por, al menos, una soluci´on ´optima: X (i1,j1)∈A xi1j1=xj1j2∀j1∈V1\ {01}(2.11) donde j2es la copia correspondiente al nodo j1en el nivel 2. Notemos que, para un par de nodos j1yj2, las restricciones (2.11) fuerzan a que el arco (j1, j2) est´e en la soluci´on siempre que el nodo j1est´e en la soluci´on. Jos´e ´ Angel Iranzo Sanz 19 Tambi´en son v´alidas las restricciones (2.12) ya que en un ´arbol de Steiner ´optimo, para cada j1∈V\ {01,00 1}, si consideramos s´olo los arcos entre nodos del nivel 1, el n´umero de arcos que llegan y que dejan j1debe ser el mismo: X (j1,i)∈A,i∈V1 xj1i=X (i,j1)∈A,i∈V1 xij1∀j1∈V1\ {01,00 1}(2.12) Combinando las restricciones (2.11) y (2.12) para todo j1∈V1\ {01,00 1}se obtiene un nuevo conjunto de igualdades para el modelo (2.10) m´as fuertes que las restricciones (2.10b). Estas igualdades son: X (j1,i)∈A,i∈V1 xj1i=xj1j2∀j1∈V1\ {01,00 1}(2.13) La estructura y los costes del grafo Gaseguran que existe una soluci´on ´optima con x0102= 1 (2.14) y los cortes de Steiner (2.10d) para S={00 2}fuerzan la igualdad x00 100 2= 1 (2.15) Tambi´en son v´alidas para este problema las desigualdades estudiadas por Bauer (1997). Sea H⊆V1un subconjunto de nodos y sean los conjuntos de arcos A(H) = {(i, j)∈A: i, j ∈H}yδ1(H) = {(i, j)∈A:i∈Hj ∈V1\H}. Adem´as, sea T⊆δ1(H) y T={(j, i)∈A: (i, j)∈T}. Entonces, se tiene la siguiente desigualdad X a∈A(H) xa+X a∈T∪T xa≤X i∈H xi1i2+|T| − 1 2(2.16) siempre que (i) {i, j}∩{k, l}=∅para [i, j],[k, l]∈Tsi [i, j]6= [k, l]. (ii) |T| ≥ 3 e impar. Esta desigualdad, adecuadamente adaptada, aparece tambi´en en los modelos de Labb´e et al. (2004) y Kedad-Sidhoum y Nguyen (2010), y se obtiene de forma an´aloga. As´ı, se puede reforzar el modelo (2.10) reemplazando las restricciones (2.10b) por las igualdades (2.13) y a˜nadiendo las ecuaciones (2.11), (2.14) y (2.15). Este modelo se denomina RCSTM (Reinforced Constrained Steiner Tree Model). 26 El problema del anillo-estrella anillos, dependiendo de las restricciones que tenga asociada cada una de ellas. El objetivo del MDRSP es dise˜nar un conjunto de anillos, partiendo cada uno desde una de las unidades centrales, de forma que cada uno de los clientes est´e asociado a un ´unico anillo. Como ocurr´ıa para el problema CmRSP, la capacidad de cada anillo est´a limitada por una cota superior Q∈N. Adem´as, para cada nodo central dexiste una cota superior md∈Nque limita el n´umero de anillos que pueden partir de dicho nodo central. Se considera tambi´en que, adem´as del conjunto de clientes, el grafo consta de ciertos nodos de transici´on o nodos de Steiner. Cada uno de los nodos de Steiner puede ser visitado a lo sumo por un anillo. En la Figura 2.8 se ilustra una soluci´on factible para el problema del anillo-estrella multidep´osito. Unidad central Nodos clientes Figura 2.8: Soluci´on factible del problema MDRSP Este problema fue inicialmente propuesto por Baldacci y Dell’Amico (2010), quienes presentaron una formulaci´on como problema de optimizaci´on lineal entera y propusieron diversos procedimientos heur´ısticos para su resoluci´on. Notemos que el MDRSP generaliza el problema RSP, que aparece cuando el conjunto de nodos de Steiner es vac´ıo y existe una ´unica unidad central, el 0, de la que puede partir un ´unico anillo (m0= 1) cuya capacidad l´ımite es, al menos, Q=n. Por tanto, el problema MDRSP es un problema NP-duro. 3 Una transformaci´on del RSP en el problema del viajante generalizado 3.1. Introducci´on En esta secci´on se propone una reformulaci´on del RSP como un problema del viajante generalizado (Generalized Traveling Salesman Problem, GTSP) sobre una red construida apropiadamente. El GTSP se plantea sobre un grafo cuyos nodos est´an distribuidos en varios subconjuntos y resuelve el problema de encontrar un ciclo con el menor coste posible que pasa por todos los subconjuntos dados. Por tanto, el ciclo, adem´as de establecer el orden en el que se visita cada subconjunto, determina tambi´en qu´e nodo o nodos se visita en cada uno de ellos y en qu´e orden. Si cada subconjunto est´a formado por uno de los nodos del grafo sobre el que se plantea el GTSP, el problema queda reducido al problema del viajante cl´asico. El GTSP fue introducido por Srivastava et al. (1969) que presentaron la versi´on sim´etrica del problema y propusieron un algoritmo de resoluci´on mediante programaci´on din´amica. Simult´aneamente, Henry-Labordere (1969) present´o la versi´on asim´etrica del problema. Ambas versiones difieren en el tipo de grafo sobre el que se plantea el problema, ya sea no dirigido o dirigido respectivamente. En la tesis doctoral de Noon (1988) aparece un estudio detallado de este problema, de sus variantes y de algunos de los algoritmos de resoluci´on existentes, tanto exactos como heur´ısticos. Se define, adem´as, la forma can´onica del GTSP en la que se considera que los subconjuntos en los que se divide el conjunto total de nodos son disjuntos, que no hay arcos internos en dichos subconjuntos, es decir arcos que conectan dos nodos del mismo subconjunto, y que un ciclo soluci´on del problema visita cada subconjunto exactamente una vez. Adem´as, si un problema no cumple alguna de estas condiciones, Noon (1988) propone las transformaciones necesarias para convertirlo a la forma can´onica en tiempo polinomial. 27 28 El problema del anillo-estrella En este trabajo nos centraremos en el GTSP asim´etrico, con subconjuntos no necesariamente disjuntos, con la posible existencia de arcos internos y en el que un ciclo debe visitar cada subconjunto una ´unica vez. 3.2. Construcci´on del grafo del problema GTSP transformado Sea G= (V, E ∪A) el grafo del RSP tal y como aparece descrito en la Secci´on 2.1. Se define el conjunto de nodos ˆ V={ij: (i, j)∈A, i 6= 0, i 6=j}. Consideramos el grafo dirigido G0= (V0, A0), donde V0=V∪ˆ V A0=A1∪A2siendo A1={(i, j),(j, i):[i, j]∈E}yA2={(ij, j),(j, ij) : ij∈ˆ V} Los arcos a∈A0tienen asociado el coste c0 aque se asigna de la siguiente manera. A los arcos del conjunto A1, que provienen de los ejes de E, se les asigna el coste cij, a los arcos del conjunto A2que son de la forma (j, ij)∈A0se les asigna coste 0 y a los que son de la forma (ij, j)∈A0se les asigna coste dij. Es decir, c0 ij =cij,c0 ji =cij para todo eje [i, j]∈E c0 ijj=dij,c0 jij= 0 para todo arco (i, j)∈A De esta manera, puede pensarse que los nodos del grafo G0est´an estructurados en dos niveles, el nivel 0 que incluye los nodos originales, es decir el conjunto Vy el nivel 1 en el que est´an los nuevos nodos creados ˆ V. Por la construcci´on del grafo G0, los nodos del nivel 1 no est´an conectados entre s´ı. De hecho, cada nodo ijdel nivel 1 s´olo est´a conectado al resto de nodos mediante dos arcos, uno de entrada y uno de salida, que lo conectan al nodo jdel nivel 0. Si llamamos nal n´umero de nodos del grafo G,mEal n´umero de ejes y mAal n´umero de arcos propios el tama˜no del grafo transformado G0es de n+mAnodos y 2mE+ 2mA arcos. La transformaci´on que se propone en este trabajo establece una equivalencia entre un ciclo Csobre el grafo G0y un anillo Rsobre el grafo G, de manera que Cpasa por el nodo idel nivel 0 si y s´olo si el nodo ipertenece al anillo R, y Cpasa por el nodo ijdel nivel 1 si y s´olo si el nodo ino est´a en Ry est´a asignado al nodo jque s´ı est´a en R. Puesto que Jos´e ´ Angel Iranzo Sanz 29 un anillo Rdel RSP para que sea factible ha de contener el nodo 0, un ciclo equivalente sobre el grafo G0deber´a contener tambi´en el nodo 0, que se encuentra en el nivel 0. En el grafo G0, para cada nodo i∈V, definimos el subconjunto de nodos Sicomo Si={i}∪{ij:ij∈ˆ V}∪{ji:ji∈ˆ V} El GTSP sobre G0consiste en encontrar un ciclo C, no necesariamente simple, que visita exactamente una vez cada uno de los conjuntos Si. Notemos que los conjuntos Sino son disjuntos y que existen arcos en A0cuyos nodos inicial y final est´an contenidos dentro de un mismo Si, por lo que un ciclo que visita una ´unica vez Sipuede contener varios nodos de Si. En otras palabras, un conjunto Sies visitado una ´unica vez si el ciclo correspondiente entra, y por tanto sale, una ´unica vez en el conjunto. En la Figura 3.1, a la izquierda se muestra un grafo Gy a la derecha su correspondiente grafo transformado G0. 12 4 3 0 (a) Grafo para el RSP 3 0 (b) Grafo para el problema transformado GTSP Figura 3.1: Ejemplo de transformaci´on a un problema GTSP Por construcci´on, un ciclo Csoluci´on del GTSP pasa necesariamente por el nodo 0∈V0. Adem´as, para cada nodo i∈V, el ciclo Ccontiene o bien el nodo io bien un ´unico nodo del tipo ij∈ˆ V, ya que todos estos nodos pertenecen a Siy no existen conexiones entre ellos. Los nodos de tipo ij∈ˆ Vpertenecen exactamente a dos subconjuntos, el Siy el Sj, y no pueden aparecer repetidos dentro de un mismo ciclo Csoluci´on factible del GTSP, ya que ijs´olo esta conectado con el nodo jque pertenece s´olo a Sj. Por el contrario, los nodos de tipo i∈Vs´ı pueden aparecer repetidos dentro de un mismo ciclo C, hecho que se ilustra en la Figura 3.2 en la que aparece a la izquierda una soluci´on factible del RSP y a la derecha la soluci´on correspondiente del GTSP sobre el grafo transformado. En cualquier caso, ninguno de los arcos a∈A0puede aparecer repetidos dentro de un mismo ciclo. 30 El problema del anillo-estrella (a) Soluci´on factible para el RSP (b) Soluci´on factible para el GTSP Figura 3.2: Transformaci´on entre una soluci´on del RSP y una del GTSP Notemos que, de esta forma, a cada soluci´on factible Rdel problema RSP se le puede asociar una soluci´on factible Cdel GTSP con el mismo valor de la funci´on objetivo sin m´as que considerar el ciclo formado por los arcos en el nivel 0 correspondientes a los ejes de R, tomados en uno de los dos sentidos posibles, y los arcos del nivel 0 al nivel 1 y viceversa correspondientes a las asignaciones del problema RSP. An´alogamente, a cada soluci´on factible Cdel GTSP se le puede asociar una soluci´on factible Rdel RSP sin m´as que considerar el anillo formado por los ejes correspondientes a los arcos del ciclo Cen el nivel 0. Mediante esta transformaci´on, el problema RSP se puede resolver utilizando las t´ecnicas y algoritmos desarrollados en la literatura para el problema GTSP. As´ı mismo, se han desarrollado transformaciones, como la de Behzad y Modarres (2002), que permiten transformar el problema GTSP en el problema del viajante cl´asico (TSP) y dar la posibilidad, por tanto, de utilizar las t´ecnicas desarrolladas para el TSP para resolver el RSP. 3.3. Formulaci´on matem´atica del problema GTSP transformado Utilizaremos la formulaci´on presentada por Noon (1988) para el problema GTSP general para formular el problema transformado. Puesto que el grafo G0del problema transformado consta de nodos de tipo i∈Vy de tipo ij∈ˆ V, en adelante cuando se utilice la notaci´on de un solo ´ındice (i,j, . . . ) nos estaremos refiriendo a nodos de Vy cuando se utilice la notaci´on ´ındice-sub´ındice (ij,jk, . . . ) nos estaremos refiriendo a nodos de ˆ V. Para cada arco a∈A0, sea zala variable binaria que toma el valor 1 si el arco a Jos´e ´ Angel Iranzo Sanz 31 pertenece al ciclo y el valor 0 en otro caso. Llamaremos subciclo del GTSP a cualquier ciclo no degenerado contenido en la soluci´on {za}a∈A0que no pasa por todos los subconjuntos de nodos Si. Dado un subciclo T, denotaremos Tal conjunto de todos los posibles subciclos y δ(T) al conjunto de arcos de A0cuyo nodo inicial sea un nodo de Ty cuyo nodo final no lo sea. Teniendo en cuenta las caracter´ısticas del grafo transformado G0, el problema GTSP general puede formularse como: min X a∈A0 c0 aza(3.1a) sujeto a X (i,j)∈A0 zij +X (ij,j)∈A0 zijj= 1 ∀i∈V(3.1b) X (j,i)∈A0 zji +X (j,ij)∈A0 zjij= 1 ∀i∈V(3.1c) X (j,ij)∈A0 zjij−X (ij,j)∈A0 zijj= 0 ∀ij∈ˆ V(3.1d) X (j,i)∈A0 zji +X (ji,i)∈A0 zjii− X (i,j)∈A0 zij +X (i,ji)∈A0 ziji = 0 ∀i∈V(3.1e) X a∈δ(T) za≥1∀T∈T(3.1f) xa∈ {0,1} ∀a∈A0(3.1g) La restricci´on (3.1b) establece que para cada subconjunto Siexiste un ´unico arco en el ciclo soluci´on que sale del conjunto y, an´alogamente, la restricci´on (3.1c) establece que existe un ´unico arco de entrada al conjunto Sien el ciclo soluci´on. Las restricciones (3.1d) y (3.1e) aseguran que para cualquier nodo, de ˆ VyVrespectivamente, el n´umero de arcos entrantes del ciclo soluci´on es igual al n´umero de arcos salientes. Por ´ultimo, la restricci´on (3.1f) permite prevenir que sean factibles soluciones con ciclos disjuntos o no conectados. 4 Un algoritmo evolutivo para el RSP Para la resoluci´on del problema RSP se propone en este trabajo un algoritmo gen´etico. Los algoritmos gen´eticos son t´ecnicas de b´usqueda estoc´astica inspiradas por la evoluci´on biol´ogica que sucede en la naturaleza. Fueron introducidos por Holland (1975) y han sido utilizados con ´exito para proporcionar buenas soluciones a un gran n´umero de problemas complejos. Cada soluci´on del problema considerado se codifica como una cadena de s´ımbolos que recibe el nombre de cromosoma o individuo. Cada posici´on de la cadena es un gen y el valor del s´ımbolo que ocupa esa posici´on es un alelo. El algoritmo precisa tambi´en una funci´on ‘fitness’ que eval´ua la calidad de un individuo. Para comenzar el algoritmo, se genera una poblaci´on de individuos y se eval´ua su calidad. En las sucesivas iteraciones, que se corresponden con las generaciones, el algoritmo mantiene una poblaci´on de individuos. A partir de la poblaci´on actual, se generan nuevos individuos (hijos) por la aplicaci´on de operaciones de recombinaci´on (cruce) o mutaci´on. Tras evaluar la calidad de los nuevos individuos, se seleccionan, mediante alg´un criterio, algunos de los padres y de los hijos para formar la nueva poblaci´on. Los distintos algoritmos gen´eticos difieren en la forma de codificaci´on de las soluciones, los operadores que aplican, la funci´on fitness y el criterio de selecci´on de la nueva poblaci´on. Para el problema del anillo estrella se han propuesto en la literatura algunos algoritmos de tipo gen´etico. Renaud et al. (2004) proponen un algoritmo gen´etico que no usa el operador mutaci´on. Liefooghe et al. (2010) proponen un algoritmo gen´etico adaptado al problema del anillo-estrella bi-objetivo. A continuaci´on se describen las caracter´ısticas del algoritmo propuesto. 33 34 El problema del anillo-estrella 4.1. Codificaci´on de los individuos Sea el grafo G= (V, E ∪A) y n=|V|. Sea una soluci´on factible cuyo anillo asociado es R. Inicialmente, se codific´o cada individuo asign´andole el conjunto de nodos por los que pasa el anillo Ral que representa, en el orden en el que se recorren. Puesto que todos los anillos deben contener al nodo 0 y no deben contener nodos repetidos, la codificaci´on ser´ıa de la forma: [0 = r0, r1, r2, . . . , rm] con ri∈V\{0}para todo 1 ≤i≤myri6=rjpara i6=j. Sin embargo, al aplicar un operador de cruce, esta codificaci´on presenta ciertas dificultades para mantener la factibilidad de las soluciones. Por ello, se decidi´o finalmente utilizar la codificaci´on propuesta por Bean (1994). Esta codificaci´on ha sido utilizada para desarrollar diversos algoritmos evolutivos para la resoluci´on de otros problemas de optimizaci´on en los que tambi´en es necesario establecer un orden sobre un cierto subconjunto de nodos, como son el problema del viajante, los problemas de planificaci´on de tareas, los problemas de rutas de veh´ıculos, etc. La codificaci´on de Bean (1994) se basa en un mecanismo de asignaci´on de c´odigos aleatorios. Cada nodo ride un anillo [0 = r0, r1, r2, . . . , rm] tiene asignado un cierto c´odigo xi∈[0,1], de forma que para cualquier par de nodos riyrjdel anillo, si riprecede a rj entonces se tiene que xi≤xj. Por tanto, conocido el conjunto de nodos que pertenecen al anillo y el c´odigo que tiene asignado cada uno de ellos, basta con ordenar los c´odigos en orden creciente para conocer el orden en el que han de recorrerse los nodos del anillo. Si dos o m´as nodos de un anillo tienen asignado el mismo c´odigo, el orden de dichos nodos se decide arbitrariamente. Como estamos interesados en soluciones factibles, en las que el nodo 0 debe pertenecer al anillo correspondiente, asignaremos el c´odigo 0.00 al nodo 0 y para que el 0 sea el primer nodo de la lista de nodos del anillo supondremos, sin p´erdida de generalidad, que el c´odigo del resto de nodos es mayor que 0. Por ejemplo, en un grafo con n= 8 nodos, para codificar el anillo [0,3,7,4], se generan tres n´umeros aleatorios y se ordenan en orden creciente. Supongamos que estos n´umeros son 0.27, 0.35 y 0.54. Este anillo puede representarse entonces como se indica en la Figura 4.1, donde el signo ‘-’ indica que el nodo correspondiente no est´a en el anillo y est´a asignado al nodo del anillo m´as cercano. Como se ver´a m´as adelante, esta codificaci´on de los individuos no plantea problemas de factibilidad al utilizar los operadores de cruce y mutaci´on. La funci´on fitness que permite evaluar la calidad de las soluciones, es decir, de los Jos´e ´ Angel Iranzo Sanz 35 Nodo 0 1 2 3 4 5 6 7 C´odigo 0.00 - - 0.27 0.54 - - 0.35 Figura 4.1: Representaci´on mediante c´odigos de una soluci´on del problema RSP individuos de la poblaci´on, asigna a cada individuo el coste del anillo al que representa, es decir, si un individuo representa el anillo R= (VR, ER) el fitness de dicho individuo es X e∈ER ce+X i∈V\VR min j∈VR dij 4.2. Poblaci´on inicial El tama˜no de la poblaci´on, N∈N, forma parte de los par´ametros de entrada del algoritmo y permanece constante generaci´on tras generaci´on. Para crear un individuo de la poblaci´on inicial se genera un valor sde una variable aleatoria Uniforme en (0,1). A continuaci´on, se selecciona cada uno de los nodos del grafo (excepto el 0) con probabilidad s, se generan tantos c´odigos aleatorios como nodos han sido seleccionados y se asigna a cada nodo seleccionado el c´odigo generado. El individuo se construye entonces con el nodo 0 con el c´odigo 0.00, los nodos seleccionados con sus respectivos c´odigos y los nodos no seleccionados sin c´odigo. Inicialmente se probaron tambi´en otras formas de generar la poblaci´on inicial que fueron descartadas porque proporcionaban peores resultados experimentales. Entre estas formas se prob´o, por ejemplo, fijar la probabilidad sa priori, pero se ha observado que se obtiene entonces una poblaci´on inicial sesgada que hace que el algoritmo converja inicialmente de forma m´as lenta. En particular, el criterio de tomar una probabilidad fija s= 0.5 fue utilizado por Liefooghe et al. (2010) al resolver el problema del anillo-estrella bi-objetivo mediante algoritmos evolutivos. 4.3. Operador de cruce o recombinaci´on En el algoritmo propuesto se utiliza un operador de tipo cruce en un punto. Dados dos individuos de la poblaci´on, denominados padres, que est´an codificados como se ha indicado en el Secci´on 4.1, el operador de cruce en un punto se define de forma natural. En primer lugar, se selecciona aleatoriamente una posici´on para realizar el cruce, que divide cada uno de los dos individuos padres en dos partes. Para obtener los dos hijos resultantes, se combina la primera parte del primer padre con la segunda parte del segundo padre 42 El problema del anillo-estrella Figura 4.4: Mejor soluci´on encontrada, grafo con 50 nodos Figura 4.5: Mejor soluci´on encontrada, grafo con 100 nodos Jos´e ´ Angel Iranzo Sanz 43 Figura 4.6: Mejor soluci´on encontrada, grafo con 200 nodos 200 nodos se ha obtenido que, tras 10 ejecuciones, se consigue un fitness medio de 29.91, es decir, algo menor que el fitness medio obtenido mediante el criterio de parada inicial en la misma situaci´on. El tiempo medio del algoritmo en este caso aumenta hasta los 301.09 segundos y la ´ultima mejora se realiza, en media, alrededor de la iteraci´on 5014. En la Figura 4.7 puede verse una gr´afica en el que se muestra la velocidad con la que decrece el valor medio del fitness del mejor anillo a medida que transcurren las iteraciones. iteración fitness Figura 4.7: Resultados para n= 200 y N= 100 durante 104iteraciones Para dar una idea del error que se comete al resolver un problema mediante este algoritmo se han seleccionado varios problemas para los que se conoce una soluci´on exacta, 44 El problema del anillo-estrella en la mayor´ıa de los casos, o muy pr´oxima. Los grafos sobre los que se ha resuelto el problema RSP han sido seleccionados del conjunto de problemas TSPLIB (Reinelt (1991)) que contiene grafos con entre 50 y 200 nodos con formato 2-dimensional. Los costes de los arcos y los ejes han sido definidos para obtener soluciones que visitan aproximadamente el 100 %, el 75 %, el 50 % y el 25 % del total de nodos del grafo, de forma que para cada par de nodos i, j ∈Vse define cij =dωlijeydij =d(10 −ω)lijepara ω∈ {3,5,7,9}, siendo lij la distancia eucl´ıdea entre los nodos iyj. Los par´ametros de entrada del algoritmo evolutivo son α=3 n,β= 10−2,C=d0.01ne, ε= 10−10 yM= 104. El n´umero de individuos de la poblaci´on utilizada en el algoritmo es, en todos los casos, M= 100. Los grafos de la base de datos TSPLIB sobre los que se han realizado las pruebas son el eil51,rd100 y el kroA200, con 51, 100 y 200 nodos respectivamente. Ejecutando diez veces el algoritmo para cada una de las configuraciones posibles se obtiene la Tabla 4.3 de resultados, que contiene los siguientes datos: Grafo: Nombre del grafo sobre el que se aplica el algoritmo evolutivo. ω: Par´ametro de proporcionalidad para los costes de ejes y arcos. ´ Optimo: Valor ´optimo encontrado por Labb´e et al. (2004), salvo los casos marcados con * en los que se trata de una cota superior. Tiempo: Tiempo medio de c´alculo hasta que el algoritmo se detiene (en segundos). Fitness: Valor medio, m´ınimo y m´aximo del mejor fitness encontrado. %Error: Porcentaje de error relativo medio y m´ınimo. El porcentaje de error relativo se calcula como 100(fit−opt)/opt siendo opt la soluci´on dada por el algoritmo de ramificaci´on y acotaci´on descrito en Labb´e et al. (2004) y fit la soluci´on heur´ıstica obtenida mediante este algoritmo evolutivo. La soluci´on dada por su algoritmo de ramificaci´on y acotaci´on no es la ´optima en todos los casos, ya que ejecutaron el algoritmo durante un tiempo m´aximo de dos horas por problema. Los valores negativos que aparecen en las columnas de %Error corresponden a problemas en los que la soluci´on heur´ıstica del algoritmo evolutivo es mejor que la soluci´on encontrada por el algoritmo de ramificaci´on y acotaci´on en dos horas. Notemos que, en general, en las pruebas realizadas el algoritmo tiende a dar mejores resultados a medida que aumenta el coste de los ejes con respecto al coste de los arcos. Tambi´en se ha obtenido un error menor para los grafos con mayor n´umero de nodos, mejorando en algunos casos las cotas superiores de la soluci´on ´optima que obtuvieron Labb´e et al. (2004) tras dos horas de c´alculo. Jos´e ´ Angel Iranzo Sanz 45 Grafo ω´ Optimo Tiempo Fitness % Error medio m´ınimo m´aximo medio m´ınimo eil51 3 1278 3,8 1358,7 1314 1404 6,31 2,82 5 1995 3,3 2102,9 2084 2148 5,41 4,46 7 2113 2,3 2167,3 2163 2178 2,57 2,37 9 1244 0,8 1280 1280 1280 2,89 2,89 rd100 3 23730 10,1 25041,1 23944 26001 5,53 0,90 5 37975 10,0 38733,9 38075 39733 2,00 0,26 7 40915 6,9 41168,6 41042 41417 0,62 0,31 9 31776 5,3 32601,6 32434 32789 2,60 2,07 kroA200 3 93699* 202,2 93925,2 92012 95810 0,24 -1,80 5 138885* 61,0 143808 140844 148639 3,54 1,41 7 158227 74,4 160230 158452 163382 1,27 0,14 9 124678* 45,3 123581 122808 124394 -0,88 -1,50 Tabla 4.3: Resultados experimentales sobre grafos de la TSPLIB 46 El problema del anillo-estrella Jos´e ´ Angel Iranzo Sanz 47 Bibliograf´ıa R. Baldacci y M. Dell’Amico. Heuristic algorithms for the multi-depot ring-star problem. European Journal of Operational Research, 203(1):270–281, 2010. R. Baldacci, M. Dell’Amico y J.J. Salazar Gonz´alez. The capacitated m-ring-star problem. Operations Research, 55(6):1147–1162, 2007. P. Bauer. The circuit polytope: Facets. Mathematics of Operations Research, 22(1): 110–145, 1997. J.C. Bean. Genetic algorithms and random keys for sequencing and optimization. Informs Journal on Computing, 6(2):154–160, 1994. A. Behzad y M. Modarres. A new efficient transformation of the generalized traveling salesman problem into traveling salesman problem. En Proceedings of the 15th International Conference of Systems Engineering, pp. 6–8, 2002. G.A. Croes. A method for solving traveling-salesman problems. Operations Research, 6 (6):791–812, 1958. T. Dias, G. de Sousa Filho, E. Macambira, L. dos Anjos F. Cabral y M. Fampa. An efficient heuristic for the ring star problem. En C. ´ Alvarez y M. Serna, editores, Experimental Algorithms, volumen 4007 de Lecture Notes in Computer Science, pp. 24–35. Springer, 2006. M. Ehrgott. Multicriteria optimization. Springer Verlag, Berlin, Heildeberg, 2005. M. Fischetti, J.J. Salazar Gonz´alez y P. Toth. A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Operations Research, 45(3):378–394, 1997. A.L. Henry-Labordere. The record balancing problem: A dynamic programming solution of a generalized traveling salesman problem. RAIRO Operations Research, B2:43–49, 1969. J.H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI, 1975. F.K. Hwang y D.S. Richards. Steiner tree problems. Networks, 22(1):55–89, 1992. R.M. Karp. Reducibility among combinatorial problems. Complexity of Computer Computations, pp. 85–103, 1972. S. Kedad-Sidhoum y V.H. Nguyen. An exact algorithm for solving the ring star problem. Optimization, 59(1):125–140, 2010. T. Koch y A. Martin. Solving Steiner tree problems in graphs to optimality, volumen 32. 1998. M. Labb´e, G. Laporte, I. Rodr´ıguez Mart´ın y J.J. Salazar Gonz´alez. The ring star problem: Polyhedral analysis and exact algorithm. Networks, 43(3):177–189, 2004. 48 El problema del anillo-estrella M. Labb´e, G. Laporte, I. Rodr´ıguez Mart´ın y J.J. Salazar Gonz´alez. Locating median cycles in networks. European Journal of Operational Research, 160(2):457–470, 2005. Y. Lee, S.Y. Chiu y J. S´anchez. A branch and cut algorithm for the Steiner ring star problem. International Journal of Management Science, 4(1):21–34, 1998. A. Liefooghe, L. Jourdan y E.G. Talbi. Metaheuristics and cooperative approaches for the bi-objective ring star problem. Computers and Operations Research, 37(6):1033–1044, 2010. S. Lin. Computer solutions of the traveling salesman problem. Bell System Technical Journal, (44):2245–2269, 1965. A. Mauttone, S. Nesmachnow, A. Olivera y F. Robledo. A hybrid metaheuristic algorithm to solve the capacitated m-ring star problem. En Proceedings of the International Network Optimization Conference (INOC 2007). Spa, Belgium, 2007. Z. Naji-Azimi, M. Salari y P. Toth. A heuristic procedure for the capacitated m-ring-star problem. European Journal of Operational Research, 207(3):1227–1234, 2010. G.L. Nemhauser y L.A. Wolsey. Integer and Combinatorial Optimization. Wiley, New York, 1999. Ch.E. Noon. The generalized traveling salesman problem. PhD thesis, University of Michigan, 1988. J.A. Moreno P´erez, M.V. Marcos y I. Rodr´ıguez Mart´ın. Variable neighborhood tabu search and its application to the median cycle problem. European Journal of Operational Research, 151(2):365–378, 2003. G. Reinelt. Tsplib–a traveling salesman problem library. INFORMS Journal on Computing, 3(4):376–384, 1991. J. Renaud, F.F. Boctor y G. Laporte. Efficient heuristics for median cycle problems. Journal of the Operational Research Society, 55(2):179–186, 2004. M.G.C. Resende y C.C. Ribeiro. Grasp with path-relinking: Recent advances and applications. En T. Ibaraki, K. Nonobe y M. Yagiura, editores, Metaheuristics: Progress as Real Problem Solvers, pp. 29–63. Springer, 2005. L. Simonetti, Y. Frota y C.C. de Souza. The ring-star problem: A new integer programming formulation and a branch-and-cut algorithm. Discrete Applied Mathematics, In press, doi:10.1016/j.dam.2011.01.015, 2011. S. Srivastava, S. Kumar, R.C. Garg y P. Sen. Generalized traveling salesman problem through nsets of nodes. Journal of the Canadian Operational Research Society, 7: 97–101, 1969. R.T. Wong. A dual ascent approach for Steiner tree problems on a directed graph. Mathematical Programming, 28(3):271–287, 1984. Anexo I: C´odigo C++ 49 Archivo: /main.cpp Página 1 de 2 #include <iostream> #include <stack> #include <stdlib.h> #include <Anillo.h> using namespace std; /*En este archivo se muestra el conjunto de ordenes escritas en C++ para la resolución del problema RSP sobre grafos aleatorios generados en el conjunto [0,1]x[0,1]. El coste de ejes y arcos es proporcional a la distancia euclídea entre los distintos nodos*/ int main(int argc, char *argv[]){ double d1, d2, mediaPob; int k, r1, r2; double itMax; int n;//Número de nodos de la red int tamPob;//Tamaño de la población double beta;//Porcentaje de la población que pasa directamente a la siguiente generación double pMutacion;//Probabilidad de mutación double factor;//Factor que multiplica el coste de los ejes: c_ij = factor * d_ij double eps;//Diferencia minima entre el fitness del mejor anillo y la media de la poblacion GNUplot plotter;// Sirve para dibujar el grafo (es necesario tener instalado GnuPlot) //Lectura de datos o inicialización por defecto n= argc>1? atoi(argv[1]) : 100; tamPob= argc>2? atoi(argv[2]) : 50; beta= argc>3 ? atof(argv[3]) : 0.01; pMutacion= argc>4? atof(argv[4]) : 1./double(n); itMax=argc>5? atoi(argv[5]) : 1e4; factor=argc>6? atoi(argv[6]) : 5; eps=argc>7? atoi(argv[7]) : 1e-4; vector<pair<double, double> >puntos(n);//Coordenadas de los nodos de la red vector<vector<double> > coste(n);//Distancias euclideas entre los puntos stack<Anillo> hijos;//Hijos multiset<Anillo> poblacion;//Población vector< multiset<Anillo>::const_iterator> posPob(tamPob); //Generación de puntos aleatorios set_random(2);//Semilla fija para la creación del grafo for(int i=0; i<n;i++){ puntos[i]=make_pair(rand01(),rand01()); coste[i].resize(n); } //Cálculo de costes for(int i=0; i<n; i++){ for(int j=0; j<n; j++){ d1=puntos[i].first-puntos[j].first; d2=puntos[i].second-puntos[j].second; coste[i][j]=coste[j][i]=sqrt(d1*d1+d2*d2); } } //Cambio de semilla (para resolver un mismo problema con distintas poblaciones) set_random(time(0)); //Llamada a la función de inicialización de los anillos Anillo::setCostes(coste,factor); //Inicio del Algoritmo Evolutivo clock_t tiempo=clock(); Anillo mejorAnillo; //Generación de la población inicial aleatoria for(int i=0; i<tamPob; i++) poblacion.insert(Anillo()); //Recombinaciones + Mutación + Búsqueda local Jos´e ´ Angel Iranzo Sanz 51 Archivo: /gnuplot.h Página 1 de 1 #ifndef GNUPLOT_H_ #define GNUPLOT_H_ #include <fstream> using namespace std; class GNUplot{ public: GNUplot() throw(string); ~GNUplot(); void operator ()(const string& command); protected: FILE *gnuplotpipe; }; #endif 58 El problema del anillo-estrella Archivo: /gnuplot.cpp Página 1 de 1 #include "gnuplot.h" using namespace std; GNUplot::GNUplot()throw(string){ gnuplotpipe=popen("gnuplot -persist","w"); if(!gnuplotpipe){ throw("¡No se encontro GNUPLOT!"); } } GNUplot::~GNUplot(){ fprintf(gnuplotpipe,"exit\n"); pclose(gnuplotpipe); } void GNUplot::operator()(const string& command){ fprintf(gnuplotpipe,"%s\n",command.c_str()); fflush(gnuplotpipe); } Jos´e ´ Angel Iranzo Sanz 59 Archivo: /MisFunciones.h Página 1 de 1 #ifndef HEADER_MISFUNCIONES #define HEADER_MISFUNCIONES #include <fstream> #include <math.h> const std::string doubleToStr(const double & k); void set_random(long); long random2(long, long); double rand01(); #endif 60 El problema del anillo-estrella Archivo: /MisFunciones.cpp Página 1 de 1 #include<MisFunciones.h> const std::string doubleToStr(const double & k){ char resultado[15]; sprintf( resultado, "%f", k ); return resultado; } //GENERADOR DE NÚMEROS ALEATORIOS sacado de NETGEN /*** This is a portable random number generator whose origins are *** unknown. As far as can be told, this is public domain software.*/ /*** portable random number generator */ /*** Note that every variable used here must have at least 31 bits *** of precision, exclusive of sign. Long integers should be enough. *** The generator is the congruential: i = 7**5 * i mod (2^31-1). ***/ #define MULTIPLIER 16807 #define MODULUS 2147483647 static long saved_seed; /*** set_random - initialize constants and seed */ void set_random(long seed){ saved_seed = seed; random2(0,1e3);//Sirve para desechar el primer random que depende mucho de la semilla } /*** random - generate a random integer in the interval [a,b] (b >= a >= 0) */ long random2(long a, long b){ register long hi, lo; hi = MULTIPLIER * (saved_seed >> 16); lo = MULTIPLIER * (saved_seed & 0xffff); hi += (lo>>16); lo &= 0xffff; lo += (hi>>15); hi &= 0x7fff; lo -= MODULUS; if ((saved_seed = (hi<<16) + lo) < 0) saved_seed += MODULUS; if (b <= a) return b; return a + saved_seed % (b - a + 1); } /*** rand01 - genera un número aleatorio en (0,1) */ double rand01(){ return double(random2(1,1e9))/double(1e9+1); } Jos´e ´ Angel Iranzo Sanz 61