Estudio de técnicas de búsqueda por vecindad a muy gran escala

Ravindra K. Ahuja Departamento de ingeniería industrial y de sistemas Universidad de Florida Gainesville, FL 32611, USA [email protected]

Özlem Ergun Centro de investigación operativa Instituto tecnológico de Massachussets Cambridge, MA 02139, USA [email protected]

James B. Orlin Escuela Sloan de dirección Instituto tecnológico de Massachussets Cambridge, MA 02139, USA [email protected]

Abraham P. Punnen Departamento de matemáticas, estadística y ciencias informáticas Universidad de New Brunswick Saint John, New Brunswick, Canada E2L 4L5 [email protected]

(22 de julio de 1999) (Revisado el 11 de octubre de 2000)

1

Estudio de técnicas de búsqueda por vecindad a muy gran escala

Ravindra K. Ahuja, Özlem Ergun, James B. Orlin, Abraham P. Punnen Resumen Muchos problemas de optimización de interés práctico resultan intratables mediante técnicas de cálculo. Ante esta dificultad, los algoritmos heurísticos (o de aproximación) se revelan como un medio útil para su resolución, ya que permiten obtener soluciones casi óptimas en un tiempo razonable. Los algoritmos de mejora son algoritmos heurísticos que, por lo general, parten de una solución factible y tratan de hallar, por medio de iteraciones, una solución aún mejor. Los algoritmos de búsqueda por vecindad (también llamados algoritmos de búsqueda local) constituyen un tipo bastante amplio de algoritmos de mejora en los que en cada iteración se obtiene una solución mejorada buscando en la "vecindad" de la solución existente. Un aspecto crítico del diseño de esta clase de algoritmos es la elección de la estructura de la vecindad; es decir, el modo en el que se va a definir ésta. Como regla general, cuanto más amplia sea la vecindad, mayor será tanto la calidad de las soluciones localmente óptimas como la precisión de la solución final que se obtenga. Pero, al mismo tiempo, cuanto más amplia sea la vecindad, más tiempo será necesario para realizar la búsqueda dentro de ella en cada iteración. Por esta razón, una vecindad muy amplia produce necesariamente una heurística más eficaz, a menos que la búsqueda se realice de un modo muy eficiente. El presente estudio se concentra en algoritmos de búsqueda local en los que el tamaño de la vecindad es “muy grande” con respecto al tamaño de los datos y en los que la búsqueda local se hace con criterios de máxima eficiencia. En él se analizan tres tipos muy amplios de algoritmos de búsqueda por vecindad a muy gran escala (VLSN: Very Large-Scale Neighborhood): (1) métodos de profundidad variable en los que la búsqueda local se realiza de modo heurístico, (2) aplicación de la programación dinámica o de técnicas de flujo de redes a vecindades amplias, y (3) vecindades grandes inducidas por restricciones del problema original que pueden resolverse en tiempo polinómico.

1. Introducción Muchos problemas de optimización de interés práctico resultan intratables mediante técnicas de cálculo. Ante esta dificultad, los algoritmos heurísticos (o de aproximación) se revelan como un medio útil para su resolución, ya que permiten obtener soluciones casi óptimas en un tiempo razonable. Los trabajos dedicados a algoritmos heurísticos suelen dividir éstos en dos amplias categorías: algoritmos de construcción (o constructivos) y algoritmos de mejora. Los primeros montan una solución partiendo de cero, mediante la asignación de valores a una o varias variables de decisión al mismo tiempo, mientras que los algoritmos de mejora parten de una solución factible y tratan de hallar una

2

mejor por medio de iteraciones. Los algoritmos de búsqueda por vecindad (también llamados algoritmos de búsqueda local) constituyen un tipo bastante amplio de algoritmos de mejora en los que en cada iteración se obtiene una solución mejorada buscando en la "vecindad" de la solución existente. El presente estudio se concentra en algoritmos de búsqueda local en los que el tamaño de la vecindad es “muy grande” con respecto al tamaño de los datos y en los que la búsqueda local se hace con criterios de máxima eficacia. En instancias grandes de problemas, la búsqueda de este tipo de vecindades de modo explícito resulta poco práctica, lo que hace necesario realizar la búsqueda en un segmento más pequeño de la vecindad o bien desarrollar algoritmos que resulten eficaces en búsquedas de modo implícito en la vecindad. Un aspecto crítico del diseño de esta clase de algoritmos es la elección de la estructura de la vecindad (es decir, el modo en el que se va a definir ésta), ya que del tipo de estructura que se elija dependerá el que la búsqueda de vecindad desarrolle soluciones altamente precisas o soluciones con óptimos locales muy pobres. Como regla general, cuanto más amplia sea la vecindad, mayor será tanto la calidad de las soluciones localmente óptimas como la precisión de la solución final que se obtenga. Pero, al mismo tiempo, cuanto más amplia sea la vecindad, más tiempo será necesario para realizar la búsqueda dentro de ella en cada iteración. Dado que se suelen ejecutar varios algoritmos de búsqueda local con distintos puntos de partida, la mayor duración de los tiempos de ejecución para cada iteración requiere un menor número de ejecuciones por tiempo unitario. Por esta razón, una vecindad muy amplia produce necesariamente una heurística más eficaz, a menos que la búsqueda se realice de un modo muy eficiente. Varios de los métodos más utilizados por su alta eficiencia en investigación operativa pueden entenderse como técnicas de búsqueda por vecindad a gran escala. Así, por ejemplo, si contemplamos el algoritmo simplex para la resolución de programas lineales como un algoritmo de búsqueda local, tendremos que la generación de columnas es a su vez un método de búsqueda por vecindad a gran escala, al igual que ocurre con las técnicas de extrapolación empleadas para la resolución de muchos problemas de flujo de redes. El algoritmo de cancelación del ciclo de coste negativo que se usa para resolver el problema del flujo de coste mínimo y el algoritmo del camino de aumento que resuelve problemas de ajuste son dos ejemplos de ello. En el presente estudio, hemos clasificado los métodos de vecindad a gran escala en tres categorías que pueden coincidir parcialmente. La primera de ellas comprende los métodos de profundidad variable: una serie de algoritmos que se centran en vecindades exponencialmente grandes en las que realizan búsquedas parciales por medio de la heurística. La segunda categoría comprende algoritmos de mejora basados en flujos de red; métodos de búsqueda local que emplean técnicas de flujo de red para identificar posibilidades de mejora en la vecindad. Por último, en la tercera categoría se analizan vecindades para problemas NP-difíciles inducidos por subconjuntos de restricciones de los problemas que se pueden resolver en tiempo polinómico. Aunque hemos introducido el concepto de búsqueda por

3

vecindad a gran escala al hacer referencia a técnicas de generación de columnas para programas lineales y a técnicas de extrapolación para flujos de redes, no se insiste sobre los programas lineales. Por el contrario, el estudio se concentra en la aplicación de técnicas de búsqueda por vecindad a gran escala a problemas de optimización NP-difíciles. Esta monografía se halla estructurada del modo que a continuación se describe. En el apartado 2 se incluye una breve descripción general de la búsqueda local. El apartado 3 comprende un análisis de métodos de profundidad variable. El apartado 4 trata sobre algoritmos de búsqueda por vecindad a gran escala basados en técnicas de flujo de redes. En el apartado 5 se analizan técnicas eficientes para la resolución de supuestos especiales de problemas NP-difíciles de optimización combinatoria, así como de vecindades muy amplias basadas en ellos. El apartado 6 describe las mediciones de vecindades, que pueden servir de guía para el desarrollo de algoritmos de búsqueda local con respecto a una vecindad dada. Por último, en el apartado 7 se analiza el rendimiento computacional de varios de los algoritmos vistos en los apartados anteriores.

2. Búsqueda local: esquema general Comenzaremos por introducir formalmente un problema de optimización combinatoria, junto con el concepto de vecindad. Existen diversas maneras de representar este tipo de problemas, todas ellas basadas en métodos de representación del conjunto de soluciones factibles. En este apartado, representaremos el conjunto de soluciones factibles como subconjuntos de un conjunto finito, formulándolo del siguiente modo: Sea E = {1, 2,..., m} un conjunto finito. En general, la cardinalidad de un conjunto S se indica mediante |S|. Supongamos, además, que F ⊆ 2E, donde 2E indica el conjunto formado por todos los subconjuntos de E. Los elementos de F se denominan soluciones factibles. Sea f: F → ℜ, llamándose a la función f la función objetivo. Con estos datos, una instancia de un problema de optimización combinatoria (POC) se representará del siguiente modo: Minimizar {f(S) : S ∈ F}. Damos por hecho que la familia F no nos viene dada explícitamente mediante el listado de todos sus elementos; sino que se halla representada en una forma compacta de tamaño polinómico en m. El par (F, f) indica una instancia de un problema de optimización combinatoria. En la mayor parte de los problemas que veremos, la función de coste es una función lineal; es decir, existe un vector f1, f2,…, fm tal que, para todos los conjuntos factibles, S, f(S) = Σi∈Sfi. Supongamos que (F, f) es una instancia de un problema de optimización combinatoria. La función de vecindad es un punto de definición del mapa N: F→ 2E. En esta función, cada valor de S

4

∈

F tiene

asociado un subconjunto N(S) de E. El conjunto N(S) recibe el nombre de vecindad de la solución S, y podemos suponer, sin pérdida de generalidad, que S

∈

N(S). Se dice que una solución S*

∈

F es

localmente óptima con respecto a una función de vecindad N cuando f(S*) ≤ f(S) para todo S ∈ N(S*). Asimismo, se dice que N(S) es exponencial cuando |N(S)| crece de manera exponencial en m a medida que el valor de esta última se incrementa. A lo largo de la mayor parte de este estudio, veremos vecindades de tamaño exponencial, además de vecindades cuyo tamaño es demasiado amplio para realizar en ellas búsquedas explícitas en la práctica. Así, por ejemplo, una vecindad con m3 elementos resultará demasiado amplia para una búsqueda en la práctica si m tiene un valor alto (por ejemplo, superior a un millón). Nos referiremos a las técnicas de búsqueda por vecindad empleando dichas vecindades como algoritmos de búsqueda por vecindad a muy gran escala o algoritmos de búsqueda VLSN. Para dos soluciones S y T, llamaremos S – T al conjunto de elementos que se encuentran en S pero no en T. La distancia d(S, T) la definiremos como |S - T| + |T - S|, que es el número de elementos de E que se encuentran en S o en T, pero no en ambos. Ocasionalmente, podremos permitir que las vecindades incluyan también soluciones no factibles. Por ejemplo, en el caso anterior podemos hacer que la vecindad de un recorrido incluya cada uno de los itinerarios obtenidos mediante la supresión de uno de los vértices del mismo. Para resaltar el hecho de que una vecindad contenga otros elementos además del itinerario, daremos, como norma general, una descripción combinatoria de las soluciones no factibles permitidas en la búsqueda. Nos referiremos a estas estructuras combinatorias no factibles como estructuras de referencia. Un camino de Hamilton sería un ejemplo de este tipo de estructuras. Podemos imaginar un algoritmo de búsqueda por vecindad (para un problema de minimización de costes)como compuesto de tres partes: (i) Un grafo de vecindad (NG) definido con respecto a una instancia de problema específica, donde NG es un grafo dirigido con un nodo para cada solución factible que se cree (o una instancia de una estructura de referencia no factible), y que consta de un arco (S, T) siempre que T ∈ N(S). (ii) Un método de búsqueda del grafo de vecindad en cada iteración. (iii) Un método que permita determinar cuál es el siguiente nodo del grafo de vecindad que se elegirá en la búsqueda del paso anterior. Nos referiremos a este nodo como solución básica. El algoritmo termina cuando S es una solución localmente óptima con respecto a la vecindad dada. (Véase [1] para un estudio extensivo). A continuación definiremos dos vecindades basadas en la distancia. La primera es Nk(S) = {T ∈ F : d(S, T) ≤ k}. Nos referiremos a estas vecindades como vecindades de distancia-k.

5

En determinadas instancias de problemas, dos soluciones factibles cualesquiera tienen la misma cardinalidad, como ocurre en el problema del viajante de comercio (TSP: Travelling Salesman Problem), donde cada solución factible S representa un recorrido en un grafo completo por un número n de ciudades, por lo que tiene un número n de arcos (véase [48] para más detalles sobre el TSP). Como regla general, afirmamos que se puede obtener T mediante un intercambio simple de S cuando |S - T| = |T - S| = 1; y que se puede obtener mediante un k-intercambio cuando |T - S| = |S - T| = k. Definimos la vecindad de k- intercambios de S como {T : |S - T| = |T - S| ≤ k}. Si dos soluciones factibles cualesquiera tienen la misma cardinalidad, la vecindad de k-intercambios de S será igual a N2k(S). Un ejemplo típico de vecindad de k-intercambios aplicada al problema del viajante de comercio es la vecindad de doble intercambio, también conocida como vecindad 2-opt. En el grafo correspondiente a ella, cada uno de los nodos representa un recorrido, y dos recorridos serán vecinos cuando se pueda obtener uno a partir del otro mediante un intercambio doble. Aplicando un método de búsqueda exhaustiva (o con algunos atajos), la siguiente solución básica será una solución de mejora. De Nm(S) = F, se desprende que realizar búsquedas en la vecindad de distancia k puede resultar más complicada a medida que el valor de k aumente. Por lo general, ocurre que esta vecindad crece exponencialmente cuando k no es un valor fijo, y que hallar la mejor solución (o incluso una solución mejorada) es NP-difícil cuando el problema original es también NP-difícil.

3. Métodos de profundidad variable Para k = 1 ó 2, se pueden realizar búsquedas eficaces en las vecindades de k-intercambios (o, de modo similar, las de distancia k), aunque la media de los óptimos locales que se obtienen suele resultar insuficiente. En cambio, para valores más altos de k, las vecindades de k-intercambios producen mejores óptimos locales, pero el esfuerzo necesario para realizar la búsqueda puede ser excesivo. Los métodos de profundidad variable son técnicas que permiten realizar búsquedas parciales en las vecindades de kintercambios. El objetivo de esta búsqueda parcial consiste en hallar soluciones que sean vecinas en el valor de la función objetivo a los óptimos globales, y que a la vez sean capaces de reducir drásticamente el tiempo de búsqueda en la vecindad, si bien no suelen garantizar óptimos locales. En los algoritmos de búsqueda por vecindad a muy gran escala, entran en juego varios tipos de algoritmos para realizar búsquedas parciales en la vecindad de k-intercambios. En este apartado analizaremos el algoritmo de Lin y Kernighan [50] para el TSP, así como otras heurísticas de profundidad variable aplicadas a búsquedas en vecindades de k-intercambio en distintos problemas de optimización combinatoria. El apartado siguiente está dedicado a la descripción de otros enfoques que, en tiempo polinómico, permiten realizar búsquedas de modo implícito en un subconjunto de tamaño exponencial de la vecindad de k-intercambio cuando k no es un valor fijo.

6

Antes de pasar a describir el algoritmo de Lin y Kernighan, veremos algunos aspectos relativos a la notación. Posteriormente, explicaremos el modo de generalizar dicho algoritmo a métodos de profundidad variable (y a "ejection chains") para resolver heurísticamente problemas de optimización combinatoria. Supongamos que T y T’ son subconjuntos de E, aunque no necesariamente factibles. Una ruta que vaya de T a T’ será una secuencia T = T1, …, TK = T’ tal que d(Tj, Tj+1) = 1 para j = 1 a K - 1. Los métodos de profundidad variable se basan en una subrutina Move que tiene las siguientes características: 1. En cada iteración, esta subrutina crea un subconjunto Tj y posiblemente también un subconjunto factible Sj a partir del par de entrada (Sj-1,Tj-1) conforme a determinados criterios de búsqueda. El subconjunto Tj puede ser factible o no serlo. Representaremos esta operación como Move (Sj-1,Tj-1) = (Sj, Tj) 2. d(Tj, Tj+1) = 1 para todo j = 1 a K - 1. 3. Tj cumple las propiedades adicionales, dependiendo del enfoque de profundidad variable. Llamemos T al recorrido actual del problema del viajante de comercio, suponiendo, sin pérdida de generalidad, que T visita las ciudades siguiendo el orden 1, 2, 3,…, n, 1. Podemos definir la vecindad de intercambio-2 para T como la sustitución de los vértices (i, j), y (k, l) por otros dos; (i, k) y (j, l), o bien (i, l) y (j, k) para formar otro recorrido T’. Obsérvese que d(T, T’) = 4. La vecindad de intercambio-2 se puede describir de un modo más formal aplicando 4 operaciones de la subrutina Move, en las que la primera de ellas suprime del recorrido el vértice (i, j), la segunda inserta el vértice (i, k), la tercera suprime el vértice (k, l) y la cuarta y última inserta el vértice (j, l). Llamemos G = (N, A) a un grafo no dirigido en los nodos n; y P = v1,

…,

vn a un camino de

Hamilton de G con n nodos. Por otra parte, un stem and cycle (término acuñado por Glover [30]) es un subgrafo expandido de n arcos que se obtiene añadiendo un arco (i, j) a un camino de Hamilton, en el que i es un nodo extremo del camino. Obsérvese que, al ser i y j los nodos extremos del camino, la estructura stem and cycle es un ciclo de Hamilton, o, de modo equivalente, un recorrido. Si T es un camino o una estructura del tipo mencionado, indicaremos su longitud total por medio de f(T). La heurística de Lin y Kernighan permite la sustitución de un total de n vértices al moverse de un recorrido S a un recorrido T; es decir, d(S, T) equivale a un valor arbitrario k = 2n. El algoritmo comienza por suprimir un vértice del recorrido original T1 construyendo un camino de Hamilton T2. En lo sucesivo, uno de los puntos extremos de T2 será constante y permanecerá constante hasta el fin de la iteración. El otro punto extremo se selecciona al comenzar la búsqueda. El movimiento par inserta un extremo en el camino de Hamilton T2j que incide en el punto extremo no constante para obtener una

7

estructura stem and cycle T2j+1. Por su parte, los movimientos impares de la iteración suprimen un extremo de la estructura stem and cycle existente T2j-1 para obtener un camino de Hamilton T2j. De cada camino de Hamilton T2j se construye implícitamente un recorrido factible S2j uniendo los dos nodos extremos. Al final de la iteración de Lin y Kernighan obtenemos el nuevo recorrido de la solución base Si, de modo que f(Si) =f(S2j) para todo j. A continuación describiremos con mayor detalle los pasos del algoritmo de Lin y Kernighan. Cuando se produce un movimiento par, el vértice que se va a añadir es el de longitud mínima, que incide sobre el punto extremo no constante, lo que se añade al camino de Hamilton T2j únicamente si f(S)-f(T2j+1) > 0. El algoritmo de Lin y Kernighan [50] describe también un medio de mejorar la forma de elegir este vértice. La elección del vértice que se va a añadir al camino de Hamilton T2j se realiza maximizando f(T2j) – f(T2j+2). Por otra parte, los vértices que se van a suprimir en los movimientos impares vienen determinados exclusivamente por la estructura stem and cycle T2j-1 creada en el movimiento anterior, de modo que T2j sea un camino de Hamilton. A la hora de elegir los vértices que se van a añadir, también se pueden tener en cuenta otras restricciones. Varios estudios han considerado distintas combinaciones de restricciones, como que un vértice ya suprimido no se pueda volver a añadir o que un vértice añadido previamente no pueda suprimirse en un movimiento posterior. Por último, el algoritmo de Lin y Kernighan termina con un óptimo local cuando no hay posibilidad de construir un recorrido que lo mejore tras considerar todos los nodos como el nodo fijo original. Veamos una ilustración del algoritmo de Lin y Kernighan con un ejemplo numérico, partiendo del recorrido de 10 nodos que muestra la figura 1(a). El algoritmo suprime primero el arco (1, 2) creando el camino de Hamilton de la figura 1(b). A continuación se añade el arco (2, 6), lo que da como resultado la estructura stem and cycle de la figura 1(c).

8

Figura 1. Ilustración del algoritmo de Lin y Kernighan (a) Recorrido con 10 nodos. (b) Camino de Hamilton. (c) Estructura stem and cycle. Al suprimir el vértice (6, 5) de esta estructura obtenemos un camino de Hamilton, mientras que si añadimos el vértice (5, 8) tenemos otra estructura stem and cycle. Los movimientos de inserción de vértices en la heurística de Lin y Kernighan se hallan guiados por criterios de costes basados en el "beneficio acumulativo", definiéndose los movimientos de supresión de vértices únicamente con intención de generar la estructura del camino. El algoritmo de Lin y Kernighan alcanza un óptimo local cuando, después de haber considerado todos los nodos como el nodo de inicio, no se obtienen soluciones de mejora. Diversas variantes de este algoritmo han dado lugar a soluciones heurísticas de gran calidad. Se

9

trata de algoritmos que recurren a distintas mejoras, como los movimientos 2-opt, 3-opt y 4-opt especial. ([29], [41], [42], [50], [51], [52], [64]) a fin de obtener un itinerario que no se podría diseñar mediante los movimientos básicos de la heurística de Lin y Kernighan. Asimismo, se emplean estructuras de datos capaces de actualizar de modo eficiente los itinerarios, y así poder lograr tanto la eficiencia computacional como la calidad de la solución ([24], [42]). Papadimitriou [54] ha demostrado que el problema de determinar un óptimo local con respecto a una versión del algoritmo de Lin y Kernighan es un problema PLS-completo. Podemos definir los métodos de profundidad variable para el TSP mediante un procedimiento de generalización de la heurística de Lin y Kernighan. Se trata de un procedimiento que toma como datos de partida un itinerario factible S, aplicando a continuación la función Move más arriba. En cada iteración, esta función crea el par (Tj, Sj), en el que el subconjunto Tj puede ser una solución factible, o bien ser una instancia no factible de una estructura de referencia; y el subconjunto Sj es factible. A continuación, se invoca la función Move para r iteraciones, dependiendo el valor de r de la regla directriz adecuada. Por último, el procedimiento de búsqueda de profundidad variable da como resultado el subconjunto factible Sk que tenga el mejor valor de función objetivo hallado en la búsqueda. Procedimiento: búsqueda de profundidad variable (S); Inicio: S1 := T1 := S; para j := 2 a r (Tj, Sj) = Move(S j-1, Tj-1); seleccionar el conjunto Sk que minimice (f(Sj): 1 ≤ j ≤ r); Final Este tipo concreto de búsqueda de profundidad variables se basa en una heurística llamada “Move”, que crea de forma sistemática un itinerario de soluciones comenzando por la solución inicial. Al tratarse de un marco bastante flexible, existen varias formas de diseñar este procedimiento. Las características del diseño de Move pueden suponer la diferencia entre una heurística capaz de proporcionar resultados y otra que no lo sea tanto. En el procedimiento arriba descrito, hemos supuesto que Move crea en cada fase una solución simple. En realidad, esta heurística ofrece la posibilidad de crear soluciones factibles múltiples en cada fase ([30], [61]) o ninguna solución factible en una fase determinada ([30], [58]). Muchos métodos de profundidad variable requieren las soluciones intermedias Tj para poder cumplir ciertas propiedades topológicas (o estructurales). En el algoritmo de Lin y Kernighan, por

10

ejemplo, es necesario que para cada valor impar de j, Tj sea una estructura stem and cycle, así como que, para cada valor par de j, Tj sea un camino de Hamilton. En el siguiente apartado veremos también ejemplos en los que Tj cumple otras propiedades que no son estructurales; como, por ejemplo, las que dependen del orden de los índices. Glover [30] consideró una clase estructurada de métodos de profundidad variable llamados ejection chains y basados en métodos de itinerarios alternativos clásicos, ampliando y generalizando las ideas de Lin y Kernighan. En palabras de Glover: “De modo muy esquemático, una ejection chain se inicia seleccionando un conjunto de elementos que van a experimentar un cambio de estado (e.g, ocupar nuevas posiciones, recibir nuevos valores o ambas cosas). Este cambio tendrá por efecto identificar una serie de conjuntos distintos, que tengan la propiedad de que los elementos de al menos uno de ellos deben ser “eyectados” de su estado actual. Por lo general, los pasos de cambio de estado y de eyección se alternan, y las opciones existentes para cada uno de ellos dependerán del efecto cumulativo de los pasos previos (estando influido generalmente, aunque no siempre, por el paso inmediatamente anterior). En algunos casos, una secuencia en cascada de operaciones indica que se ha producido un efecto dominó. La terminología de la "ejection chain" pretende sugerir, no limitar; proporcionando un hilo conductor que sirva para vincular una serie de procedimientos útiles para sacar el máximo partido de la estructura sin fijar reglas de admisión que excluyan otros tipos de clasificaciones.” (La cursiva es un añadido). En el presente estudio, emplearemos una definición más restrictiva de las ejection chains. Así, nos referiremos al método de profundidad variable como una ejection chain si: (i)

|T1| = |T3| = |T5| =…= n, y:

(ii)

|T 2| = |T4| = |T6| =…= n +1 (o n-1).

Para cada valor par de j, si |Tj| = |S|- 1, Tj se obtiene a partir de Tj-1 eyectando un elemento. De otro modo, |Tj| = |S|+1, y Tj+1 se obtiene eyectando un elemento a partir de Tj. Muchos de los métodos de profundidad variable publicados en estudios pueden contemplarse como ejection chains. Estos métodos suelen suponer la construcción de diferentes estructuras de referencia, junto con una serie de reglas que permitan obtener distintas soluciones factibles. Por lo que sabemos, todos los métodos de profundidad variable aplicados al problema del viajante de comercio de los que tenemos noticia pueden contemplarse como ejection chains. Podemos suponer que los nodos del grafo de vecindad referido a la vecindad de Lin y Kernighan se hallan compuestos por caminos y estructuras de stem-and-cycle. (Recuérdese que los itinerarios son también instancias de stem-and cycle. Los puntos finales de cada vértice del grafo de vecindad enlazarían un camino con una estructura stem and cycle. La técnica de búsqueda sería la

11

propuesta por Lin y Kernighan [44], y el proceso de selección consistiría en elegir el mejor de los itinerarios hallados al realizar la búsqueda. Por consiguiente, las estructuras de referencia descritas para las ejection chains serían los nodos del grafo de vecindad de las técnicas de ejection chain. Toda técnica en la que la siguiente solución básica sea mucho mayor que la distancia unitaria desde la solución básica existente es un "método de profundidad variable". Una ejection chain es un método de profundidad variable en el que los vecinos se caracterizan por ser subconjuntos los unos de los otros (y en los que, por tanto, un elemento se eyecta al trasladarse del más grande al más pequeño). En el método descrito anteriormente, las técnicas de profundidad variable se basan en la función Move. También es posible crear subconjuntos de tamaño exponencial de Nk en los que se realicen búsquedas mediante flujos de redes. En estas vecindades, se puede también llegar a cualquier vecino mediante una secuencia de funciones Move en un grafo de vecindad adecuadamente definido. Conviene tener presente que, en el caso del algoritmo de Lin y Kernighan, la vecindad es de tamaño polinómico, y que es la propia búsqueda la que lleva a obtener soluciones sustancialmente diferentes de la solución básica. En el siguiente apartado analizaremos estas técnicas basadas en flujos de redes, algunas de las cuales pueden también contemplarse como técnicas de ejection chain cuando existe un medio natural de asociar una ejection chain (una secuencia alternativa de adiciones y supresiones) a elementos de la vecindad ([30], [31], [58], [21]). Los algoritmos basados en la profundidad variable y en la ejection chain se han aplicado con éxito a la obtención de soluciones válidas para diversos problemas de optimización combinatoria. Autores como Glover [30], Rego [61], Zachariasen y Dum [83], Johnson y McGeoch [42], Mak y Morton [51], y Pesch y Glover [55] han utilizado estos algoritmos para la resolución del problema del viajante de comercio. El problema del enrutamiento de vehículos ha sido tratado por Rego y Roucairol [63] y Rego [62], mientras que Dondorf y Pesch [13] han propuesto la solución a algoritmos de clustering mediante ejection chains. Por su parte, Yagiura et al. ([80]) han considerado la aplicación de métodos de profundidad variable al problema de las asignaciones en general, al igual que distintas variantes de la ejection chain [79]. Asimismo, Laguna et al. [47] aplican algoritmos cortos de estructura ejection chain al problema de las asignaciones multinivel en general. Estas técnicas se aplican también al problema de la partición del grafo uniforme ([16], [20], [44], [53]), al problema de las asignaciones por categorías ([3]), al problema de asignación de canal ([17]), y al de distribución de turnos de enfermería([14]). Por último, Sourd [70] aplica una clase muy general de procedimientos de mejora de vecindades a muy gran escala en los que la distancia entre dos vecinos depende de las tareas programadas en máquinas no relacionadas. El desarrollo de estas vecindades se lleva a cabo mediante la generación de árboles de enumeración parciales, aunque de tamaño grande, basados en las soluciones existentes y

12

buscados por heurística.

4. Algoritmos de mejora basados en flujos de redes En este apartado estudiaremos algoritmos locales de mejora en los que la búsqueda por vecindades se lleva a cabo mediante algoritmos basados en flujos de redes. Las técnicas de flujos de redes empleadas para identificar vecindades de mejora pueden agruparse en tres categorías: (i) métodos de búsqueda de ciclo de coste mínimo; (ii) métodos basados en la programación dinámica o en la técnica del camino más corto; y (iii) métodos basados en la búsqueda de asignaciones y ajustes de coste mínimo. Las vecindades definidas por ciclos pueden contemplarse como generalizaciones de vecindades de dos intercambios, mientras que las basadas en asignaciones se pueden entender como generalizaciones de vecindades a partir de inserciones. En los tres subapartados que siguen, se ofrecen definiciones generales de estas vecindades exponenciales, describiéndose además los algoritmos de flujos de redes empleados en la búsqueda de vecindades mejoradas. En muchos de los problemas, la vecindad de mejora se determina aplicando un algoritmo de flujos de redes a un grafo relacionado, lo que se conoce como grafo de mejora.

4.1 Vecindades definidas por ciclos En este subapartado, comenzaremos por definir un problema de partición genérica, para a continuación pasar a definir la vecindad de dos intercambios y la vecindad de intercambio cíclico. Sea A = {a1, a2, a3, …, an} un conjunto formado por n elementos. El conjunto {S1, S2, S3, …, SK} define una Kpartición de A f A cuando cada conjunto Sj es no vacío, los conjuntos no se hallan agrupados por pares, y su punto de unión es A. Para cualquier subconjunto S de A, llamaremos d[S] al coste de S. Por tanto, el problema de partición consiste en hallar una partición de A en tantos subconjuntos de K como sean necesarios para minimizar Σk d[Sk]. Sea {S1, S2, S3, …, SK} cualquier partición factible. Diremos entonces que {T1, T2, T3, …, TK} será un 2-vecino de {S1, S2, S3, …, SK} cuando pueda obtenerse intercambiando dos elementos que se encuentren en subconjuntos diferentes. La vecindad de dos intercambios de {S1, S2, S3, …, SK} se halla formada por todas las vecindades-2 de {S1, S2, S3, …, SK}. De donde deducimos que {T1, T2, T3, …, TK} es una vecindad cíclica de {S1, S2, S3, …, SK} cuando se pueda obtener transfiriendo elementos simples a lo largo de una secuencia de subconjuntos de k ≤ K en S. Sea también (Sh1, Sm2, Sn3, …, Spk) una secuencia de k subconjuntos tal que hace necesario que h = p, que es el último subconjunto de la secuencia idéntico a Sh1. A esta transferencia de elementos la llamaremos intercambio cíclico, quedando

13

ilustrada en la figura 2. En el presente ejemplo, el nodo 9 pasa del subconjunto S1 al subconjunto S4; el nodo 2 se transfiere del subconjunto S4 al subconjunto S5, el nodo 3 pasa del subconjunto S5 al S3 y, finalmente, el intercambio se completa transfiriendo el nodo 14 del subconjunto S3 al S1. De un modo análogo puede definirse un vecino de camino. Desde un punto de vista matemático, no resulta difícil convertir un intercambio de camino en un intercambio cíclico añadiendo los nodos de prueba adecuados.

Por lo general, el número de vecindades cíclicas es sustancialmente mayor que el de vecindades de dos intercambios (2-vecindades). Mientras que hay O(n2) 2-vecindades para un valor fijo de k, existen O(nK) vecinos cíclicos. Si se permite que la variación de k sea paralela a la de n, tendremos un número exponencial de vecinos cíclicos. Thompson [75], Thompson y Orlin [76], y Thompson y Psaraftis [77] han mostrado la forma de obtener una vecindad mejorada en la vecindad de intercambio cíclico hallando un ciclo de "subconjunto no agrupado" de coste negativo en un grafo de mejora. Expondremos a continuación cómo construir dicho grafo. Sea A = {a1, a2,…, an} que es el conjunto de elementos que componen el problema de partición del conjunto original, y llamemos S[i] al subconjunto en el que se encuentra el elemento ai. El grafo de mejora es un grafo G = (V, E) en el que V = {1, 2,…, n} es un conjunto de nodos que se corresponde con los índices de los elementos de A del problema original. Sea asimismo E = {(i, j): S[i] ≠ S[j]}, donde un arco (i, j) corresponde a la transferencia del nodo i desde S[i] a S[j] y a la supresión de j desde S[j]. Para cada arco (i, j)

∈

E, haremos que c[i, j] = d[{i} ∪ S[j]\{j}] – d[S[j]], es decir, el

incremento en el coste de S[j] cuando se añade i al conjunto y se suprime j. Decimos que un ciclo W en

14

G no está agrupado en el subconjunto cuando, para cada par i y j de los nodos de W, S[i] ≠ S[j], es decir, los elementos de A correspondientes a los elementos de W se encuentran todos en subconjuntos diferentes. Existe una correspondencia entre el mantenimiento de costes uno a uno en los intercambios cíclicos del problema de la partición y el mantenimiento en los ciclos no asignados en el subconjunto del grafo de mejora. Concretamente existe, para cada intercambio cíclico de coste negativo, un ciclo no asignado en el subconjunto del grafo de mejora. Desgraciadamente, el problema consistente en determinar si hay un ciclo no asignado en el subconjunto del grafo de mejora es un problema NPcompleto, y el consistente en hallar un ciclo no asignado en el subconjunto de coste negativo es NPdifícil. (Véase, por ejemplo, Thompson [75], Thompson y Orlin [76], y Thompson y Psaraftis [77].) Aun cuando este último problema sea NP-difícil, existen heurísticas que han demostrado su eficacia en la búsqueda del grafo. (Véase, por ejemplo, Thompson y Psaraftis [77] y Ahuja et al. [2].) La búsqueda por vecindad de intercambio cíclico se aplica con éxito a varios problemas de optimización combinatoria que pueden caracterizarse como problemas de partición específica. Thompson y Psaraftis [77], Gendreau et al. [25], y Fahrion y Wrede [19] resuelven el problema del enrutamiento de vehículos mediante este tipo de búsqueda, mientras que Frangioni et al. [23] aplican intercambios cíclicos a la programación de máquinas en periodos mínimos. Thompson y Psaraftis [77] han demostrado también la aplicación de este método a problemas de programación . Por su parte, Ahuja et al. [2], empleando intercambios cíclicos, han desarrollado las mejores soluciones existentes para un conjunto ampliamente usado de instancias de referencia en problemas de árboles de expansión mínima capacitados. La idea de hallar soluciones de mejora mediante la determinación de ciclos de coste negativo en grafos de mejoras se ha aplicado también en otros contextos. Talluri [74] identifica intercambios de ahorro de costes de equipo entre turnos de vuelos en problemas de asignación diaria de flota aérea hallando ciclos de coste negativo en una red relacionada. El problema de asignación de flota puede plantearse como un problema de flujo multiservicio entero sujeto a restricciones de lado, en el que cada servicio hace referencia a un tipo de flota. Talluri considera una solución dada restringida a dos únicos tipos de flota, buscando a partir de ella mejoras que puedan obtenerse mediante el intercambio de un número de vuelos entre ambos tipos de flota. Así, desarrolla un grafo de mejora asociado, demostrando que las vecindades de mejora se corresponden con los ciclos de coste negativo del grafo de mejora. Schneur y Orlin [68] y Rockafellar [65] resuelven el problema de flujo multiservicio lineal detectando flujo y enviándolos iterativamente por los ciclos de coste negativo. Esta técnica se extiende, de hecho, a la heurística de mejora basada en ciclos para el problema de flujo multiservicio entero. En [81], Wayne ofrece un algoritmo de cancelación de ciclo para resolver el problema del flujo de coste mínimo generalizado. Firla et al. [22] introducen un grafo de mejora para la intersección de dos programas

15

enteros cualesquiera. Los caminos y ciclos de esta red corresponden a posibilidades de mejora de soluciones factibles. Además, esta red da lugar a una definición algorítmica del problema del b-ajuste de peso bipartito. Los algoritmos analizados por Glover y Punnen [28] y Yeo [78] permiten construir itinerarios del viajante de comercio que resultan mejores que un número exponencial de itinerarios. Estos algoritmos se pueden contemplar, asimismo, como el cálculo de un ciclo de coste mínimo en una red considerada de capas especiales implícitamente considerada. Veremos esta heurística de forma más detallada en el apartado 5.

4.2 Vecindades definidas por caminos (o por programación dinámica) A continuación analizaremos tres tipos distintos de algoritmos de búsqueda por vecindad basados en caminos más cortos o en programación dinámica, tomando como contexto el problema del viajante de comercio. Aplicados al mismo, podemos contemplar estos enfoques de búsqueda por vecindad como: (i) adición y supresión de vértices secuencialmente, (ii) aceptación en intercambios paralelos múltiples, entendiendo definido cada intercambio como la permuta del orden actual de dos ciudades en un recorrido, y (iii) cambios cíclicos en el itinerario existente. Veamos estas vecindades con mayor detalle.

4.2.1 Creación de un nuevo vecino mediante la adición o supresión de arcos secuencialmente Examinaremos en primer lugar una clase de métodos basados en el camino más corto, que consideran los vecinos obtenidos añadiendo o suprimiendo vértices alternativamente del itinerario existente. Se trata de métodos que realizan de modo exhaustivo búsquedas en la vecindad de ejection chain tratada en el apartado 3, con el añadido de restricciones adicionales en los vértices. Para simplificar, damos por hecho que el itinerario S pasa por las ciudades siguiendo el orden 1, 2, 3, …, n, 1. Empleando la terminología del apartado 3, llamaremos itinerario T a un vecino de k-intercambios de S, y al camino que va desde S a T, la secuencia S = T1, …, TK = T. Estas vecindades corresponden a soluciones por aproximaciones sucesivas creadas mediante los caminos pares e impares descritos en Punnen y Glover [58] entre varias otras vecindades y soluciones por aproximaciones sucesivas construidas a partir de diversas clases de estructuras de camino. La solución por aproximaciones sucesivas generada por los caminos impares ya fue desarrollada de modo independiente por Firla et al.[21]. A efectos ilustrativos de este tipo de solución generada a partir de caminos tanto pares como impares, veamos el siguiente algoritmo: (i)

Se elimina el vértice (n, 1) para obtener un camino de Hamilton T2 y se añade el vértice

16

(1, i) desde el nodo 1 al nodo i (donde i > 2) para obtener una estructura stem and cycle T3 . (ii)

El actual nodo terminal del camino es el nodo i. Se elimina el vértice (i, i-1) y se añade el vértice (i-1, j) para i < j < n, creando primero un camino de Hamilton y a continuación una estructura stem and cycle.

(iii)

Se comprueba si se ha alcanzado un criterio de terminación. Si se alcanza, se sigue al paso (iv). Si no, se define i = j y se vuelve al paso (ii).

(iii)

Se elimina el vértice (j, j-1) y se añade el vértice final (j-1, n) para completar el recorrido.

Figura 3. Ilustración del intercambio de camino alternativo.

La figura 3 ilustra este proceso en un itinerario de 9 nodos S = (1, 2,…, 9, 1). El procedimiento de intercambio de camino se inicia con la supresión del vértice (n, 1) y la adición del vértice (1, 4). A continuación se elimina el vértice (3, 4) y se añade el vértice (3, 7). Por último, se crea el nuevo itinerario T suprimiendo el vértice (6, 7) y añadiendo el vértice (6, 9). En la figura 3(a) los vértices añadidos aparecen representados mediante líneas en negrita y los eliminados mediante una raya sobre el vértice. La figura 3(b) ilustra el nuevo itinerario que se obtiene tras el intercambio de camino. Firla et al.[21], Glover [30] y Punnen y Glover [58] han demostrado que se puede obtener una solución de mejora para esta vecindad en tiempo O(n2), hallando en un grafo de mejora un camino de longitud mínima par o impar. Describimos aquí un grafo de mejora que permite identificar la mejor vecindad de un itinerario hallando un camino más corto con un número de nodos par o impar. Recordemos que S = (1, 2, 3,…, n, 1) es el itinerario existente del problema del viajante de

17

comercio con n nodos. El grafo de mejora es un grafo G = (V, E) en el que V = {1, 2,…, n}, lo que corresponde a los nodos del problema original, y donde E = {(i, j) : 1 = i < j-1 < n} es un conjunto de arcos dirigidos. Los arcos (1, j)

∈

E (de modo que 2 < j = n) corresponden a la supresión del

vértice (n, 1) y a la adición del vértice (1, j), y los arcos (i, j)

∈

E (de modo que 1 < i < j-1 < n)

corresponden a la supresión del vértice (i-1, i) y la adición del vértice (i-1, j) en el recorrido original S. Si d[i, j] es el coste de trasladarse de la ciudad i a la ciudad j cuando asociamos un coste c[1, j] = -d[n, 1] + d[1, j].a cada arco (1, j) ∈ E de modo que 2 < j = n y un coste c[i, j] = -d[i-1, i] + d[i-1, j] a cada arco (i, j) ∈ E tal que 1 < i < j-1 < n. Por último, hallar un camino de coste negativo G desde el nodo 1 a n permite identificar un intercambio k provechoso. Por otra parte, en [58] se examinan soluciones por aproximaciones sucesivas creadas a partir de caminos pares e impares, nuevas estructuras de caminos, como caminos cortados y caminos inversos, que llevan a distintas soluciones por aproximaciones sucesivas, y estructuras de referencia. El tamaño de la vecindad generada únicamente por caminos pares e impares es Ω (n2n). Las técnicas que aceleran la búsqueda en vecindades son importantes incluso en vecindades cuyo tamaño no sea exponencial. Así, por ejemplo, gracias al empleo de un algoritmo del camino más corto en un grafo de mejora acíclico, Glover [31] ha obtenido una clase con los mejores movimientos 4-opt en tiempo O(n2).

4.2.2 Creación de un nuevo vecino mediante intercambios compuestos La segunda clase de algoritmos de búsqueda local definidos mediante intercambios de caminos consiste en una generalización de la vecindad de intercambio. Dado un itinerario del problema del viajante de comercio T = (1, 2, 3,…, n, 1) con un número n de nodos, la vecindad de intercambio generará soluciones intercambiando las posiciones de los nodos i y j por 1 ≤ i ≤ j ≤ n. Por ejemplo, supongamos que i = 3 y que j = 6, T' = (1, 2, 6, 4, 5, 3, 7,…, n, 1) es un vecino) de T bajo la operación de intercambio. Se dice que dos operaciones de intercambio que conecten el nodo i con j, y el nodo k con l son independientes cuando max{i, j} < min{k, l}, ó cuando min{i, j} > max{k, l}. Entonces, una vecindad a gran escala en el itinerario T se puede definir componiendo (es decir, tomando en su totalidad) un número arbitrario de operaciones de intercambio individuales. Congram et al. [9] y Potts y van de Velde [57] aplicaron esta vecindad de intercambios compuestos al problema de la programación de la lentitud ponderada total de una máquina y al del viajante de comercio (TSP), respectivamente, llamando a este enfoque dynasearch. En su estudio, Congram et al. [9] demuestran que el tamaño de la vecindad es O(2n-1) y presentan una recursión de programación dinámica capaz de hallar la mejor vecindad en tiempo O(n3). Hurink [40] aplica un

18

supuesto especial de la vecindad de intercambio compuesto en la que sólo se permite sustituir pares adyacentes en el contexto de problemas de funcionamiento de una única máquina, y demuestra que es posible obtener un vecino de mejora en tiempo O(n2) hallando el camino más corto en el grafo de mejora apropiado. A continuación describiremos un grafo de mejora que nos sirva de ayuda en la búsqueda de la vecindad de intercambio compuesto. Sea T = (1, 2, 3,…, n, 1) un itinerario del viajante de comercio de n nodos. El grafo de mejora es un grafo G = (V, E), donde (i) V = {1, 2,…, n, 1' , 2' ,…, n'} es a un conjunto de nodos correspondiente a los nodos del problema original y una copia de éstos, y (ii) E es un conjunto de arcos dirigidos (i, j') ∪ (j', k), en el que un arco (i, j') corresponde al intercambio de los nodos i y j, y un arco (j', k) indica que el nodo k es el primer nodo del siguiente intercambio. Así, por ejemplo, un camino de tres arcos (i, j'), (j', k), (k, l) ) en G representa dos operaciones de intercambio que cambian el nodo i por el j, y el nodo k por l. Para construir el conjunto de arcos E, se tiene en cuenta cada par de nodos (i, j') y (j', k) en V, añadiéndose el arco (i, j') a E si, y solamente si, j > i.> 1. El arco (j', k) se añade a E si, y solamente si, j = 1 y k > j ó j > 1 y k > j + 1. Para cada arco (i, j')

∈

E, se asocia un coste c[i, j] equivalente al incremento neto en el

coste óptimo del itinerario del viajante de comercio tras suprimir los vértices (i-1, i), (i, i+1), (j–1, j) y (j, j+1) y añadir los vértices (i-1, j), (j, i+1), (j-1, i) y (i, j+1). En otras palabras, si d[i, j] es el coste de trasladarse del nodo i al nodo j en el problema original, y d[n, n+1] = d[n, 1], tenemos que: c[i, j'] = (-d[i-1, i] – d[i, j] - d[j, j+1] ) + (d[i-1, j] + d[j, i] + d[i, j+1]) para j' = i+1, y c[i, j] = (-d[i-1, i] – d[i, i+1] - d [j-1, j] - d[j, j+1] ) + (d[i-1, j] + d[j, i+1] + d[j-1, i] + d[i, j+1]) para j' > i+1. El coste c[j', k] de todos los vértices (j', k) se define como igual a 0. Vemos que hallar el mejor vecino de un itinerario en el TSP para la vecindad de intercambio compuesto equivale a hallar el camino más corto en el grafo de mejora y, por tanto, precisa un tiempo O(n2). Obsérvese que, al ser el TSP un problema cíclico, uno de los nodos se mantiene fijo durante el intercambio. En la construcción más arriba expuesta del grafo de mejora, suponemos, sin pérdida de generalidad, que no se permite mover el nodo 1, por lo que la búsqueda por vecindad se realiza hallando el camino más corto desde el nodo 1' al nodo n o al nodo n'. La recursión de programación dinámica que ofrecen Congram et al. [9] para realizar búsquedas en la vecindad llevará igualmente un tiempo O(n2) cuando se aplique al problema del viajante de comercio. El algoritmo del camino más corto visto arriba emplea un tiempo O(n3) cuando se aplica al problema de la programación del retraso ponderado total, ya que ese tiempo O(n3) es el que se precisa para calcular los costes de los arcos.

19

4.2.3 Creación de un nuevo vecino mediante un intercambio cíclico La última clase de algoritmos de búsqueda local que trataremos en este apartado se basa en un tipo de intercambio cíclico de itinerarios piramidales (Carlier y Villon [8]). Se dice que un itinerario es piramidal cuando comienza en la ciudad 1, visita a continuación las ciudades en orden creciente hasta llegar a la ciudad n, y termina volviendo a la ciudad 1 pasando por las restantes ciudades en orden decreciente. Supongamos que T(i) representa la ciudad situada en la posición i-ésima del itinerario T. Un recorrido T' es un vecino piramidal de un recorrido T cuando existe un número entero p tal que: (i)

0 ≤ p ≤ n,

(ii)

T' (1) T' (2) = T(i2),…, T' (p) = T(ip) con i1 < i2