INTRODUCCIÓN A LA APLICACIÓN DEL MÉTODO TABÚ EN PROBLEMA TSP

INTRODUCCIÓN A LA APLICACIÓN DEL

MÉTODO TABÚ EN PROBLEMA TSP
INTRODUCTION TO THE APPLICATION OF THE TABU
METHOD IN TSP PROBLEM

1
Carolina Gómez Rodriguez, 2 Fernando Gómez Hernández

Fecha de recepción: 30 de Octubre de 2019

RESUMEN

En el presente escrito se quiere a dar a conocer los conceptos referentes a la Búsqueda Tabú, la
cual es uno de los algoritmos metaheurísticos aplicado exitosamente para la solución de
optimización global de ruteo y distribuciòn. Sus principales caracteristicas son el uso de la
memoria adaptiva, ya sean cortas o largas, junto con la estrategia de la diversificación exploran
regiones, evitando repetir las soluciones óptimas dadas en las diferentes interacciónes. A partir de
este concepto, se quiere dar a través de un ejemplo, un acercamiento de su posible aplicación para
la solución de TSP (Travel Salesman Problem), el cuál busca la ruta mínima que debe de utilizar el
vendedor para visitar todas las ciudades en una lista dada solo una vez y regrese a la primera
ciudad.

Palabras clave: Método heurístico, Búsqueda Tabú, Memoria, TSP.

ABSTRACT

This paper is intended to publicize the concepts relates to the Tabu Search, which is on of thee
metaheuristic algorithms successfully applied for the global routing and distribution optimization
solution. Its main feature is the use of adaptive memory, whether short or long, together with the
diversification strategy, explore regions, avoiding repeating the optimal solutions given in the
different interactions. From this concept, we want to give, through an example, an approach of its
possible application for the solution of TSP (Travel Salesman Problem), which seeks thee minimum.
route that the seller must use to visit all cities on a list given only once and return to the first city.

Keywords: Heuristic Method, Tabu Searching, Memory, TSP.

INTRODUCCIÓN memorias “Lista Tabú” que registran las

soluciones recientes, las cuales no son
En 1986, Fred Glover creó un nuevo enfoque consideradas en las 3 próximas iteraciones.
llamado Búsqueda Tabú, encargado de
encontrar el óptimo local, utilizando
1
 INTRODUCCIÓN A LA APLICACIÓN DEL MÉTODO TABÚ EN PROBLEMA TSP

Actualmente, no sólo se ha implementado que proporciona es la mejor que se pudo

este algoritmo heuríustico, sino otros para encontrar en cualquier iteración.
resolver el problema del agente viajero, por lo
que la búsqueda tabú, el único procedimiento Generalmente los métodos heurísticos se
general para una optimización de una basan en ideas bastante simples y de sentido
solución global, que puede a molderse a la común, acerca de la forma en que se debe
mayoría de los problemas incluyendo el TSP. buscar una buena solución. Existen
diferentes métodos heurísticos cómo los que
De hecho, la búsqueda tabú puede verse nombraron en la clase de modelos de
como un procedimiento metaheurístico, que Decisión de la Maestría Gerencia de
se caracteriza por realizar una búsqueda Operaciones (ej: Algoritmo de Dijstra, Regla
local, guiando a encontrar las mejores de Johnson, Método de los ahorros). Por lo
soluciones. Por lo tanto, este algoritmo esta general estos métodos se diseñan para
relacionado como una búsqueda inteligente abordar un tipo específico de problema, en
que en cierto modo imite el comportamiento vez de una variedad de aplicaciones.
humano.
Posteriormente surgió la meta heurística,
Con esta herramienta, se desarrollará un
donde el prefijo meta habla de un nivel
ejemplo, con el que se dará una introducción superior ó más allá de la heurística.
a la aplicación de la búsqueda Tabú para
desarrollar el problema de TSP, con el fin de
tener una metodologia para su solución. Definimos la meta heurística como un
procedimiento que aplica alguna regla o
conjunto de reglas basada en una fuente de
conocimiento, siendo este método utilizado
1. MÉTODO METAHEURÍSTICO para problemas que no tienen un algoritmo o
heurística especifica que dé una solución
Antes de enfocarnos en los métodos meta satisfactoria.
heurístico, definiremos uno de sus
antecesores el método heurístico, el cual Algunos de los metas heurísticos más
viene del griego εὑρίσκειν, que significa « usados son búsqueda local, optimización
inventar, hallar ». basada en colonias de hormigas, búsqueda
tabú y algoritmos genéticos(Sarmiento,
El método heurístico es un procedimiento 2014).
que tiene como objetivo “la búsqueda de una
solución factible muy buena, pero no Por lo tanto, la meta heurística se ha
necesariamente una solución óptima, para el convertido en una de las técnicas más
problema específico bajo importantes del paquete de herramientas que
consideración”(Hiller, Frederick. Lieberman, utilizan los profesionales de la Investigación
2010) de operaciones.

El texto de Hillier-Lieberman señala que con

el método heurístico no se puede ofrecer
plena garantía de la calidad de la solución,
2. DEFINICIÓN PROBLEMA
pero que un método heurístico bien diseñado TSP
puede proporcionar una solución que al
menos está cerca de ser óptima. El Problema TPS (siglas en inglés Traveling
Salesman Problem), hace referencia en
La estrategia del método heurístico, se basa español al problema del agente viajero.
en algoritmos iterativos, donde cada iteración
implica la realización de una búsqueda de El suizo Euler es el padre creador de este
una nueva solución que puede ser mejor que problema, ya que quería encontrar caminos y
la anterior. Cuando el algoritmo termina circuitos en el gráfico de la
después de un tiempo razonable, la solución dodecaédrica(Arif, 2016).

2
 INTRODUCCIÓN A LA APLICACIÓN DEL MÉTODO TABÚ EN PROBLEMA TSP

Este problema puede definirse como un NP agente de ventas, el cuál debe visitar cierta
completo y un problema de optimización cantidad de ciudades en un solo viaje.
combinatoria para aplicarse a enrutamiento Si comienza desde su ciudad de origen, el
de vehículos, secuenciación de trabajos, agente determinará cuál ruta debe seguir
análisis de datos combinatorios, entre otros. para visitar cada ciudad para finalizar en su
punto inicial, de manera que se minimice la
Los algoritmos exactos como el que usa el longitud/costos/tiempo total del viaje.
TSP, están diseñados para encontrar la Los problemas TSP se complican a medida
solución óptima o en este caso, la ruta más que se aumenta el número de ciudades,
corta, el cuál se deriva de la siguiente relacionaremos la formulación de las rutas
formulación (Gangadevi, 2018). posibles.
(n−1) !
n n Rutas Posibles=
2
Minimizar ∑ ∑ d ( i, j ) X (i, j) Donde para el ejemplo de la Ilustración 2.
i=1 j=1
( 4−1)! 6
Rutas posibles= = =3
Sujeto a: 2 2
Las tres rutas posibles serían las siguientes:
n
Ruta 1: A-B-D-C-A
∑ X (i , j )=1 i=1 , … , N Ruta 2: A-C-D-B-A
j Ruta 3: A-D-B-C-A
Al aumentar a un número de ciudades, los
n
problemas se vuelven tipo NP-completos
∑ X (i , j )=1 j =1, … , N (complejidad del ejercicio), ya que un
i
computador se tardaría mucho en resolverlo,
es por esto que se han desarrollado
x ( ij ) ∈ X diferentes métodos para poder abordar con
buenas aproximaciones este tipo de
X ( i , j )=0 o 1 problemas.

N : Número de nodos 3. MÉTODO TABÚ

d ( i, j ) :la distancia entre en nodoi y el nodo j
x ( i , j ) :Variables dedecision , donde es 1 cuando La búsqueda Tabú es un algortimo de
búsqueda local que evita que el proceso se
las variables i , j estanincluidas en laruta y 0 detenga en una solución óptima local. Este
cuando no . es utilizado en la mayoria de las veces para
encontrar las soluciones a los problemas de
A continuación, mostraremos un pequeño ruteo y distribución, a través de una
problema del agente viajero con cuatro exploración, delimitada por una lista tabú que
ciudades. clasifica las soluciones óptima como
movimientos tabú, con el fin de que no sean
tomados nuevamente mientras que se realiza
el proceso.

Otra forma de verlo, la búsqueda tabú se

mueve itinerariamente desde una solución x
¿
hacia una x , donde las soluciones admitidas
¿
para N ( x) son determinadas mediante
estructuras de memoria, las cuales pueden
ser a mediano o a largo plazo(Lopez,
Ilustración 1 Problema Agente viajero
Simétrico 4 Ciudades Erasmo. Salas, Oscar. Murillo, 2014).

Este es uno de los problemas clásicos de Este proceso está estructurado por la
optimización, donde hace relación a un memoria, la cual se caracteriza por ser de
3
 INTRODUCCIÓN A LA APLICACIÓN DEL MÉTODO TABÚ EN PROBLEMA TSP

corto y a largo plazo. La de corto plazo se adecuada sin mejorar la mejor

encarga de guardar los eventos o las solución.
soluciones optenidas recientemente y las de
largo plazo, almacenan los datos A continuación se presenta la metodología
denominados eventos con los que se pueden para la implementación de este algoritmo
definir las estrategias de diversificación que (Jaramillo, 2008):
permiten no visitar las mismas regiones
(Hincapié, Ricardo.Rios, Carlos. Gallejo,
 Inicialización: se lee el tamaño de la
2004). Este tipo de memorias funcionan por lista tabú ¿ y el intervalo de
ser recientes, en frecuencia, en calidad, y en diversificación iD . Interación t=0.
influencia.
 Solución Inicial: Se genera una
La búsqueda Tabú incorpora el siguiente
solución inicial y se calcula el valor
concepto que se debe tener en cuenta como
de la función objetivo. Tanto la
la intensificación, es la exploración de una
solución actual como la global deben
región con mayor intensidad de lo normal
estar iguales a la solución inicial.
después de que se haya denominado como
una de las regiones con posibilidad de
encontrar soluciones óptimas(Castañeda,  Búsqueda en el vencindario: Se
escoge la solución no-tabú como la
2009) . Además, contempla los siguientes
solución candidata. Si la solución es
elementos para su mejor que la global, esta debe
construcción(Alancay,Natalia. igualarse a la nueva solución
Villagra,Silvia.Villagra, 2015) candidata.

 Solución Inicial: Solución óptima que  Aspiración: Si no se puede

satisfaga las restricciones y seleccionar una nueva solución o
disminuya el tiempo en la búsqueda. interacción, se debe ignorar la lista
Esta puede ser generada tabú y nombrarla como mejor
aleatoriamente. solución en el vencindario.

 Movimiento: Procedimiento  Actualización Lista: Agregar la

determinístico con el que se genera solución actual a la lista tabú.
una solución aceptable a partir de la
solución inicial.  Mover: Igualar la solución actual a la
solución optima, incrementando las
 Vencindad: Es el conjunto de todas interacciones.
las soluciones aceptables, las cuales
se generan por la ejecución de un  Diversificación: si t mod iD=0 se
movimiento sobre una solución cumple el intervalo de diversificación,
inicial. por lo tanto, se va al paso 2, si no ir
al paso 9.
 Lista Tabú: Como se mencionaba
anteriormente, es una memoria  Terminación: Si se cumpleel criterio
adaptiva que evita que se repitan los de parada, terminar, si no ir al paso
mismos movimientos, con el fin de 3.
evitar visitar las mismas soluciones
aceptables.
Después de introducir los conceptos básicos,
se abordará un ejemplo simple y después se
 Criterio de parada: Una vez regresará al ejemplo del agente viajero.
terminada el procedimiento, déspues
de hacer varias alternativas y se
alcanza un número de búsqueda

4
 INTRODUCCIÓN A LA APLICACIÓN DEL MÉTODO TABÚ EN PROBLEMA TSP

4. APLICACIÓN METODO
TABU EN PROBLEMA TSP

La continuación explicaremos la aplicación

del método tabú en el problema del agente
viajero
El problema radica en elegir las “ligaduras” o
caminos, aquellas ligaduras son los caminos
por las que pasa el agente viajero a lo largo
de su recorrido por todas las ciudades(Khan,
2016). Este método busca siempre minimizar
la distancia total o el costo asociada al
número de ciudades.
El método tabú según el libro de Hilier- Ilustración 3 Ejemplo típico Problema TSP (Hillier-
Lieberman describe el esquema mediante Lieberman)
seis puntos:
1) Algoritmo de búsqueda local: Iniciamos con la solución de la prueba inicial
1-2-3-4-5-6-7-1 (Sumatoria= 69)
En cada iteración se debe seleccionar el Lista tabú: No hay
mejor vecino inmediato de la solución de
prueba y que no esté descartado por la lista Se empieza a realizar las iteraciones:
tabú. Iteración 1
2) Estructura de la vecindad Números a invertir: 3-4
Nueva solución de Prueba:
Especificar cuáles soluciones son vecinas 1-2-4-3-5-6-7-1
inmediatas de la solución de prueba. Caminos borrados: 2-3 y 4-5
3) Forma de los movimientos tabú Caminos agregados 2-4 y 3-5
Busca evitar regresar con rapidez a la Lista Tabú: 2-4 y 3-5
solución de la prueba anterior. Sumatoria distancia total= 65
4) Adición de un movimiento tabú Tabla 1 Iteración 1: Problema TSP

Luego de cada iteración, después de elegir Luego se realiza la segunda iteración:

los dos caminos que se deben agregar a la Iteración 2
solución de prueba actual, se debe incorporar Números a invertir: 3-5-6
estos dos caminos a la lista tabú. Nueva solución de Prueba:
5) Tamaño máximo de la lista tabú 1-2-4-6-5-3-7-1
Caminos borrados: 4-3 y 6-7
Cuatro en total, que corresponde en total a Caminos agregados 4-6 y 3-7
dos de las dos iteraciones más recientes. Lista Tabú: 2-4 y 3-5
6) Regla de detención 4-3 y 3-7
Detener el proceso después de tres Sumatoria distancia total= 64
iteraciones consecutivas sin mejor el valor de Tabla 2 Iteración 2: Problema TSP
la función objetivo
A continuación, el libro refleja esta ruta
A partir de la Ilustración 1, del libro de Hillier-
1-2-4-6-5-3-7-1
Lieberman escogeremos dicho diagrama de
posibles rutas del agente viajero para poder
entender explicar de una forma apropiada el
método tabú.

5
 INTRODUCCIÓN A LA APLICACIÓN DEL MÉTODO TABÚ EN PROBLEMA TSP

6-7 y 5-3
Sumatoria distancia total= 63
Tabla 4: Iteración 4: Problema TSP

Finalmente, el libro nos relaciona cómo sería

la figura con esta nueva solución de prueba.

Ilustración 4 Ejemplo típico Problema TSP (Hillier-

Lieberman)

Iteración 3
Números a invertir: 3-7
Nueva solución de Prueba:
1-2-4-6-5-7-3-1 Ilustración 6 Ejemplo típico Problema TSP (Hillier-
Caminos borrados: 5-3 y 7-1 Lieberman)
Caminos agregados 5-7 y 3-1
Lista Tabú: 2-4 y 3-5 (borrar) Hasta ahora esta iteración ha sido la que
4-3 y 3-7 menor distancia ha tenido con 63 unidades,
5-7 y 3-1 es decir que esta sería nuestra solución
Sumatoria distancia total= 66 óptima.
Tabla 3 Iteración 3: Problema TSP
Cuando realice la programación, el método
A continuación, relacionaremos la nueva ruta computacional utilizado tratará de seguir
1-2-4-6-5-7-3-1 realizando iteraciones, sin embargo, el
método tabú como tiene “memoria”, en ese
caso no permitirá realizar los dos últimos
movimientos guardados en la lista tabú.

Finalmente se realiza la última parte del

modelo de método tabú, sobre la regla de
detención. Esta regla nos indica que las
iteraciones deben detenerse cuando la
solución de prueba actual no tenga vecinos
inmediatos que no estén bloqueados por la
lista tabú
Existen actualmente varias herramientas
computaciones que se podría desarrollar este
tipo de metaheuristica uno de ellos es IOR
Ilustración 5 Ejemplo típico Problema TSP (Hillier-
Lieberman) Tutorial.

Iteración 4
Números a invertir: 5-7
Nueva solución de Prueba:
1-2-4-6-7-5-3-1
Caminos borrados: 6-5 y 7-3
Caminos agregados 6-7 y 5-3
Lista Tabú: 4-3 y 3-7(borrar)
5-7 y 3-1
Imagen 1 Icono IOR Tutorial
6
 INTRODUCCIÓN A LA APLICACIÓN DEL MÉTODO TABÚ EN PROBLEMA TSP

5. CONCLUSIONES

En conclusión, se considera la
metaheurística como una herramienta muy
importante para el desarrollo de problema de
optimización que se presentan en el día a día
de operaciones. El TSP es un ejemplo que
nos muestra que por medio de diferentes
metodologías (Búsqueda Tabú, Algoritmo
Genético, Colonia de Hormigas,entre otros)
se puede solucionar este problema. La
búsqueda Tabú nos da una solución general
y aunque no fue programada, se dío a
Imagen 2 Metodo Computacional Utilizado conocer una introducción para la aplicación
de este método.

REFERENCIAS

Alancay,Natalia. Villagra,Silvia.Villagra, N. (2015). Algoritmos metaheurísticos trayectoriales para

optimizar problemas combinatorios. ICT-UNPA, Univeersidad Nacional de La Patagonia
Austral, 56–75.

Alejandro, F. (2014). Problema del agente viajero. XIKUA Universidad Autónoma Del Estado de
Hidalgo.

rif, Z. (2016). Concentric tabu search algorithm for solving traveling salesman problem(TSP).
Eastern Mediterranean University

B.Raquel. (2017). La metaheurística de Búsqueda Tabú aplicada al problema de enrutamiento de

vehículos.

B, R. (2017). Búsqueda Tabú Multiobjetivo con Enteros-Mixtos y Punto de Referencia. Revista de

Matemática: Teoría y Aplicaciones, 115–150.

Castañeda, M. (2009). Aplicación de la metaheurística búsqueda tabú al problema de la ruta más

corta para una empresa distribuidora de harina de trigo. Universidad Pontifica Bolivariana de
Bucaramanga.

Gangadevi, E. (2018). Implementing tabu search on traveling salesman problem. International

Journal of Advance Research in Science and Engineering, 857–863.

Hiller, Frederick. Lieberman, G. (2010). Introducción a la Investigación de Operaciones (2001st

ed.). Mc Graw Hill.
7
 INTRODUCCIÓN A LA APLICACIÓN DEL MÉTODO TABÚ EN PROBLEMA TSP

Hincapié, Ricardo.Rios, Carlos. Gallejo, R. (2004). Tecnica heurísticas aplicadad al problema del
cartero viajante (TSP). Scientia et Technica Año X, NO 24, 4.

Jaramillo, J. (2008). Programación lineal y algoritmos genéticos para la solución de un problema de

corte. Universidad EAFIT.

Khan, M. (2016). A tabu search approximation for finding the shortest distance using traveling sales
man problem. IOSR Journalofmathematics, 80–84.

Lopez, Erasmo. Salas, Oscar. Murillo, A. (2014). El problema del agente viajero: Algoritmo
determinístico usando búsqueda tabú. Revista de Matemática: Teoría y Aplicaciones, 127–
144.

O.D. Montoya, A.Grajales, R. A. H. (2018). Selección optima de conductores en sistemas de

distribución empleando el algortimo tabú. Ingeniare, Revista Chilena de Ingeniería, 26, 283–
295.

Riojas, A. (2005). Búsqueda tabú conceptos,algoritmo y aplicación al problema de las N-reinas.

Lima.

Sarmiento, A. (2014). Estudio del problema de ruteo de vehículos con balance de carga: Aplicación
de la meta-heurística Búsqueda Tabú. Universidad de La Sabana.