Una hiperheurística para la solución del Problema del Viajante Asimétrico

1. Resumen
3. Revisión bibliográfica
4. Solución del problema
5. Conclusiones
6. Referencias

Resumen

El uso de métodos aproximativos eficientes para obtener soluciones cercanas a las óptimas en diversos problemas combinatorios complejos es de gran interés por la gran cantidad de aplicaciones que tienen. La literatura refleja diversos algoritmos heurísticos, metaheurísticos o híbridos para la solución de problemas, pero muy pocos con enfoques hiperheurísticos.

En general, los primeros métodos mencionados requieren de un dominio de los especialistas y un trabajo previo de ajuste de parámetros para ser exitosos en una amplia gama de instancias de un problema concreto.

En este trabajo se propone una hiperheurística para el Problema del Viajante Asimétrico. La literatura revisada no refleja la utilización de este método para este tipo de problema. El objetivo fundamental no es competir con métodos eficientes existentes para mejorar la calidad de las soluciones obtenidas por los mismos, sino obtener un método robusto que se eficiente.

Para el diseño de la hiperheurística propuesta se definen diversas heurísticas simples y estructuras de vecindad, que se utilizan en métodos de búsqueda local. Se realiza un diseño de experimento con un conjunto de instancias descritas en la literatura, y se muestran los resultados obtenidos.

Palabras claves

Problemas combinatoriales, heurísticas, metaheurísticas, hiperheurísticas, el Problema del Viajante Asimétrico.

1. Introducción

Se pueden encontrar una gran cantidad de problemas reales que son modelados y resueltos con técnicas de optimización. Entre los que pueden mencionarse están los clásicos problemas de diseño de redes de telecomunicación, los de planificación de horarios, los de secuenciación de tareas, los distintos problemas de ruteo, u organización de la producción hasta los más actuales en ingeniería y re-ingeniería de software. Algunas clases de estos problemas son relativamente fáciles de resolver, este es el caso, por ejemplo, de los problemas lineales, en los que tanto la función objetivo como las restricciones son expresiones lineales, que pueden ser resueltos con el conocido método Simplex; sin embargo, muchos otros tipos de problemas de optimización son muy difíciles de resolver, y gran parte de ellos corresponden a problemas de Optimización Combinatorial.

Estos problemas difíciles de interés práctico resultan intratables si se trata de obtener una solución óptima en un tiempo razonable mediante técnicas de cálculo. Ante esta dificultad, los algoritmos heurísticos se revelan como un medio útil para su resolución, ya que permiten obtener buenas soluciones, en algunos casos óptimas, en un tiempo razonable. En los últimos años ha cobrado auge el uso de las metaheurísticas [29] que son algoritmos aproximativos, aplicándolos a una gama de diferentes problemas. Entre ellos se encuentra el Recocido Simulado [10], el Greedy Randomized Adaptive Search Procedures (GRASP) [12], Búsquedas Tabú [22] o los Algoritmos Genéticos [16]. Existen numerosos trabajos con aplicaciones de estos métodos en diferentes revistas especializadas de Investigación Operativa.

Sin embargo, esta clase de algoritmos presentan esta clase de inconvenientes cuando se trata de aplicarlos a un problema específico:

1. El número de parámetros a ser ajustados para obtener un buen desempeño del algoritmo puede requerir un tiempo considerable.
2. La comprensión de estos parámetros, básicamente para un usuario no especializados en estos métodos. Puede citarse, por ejemplo, que en los Algoritmos Genéticos es bastante fácil de entender que mientras el tamaño de la población es mas grande, los resultados obtenidos deben ser mejores aunque con un costo de tiempo mayor. Sin embargo no está muy claro cual sería la incidencia en la ejecución del algoritmo los ajustes de parámetros, como la probabilidad de cruzamientos. Otro ejemplo es el Recocido Simulado, donde la literatura describe que los mejores valores de r (la velocidad en que disminuye la temperatura), se obtiene solo de extensos diseños de experimento.
3. Para un mismo tipo de problema, los parámetros ajustados pueden no ser los mejores para cualquier tipo de instancia, pueden depender, por ejemplo, del tamaño de la instancia, las características de una matriz de costos, etc.

Mucho más reciente, cuya literatura aún es escasa, es el uso de métodos hiperheurísticos [9] para la solución de problemas combinatoriales. Estos métodos eliminan las inconveniencias planteadas de las metaheurísticas.

El propósito fundamental de este trabajo es realizar el diseño de un algoritmo hiperheurístico que solucione de forma eficiente, teniendo en cuenta la calidad de la solución y tiempo de ejecución, una amplia gama de instancias del Problema del Viajante Asimétrico (PVA). Colateralmente, que también pueda ser extensible a otros problemas como el Problema de la Mochila Binaria (PMB).

El por qué se diseña una hiperheurística para el PVA está dado básicamente por las siguientes razones: resolver un problema real surgido en la planificación del teñido de telas en la industria textil [25, 26 y 30], el cual es modelado por el PVA el cual es NP – completo [14] al cual se le han aplicado diversos algoritmos heurísticos e metaheurísticos.

La literatura reporta bibliotecas de instancias generadas con el fin de evaluar la calidad del desempeño de nuevos métodos realizados para este problema [33].

El documento tiene una estructura formada por tres epígrafes, las conclusiones y recomendaciones. En el primer epígrafe se realiza un análisis bibliográfico a las literaturas utilizadas, en el segundo propone la solución al problema, el tercero ofrece un diseño de experimento a los resultados obtenidos.

1. 2.1 El Problema del Viajante Asimétrico

   El Problema del Viajante Asimétrico [4 y 7], más conocido por su nombre en ingles The Asymmetric Traveling Salesman Problem, es quizá el problema de optimización combinatorial más popular de todos. De la manera más simple, el PAV consiste, en dadas un conjunto de n ciudades un vendedor debe visitar cada una de ellas una sola vez y regresar a su ciudad de origen, de tal forma que su recorrido sea mínimo. Matemáticamente para cada par de ciudades , se denota como la distancia entre ellas, la meta es encontrar una permutación de las ciudades que minimice:

   Existen diversas heurísticas constructivas y de búsquedas para la solución de este problema. Entre las heurísticas constructivas encontradas para este problema se encuentra la popular estrategia voraz, la del vecino más cercano, la técnica de remiendo, etc.

   2.1.1 Métodos constructivos

   Las heurísticas constructivas aportan soluciones del problema por medio de un procedimiento que incorpora iterativamente elementos a una estructura, inicialmente vacía, que representa a la solución. Las heurísticas constructivas establecen estrategias para seleccionar las componentes con las que se construye una buena solución del problema.

   Una de las mejores metaheurística constructivas sin duda alguna es GRASP [12], en su diseño el parámetro alfa es un aspecto bien discutido. Los diferentes autores que han utilizado este método lo definen después de realizar un análisis estadístico a su problema con diferentes valores. Los valores extremos de este parámetro brinda dos tipos de soluciones: golosas y aleatorias . Existen diversas variantes eficientes del método GRASP, una de ellas por ejemplo, es la llamada GRASP-Reactivo [12] donde su parámetro se va actualizando según se desarrollan las iteraciones del algoritmo.

   Los métodos golosos y el vecino más cercano son dos variantes del método GRASP, que realizan una elección que le implique los mejores resultados inmediatos, sin tener en cuenta una perspectiva más amplia. La heurística del vecino más cercano, conocido como Nearest Neighbor, comienza escogiendo un nodo inicial aleatoriamente e iterativamente busca su nodo más cerca, o si existen varios, construye una lista y escoge uno de ellos aleatoriamente. El método goloso ó Greedy, busca iterativamente los dos nodos más próximos y escoger uno aleatoriamente [7].

   Estos métodos aceptan algunas mejoras como aplicar una búsqueda local al final de cada iteración o al finalizar todas las iteraciones, así se obtiene una solución con mejor calidad.

   2.1.1.1 Remiendo por cubrimiento de ciclos

   El método de remiendo por cubrimiento de ciclos construye las soluciones a partir de ciclos realizados por las asignaciones obtenidas [7]. Por tanto el primer paso para realizar este método es convertir el PVA en un problema de asignación.

   El Problema de Asignación (PA) [34] es un problema clásico de optimización combinatorial, en el cual se encuentra un vasto número de problemas de diseño y de distribución de recursos en diferentes campos, donde la decisión a tomar es una asignación de elementos de un conjunto en otro. Para aplicar el PA al PVA se utiliza un grafo bipartito, donde la cantidad de nodos es 2n, siendo n el número de ciudades y la distancia un valor arbitrariamente grande.

   Existen varios métodos para la solución del PA. Uno de ellos, muy popular, es el método Húngaro, con sus variantes. Los pasos de este están descrito por [32], y por muchas otras referencias, pero no solucionan (no convergen) algunas instancias que presentan soluciones múltiples, y se necesitan otros pasos adicionales, no aclarados. Existen otros artículos que describen este método basado en el problema dual [32], con una complejidad , pero es engorroso y presenta detalles incompletos para su implementación.

   Otro método es por subasta, conocido como Auction [31], donde su función objetiva es maximizar, y consiste en realizar una subasta donde hay n carros a subastar a n personas, con la condición de que cada persona se lleven un carro. Este método utiliza técnica de escalamiento siendo muy eficiente y fácil de implementar.

   2.1.2 Cotas inferiores

   Para evaluar la calidad de una solución obtenida, en ausencia de la solución óptima, es importante contar con métodos que proporcionen cuotas inferiores a la solución del problema siendo el AP uno de los métodos más difundido. El método desarrollado por Held – Karp (HK) [17 y 18] ofrece mejores cotas inferiores más cercanas al óptimo real .

   2.1.3 Búsquedas locales

   Los métodos de búsquedas locales mejoran una solución obtenida comparándolas con soluciones vecinas a ella. En un proceso iterativo se van obteniendo nuevas soluciones vecinas, de mejor calidad, mientras sea posible. Una búsqueda local es la que basa su estrategia en el estudio de soluciones del vecindario o entorno de la solución actual, en general ofrecen óptimos locales.

   Muchos métodos metaheurísticos utilizan búsquedas locales como son GRASP, Recocido Simulado, Búsqueda Tabú, y Búsqueda en Vecindades Variables. El término local se emplea con bastante frecuencia en los estudios teóricos y prácticos del campo de las metaheurísticas de búsqueda. Las estructuras de entorno suelen reflejar algún concepto de proximidad o vecindad entre las soluciones alternativas del problema. Por tanto, una búsqueda local es un proceso que, dada la solución actual en la que se encuentra el recorrido, selecciona iterativamente una solución de su entorno.

   Las búsquedas locales requieren tener en cuenta diversos aspectos como son: estructuras de vecindad utilizada, criterio para recorrer el espacio de solución (para encontrar su óptimo local con la primera mejora o con la mejora profunda, etc.) y la forma en que se recorre las soluciones vecinas.

   Existen excelentes heurísticas de búsquedas para el PVA, como las variantes realizadas de Kanellakis-Papadimitriou [20], como 3-Opt [7, 11, 15, 19, 20 y 23], 4-Opt[15 y 17] cuya complejidad es O(n4) y [15] propone un algoritmo de tipo O(n2), etc.

   2. Los métodos hiperheurísticos

   Las metaheurísticas son estrategias inteligentes para diseñar o mejorar procedimientos heurísticos muy generales con un alto rendimiento. Entre las más populares y bien estudiadas técnicas se encuentran GRASP [12], Recocido Simulado [10], Búsquedas Tabú [22], y los Algoritmos Genéticos [16]. Las cuales se han aplicado con éxito en la solución de un gran número de problemas reales.

   Sin embargo, muchos de estos enfoques carecen de la robustez para resolver una amplia gama de problemas. Las metaheurísticas pueden resolver eficientemente un problema real luego de realizar un diseño de experimento profundo para ajustar sus parámetros, pero no pudiera resolver en lo absoluto, o da soluciones muy pobres, a otros casos inclusos derivados de los mismos problemas [9]. El ajuste de parámetro de una misma metaheurística en la solución de varios problemas puede llevar tiempo mucho tiempo.

   En los últimos años los investigadores de esta temática han propuesto una nueva técnica llamada hiperheurística [9 y 10]. La hiperheurística es un algoritmo de clase abstracta que opera a un nivel mas alto que las metaheurísticas, y dirige a un grupo de heurísticas simples (de un nivel más bajo) las cuales son aplicadas, dependiendo de la característica del espacio de soluciones donde se encuentra explorando [9].

   Una hiperheurística selecciona a cada paso la más prometedora heurística simple (o una combinación de heurísticas) que puede mejorar potencialmente la solución. Por otro lado, si no hay mejora, es decir, fue encontrada una solución óptima local, ella es capaz de diversificar la búsqueda a otras áreas del espacio de solución realizando una apropiada selección de un nuevo juego de heurísticas. Las heurísticas de bajo nivel, normalmente representan a los métodos de búsquedas locales o a las técnicas constructivas [9].

   Todo el dominio de información se concentra en el conjunto de heurísticas simple y en la función objetivo. La selección de una nueva heurística está basada por distintos criterios: los valores retornados de la función objetivo, por el tiempo de ejecución de la CPU, etc., siendo necesario para estos casos una perturbación de la solución [10].

   Los enfoques hiperheurísticos con respecto a las metaheurísticas tienen las siguientes ventajas principales. Primeramente, una hiperheurística es sencilla y rápida de implementar; al mismo tiempo puede producir soluciones comparables en calidad a otras ya encontradas por eficientes metaheurísticas. Segunda, ella no tiene el acceso al conocimiento del dominio específico del problema, haciéndola aplicable en pequeños estudios o a problemas reales pobremente estudiados.

   Finalmente, estas técnicas son robustas: pueden ser eficazmente aplicadas a una amplia gama de instancias de un problema.

2. Revisión bibliográfica
3. Solución del problema

3.1 Las estructuras de datos

En los problemas de optimización combinatorial, además de la calidad en las soluciones dadas por los métodos implementados, el aspecto más importante a tener en cuenta es su tiempo de ejecución. Esto se puede lograr realizando un eficiente diseño en las Estructuras de Datos (ED) que serán implementadas para los algoritmos [1, 2, 8, 13, 24 y 32].

Para realizar un diseño eficiente de algoritmos, el principal aspecto que un programador debe conocer y tener en cuenta son las ED que va a utilizar, así logrará que su aplicación sea mucho más eficiente, en otras palabras, que brinde sus soluciones en el menor tiempo posible. Es importante tener en cuenta que en los tiempos de ejecución de un algoritmo deben incluirse los tiempos de procesamiento de datos, de acceso a datos, etc., y las ED juegan en ello un papel fundamental.

Para la solución del PVA existen varias ED diseñadas, la principal es una lista enlazada de punteros, en esta podemos guardar la solución obtenida, además de utilizar una de tipo grafo, donde son guardados los datos del problema.

3.2 Heurísticas constructivas

Como se describió en el epígrafe anterior para construir las soluciones para el PVA se seleccionaron cinco algoritmos: GRASP, aleatorio, el vecino más cercano, un goloso y la técnica de remiendos.

En esta sección se analizará el método de remiendos de ciclos. Este método se puede desarrollar de varias formas: realizando cubrimiento de ciclos de mayor a menor, de menor a mayor o de forma aleatoria, el cubrimiento de estos ciclos se explica a continuación.

3.2.1 Remiendo de ciclos

Para realizar esta técnica es necesario hallar los ciclos que son formados de las asignaciones hechas por el método Auction para el PA. Después de tener las asignaciones el siguiente paso es construir una secuencia LC:

LC = C1, C2, … , Cm-1, Cm

siendo m la cantidad total de ciclos en la aplicación PA, Ck representa un ciclo ó una subruta del PVA:

Ck = ck,0, ck,1, … , ck,r-1, ck,r, ck,0

Como resultado del empate o remiendo de un par de ciclo Ck, Ck+1 se forma un nuevo ciclo C’k buscando la mínima distancia {d(ck+1,j , ck,i+1)+d(ck,i , ck+1,j+1)}, para realizar un punto de ruptura (Figura 2.1), siendo (1 ≤ i < r) y (1 ≤ j < p), donde | Ck | = r y | Ck+1| = p, quedando C’k de la siguiente forma (Figura 2.2):

C’k = ck+1,0, ck+1,1, … , ck+1,j, ck,i+1, … , ck,r, ck,1, ck,2, … , ck,i, ck+1,j+1, …, ck+1,p, ck+1,0

Figura 2.1 Puntos de rupturas de los ciclos Ck, Ck+1

Figura 2.2 Remiendo de ciclos

Los métodos de tipo Patche utilizados tienen en cuenta una única forma de unir ciclos, la explicada anteriormente. El orden en el que se toman los ciclos no es predefinido, lo define la propia hiperheurística.

En este trabajo se propone una modificación a estas técnicas realizando búsquedas locales a las soluciones obtenidas que permitan mejorar la calidad de las mismas. Para esto es necesario realizar un análisis de posibles métodos de búsqueda local para el PVA y seleccionar los mejores.

3.3 Heurísticas de búsquedas

En este trabajo se proponen cinco métodos de búsquedas locales para el PVA, dos de ellos (Mover Nodo y Intercambiar Nodo) no se encuentra reflejado por ningún autor en la literatura, aunque son variantes realizadas a 3-Opt y 4-Opt respectivamente los otras son (2-Opt, 3-Opt y 4-Opt), las cuales son utilizado con frecuencia en los trabajos del PVA [4 y 7].

Las búsquedas locales se pueden realizar de diversas maneras, las más utilizadas son la primera mejora (tomar como punto de partida la primera solución que mejore la solución actual) y la mejora profunda (recorrer toda la vecindad de la solución actual y tomar la mejor solución vecina), aunque esta última es muy rechazada por el costo computacional que genera [32]. En este trabajo se utilizará la búsqueda de la primera mejora para cada método de búsqueda. La razón para ello es que, según un pequeño diseño de experimento realizado, las estructuras de vecindad propuestas son fuertes, en el sentido de que partiendo de diversas soluciones iniciales se obtienen soluciones de calidad semejante con la primera mejora o con la mejora profunda, consumiendo este último mucho más tiempo de ejecución.

3.3.1 Operador Mover nodo

En las literaturas estudiadas este movimiento de búsqueda no fue descrito por ningún autor aunque es una variante que se dijo del operador 3-Opt, la búsqueda de Mover Nodo es la siguiente:

Sea la ruta S0 formada por la siguiente estructura:

S0 = a0, a1, … , ai-1, ai, ai+1, ai+2, … , aj-1, aj, aj+1, … , an-2, an-1, an, a0

donde i y j son las dos posiciones a utilizar para realizar el movimiento, este método se basa en desplazar el nodo situado en la posición i a la posición j, como se muestra en la Figura 2.3a. Existen dos posibles variantes para el movimiento del nodo ai, para obtener la nueva solución vecina S1:

1. Si (i < j), el nodo ai se coloca entre el nodo aj y aj+1, lo que resulta:

2. S1 = a0, a1, … , ai-1, ai+1, ai+2, … , aj-1, aj, ai, aj+1, … , an-1, an, a0

3. Si (i > j), el nodo ai se coloca entre el nodo aj-1 y aj, por tanto:

S1 = a0, a1, … , aj-1, ai, aj, aj+1, … , ai-1, ai+1, ai+2, … , an-1, an, a0

como se muestra en la Figura 2.3b y 2.3c respectivamente.

2.3a 2.3b 2.3c

Fig. 2.3 Operador Mover Nodo

Una búsqueda mejorada de éste para disminuir tiempo de ejecución del algoritmo consiste en que para cada iteración de búsqueda con una nueva solución de mejor calidad que la anterior, en función de los nodos i,j, existen soluciones vecinas comunes a las vecindades de la solución actual y anterior que no se tienen en cuenta porque ya fueron exploradas. Este método es O(n2). La evaluación del costo de cada nueva solución posible es parcial y muy rápida, pues para un recorrido de n aristas, solo es necesario evaluar los costos de 3 de ellas.

3.3.2 Operador intercambiar nodo

Este operador es una modificación del operador 4-Opt y consiste solo en intercambiar dos nodos, a diferencias del operador inicial que intercambia dos subrutas. Este operador tiene la siguiente estructura:

Sea la ruta S0 formada como sigue:

S0 = a0, a1, … , ai-1, ai, ai+1, ai+2, … , aj-1, aj, aj+1, … , an-1, an, a0

donde i y j son las posiciones seleccionadas para realizar el movimiento (Figura 2.4a). Se realiza un intercambio entre el nodo ai y aj, por tanto la nueva solución vecina S1 resulta:

S1 = a0, a1, … , ai-1, aj, ai+1, ai+2, … , aj-1, ai, aj+1, … , an-1, an, a0

como se muestra en la Figura 2.4b.

2.4a 2.4b

Fig. 2.4 Operador Intercambiar Nodo.

La mejora de este método es similar al de Mover Nodo con O(n2) operaciones, aunque utiliza menos tiempo computacional. Su movimiento es muy simple, realiza un intercambio de dos variables. De la misma manera la evaluación del costo de cada nueva solución es parcial, pues para un recorrido de n aristas, solo es necesario evaluar los costos de 4 de ellas.