biologo

Investigación de operaciones en acción:
Heurísticas para la solución del TSP
Roger Z. Ríos Mercado*
José Luis González Velarde**
Abstract
One of the most common and difficult problem in
the theory of optimization is that of the Traveling
Salesperson Problem (TSP). The interest in
studying solution techniques is generated by the
great amount of practical applications of decisionmakingproblems where the TSP is seen as a
substructure problem. This article presents a
summary of the most important approximation
methods (heuristics) proposed to try to find feasible
solutions of high quality.
Key words: Investigation Operations in Action,
Traveling Salesperson Problem, Heuristics,
Metaheuristics.
1. INTRODUCCIÓN
En el artículo Investigación de operaciones en
acción:Aplicación del TSP en problemas de
manufactura y logística,1 publicado en la Revista
Ingenierías, Vol. II, No. 4, introdujimos al lector
con el Problema del Agente Viajero (mejor
conocido por TSP, por sus siglas en inglés;
Traveling Salesperson Problem), el cual es un
problema clásico de optimización combinatoria, una
de las subdisciplinas de la investigación de
operaciones (IO). Señalamos cómo lasaplicaciones
de IO se encuentran en prácticamente todos los
niveles y en todo tipo de industrias, y cómo una
utilización adecuada de las técnicas de IO dándole
soporte al complejo proceso de toma de decisiones
que enfrentan las empresas, puede tener un impacto
económico significativo.
En particular, ilustramos la importancia del TSP
con un par de problemas reales: el problema deprogramación de tareas que se presenta en la

manufactura de bienes y el del ruteo de vehículos en
el ramo de la logística.
Como* una de las características del TSP es el de
pertenecer a una clase de problemas muy difíciles
de resolver, es decir, hallar la solución óptima, en la
práctica es muy común el utilizar algoritmos de
aproximación (heurísticas) para obtener soluciones
factibles de altacalidad (relativamente cercanas al
óptimo) en tiempos de ejecución relativamente
pequeños. En este artículo, a manera de
continuación, exponemos algunas de las heurísticas
más utilizadas para intentar obtener soluciones al
TSP.
2. QUÉ ES EL TSP
Retomando la definición efectuada en1, el TSP
se formula de la siguiente manera. Un agente
viajero, partiendo de su ciudad de origen, debe
visitarexactamente una vez cada ciudad de un
conjunto de ellas (previamente especificado) y

*

Programa de Posgrado en Ingeniería de Sistemas
UANL.

**

Centro de Sistemas Integrados de Manufactura
ITESM-Campus Monterrey.

Ingenierías, Octubre-Diciembre 2000, Vol. III, No.9

15

Investigación de operaciones en acción: Heurísticas para la solución del TSP

retornar al punto de partida.Un recorrido con estas
características, es llamado dentro de este contexto
un tour. El problema consiste en encontrar el tour
para el cual la distancia total recorrida sea mínima.
Se asume que se conoce, para cada par de ciudades,
la distancia entre ellas. La Figura 1 ilustra un tour
en una instancia de ocho ciudades, representada por
un grafo donde cada nodo del grafo corresponde a
unaciudad y cada arista que une a un par de nodos
representa la parte del tour que pasa por dichos
nodos. En la figura se ilustra el tour que visita las
ciudades 1, 2, 3, 8, 5, 4, 7, 6 y 1, en ese orden.
1

3

6

5

7

8

Figura 1. Un tour en un TSP de ocho ciudades

El problema en sí es fácil de formular. Sin
embargo, al igual que muchos otros que se
presentan en el campo deoptimización, es
sumamente difícil de resolver (por resolver, nos
referimos a encontrar la solución óptima al
problema y probar desde luego que ésta es
efectivamente la mejor solución posible). En1
establecimos con más detalle cuándo un problema
es “fácil” o “difícil”. La implicación directa de un
problema difícil de resolver es que cualquier
algoritmo empleado para encontrar la solución...