Capítulo 3. Problema Del Agente Viajero

Capítulo 3. Problema del Agente Viajero

Problema del Agente
Capítulo 3.
Viajero
índice

figuras

tablas

1

2

3

4

5

referencias

Optimización es uno de los temas con mayor debate dentro del área de cómputo. En este
campo, el Problema del Agente Viajero (PAV) es uno de los problemas de optimización con
mayor estudio.
En este capítulo daremos una breve descripción delProblema del Agente Viajero (PAV),
analizaremos algunas aplicaciones relacionadas con el mismo y explicaremos cómo se
relaciona con el problema que tratamos de resolver.
En este proyecto, el problema de optimización es visto como una analogía del PAV con
algunas características en su planteamiento. Nosotros lo vamos a llamar el Agente Viajero
Multidimensional.
3.1 Descripción del problemadel Agente Viajero (PAV)
3.2 Formalización del Problema del Agente Viajero
3.3 Problemas relacionados con el PAV
3.4 Problema del Agente Viajero Multidimensional
3.5 Aplicaciones prácticas

3.1 Descripción del problema del Agente Viajero (PAV)
Indiscutiblemente, el PAV es quizá el problema de optimización combinatoria más popular de
todos (Reyes, 1996). De la manera más simple, el Problemadel Agente Viajero (PAV)
consiste, en que dadas un conjunto de ciudades, un vendedor debe visitar cada una de ellas y
regresar a su ciudad de partida, de tal forma que su recorrido sea mínimo (Figura 3.1).

Figura 3.1 Problema del Agente Viajero

3.1

1

Capítulo 3. Problema del Agente Viajero

3.2 Formalización del Problema del Agente Viajero
Muchos de los problemas de optimizacióncombinatoria pueden ser formulados como
problemas de grafos (Reinelt, 1994). Por tanto, antes de definir formalmente el Problema del
Agente Viajero vamos a revisar brevemente algunos conceptos de la Teoría de Grafos.

3.2.1 Teoría de Grafos
En la tabla 3.1 se definirán algunos conceptos que vamos a utilizar sobre esta teoría:

Tabla 3.1 Teoría de grafos. (Reinelt, 1994)

Un CircuitoEureliano es, un camino cerrado que recorre todas las aristas de un grafo
exactamente una sola vez.

3.2.2 Definición formal del PAV
Dado un grafo conexo K n con pesos en sus aristas C uv , encontrar el Circuito de Hamilton
más corto en K n .
Podemos esquematizar el problema del Agente Viajero en la siguiente gráfica ( Figura 3.2 ):

Figura 3.2 PAV

Se dice que un problema de Agente Viajeroes s imétrico cuando se considera el caso de
grafos y a simétrico en los digrafos.
Un PAV simétrico, satisface la desigualdad del triángulo si: C uv
C uw + C wv para todos
los distintos nodos u , v, w
V . E stos son problemas donde los nodos corresponden a
puntos en el espacio y donde los pesos de las aristas se calculan por medio de la evaluación de
alguna métrica de distancia entre lospuntos correspondientes (Reinelt, 1994).
Un ejemplo de este tipo de problemas, es el PAV Euclidiano. Este problema está definido por
un conjunto de puntos en un plano. El grafo correspondiente contiene un nodo para cada
punto y los pesos de las aristas son dados por la distancia Euclidiana.
3.2

2

Capítulo 3. Problema del Agente Viajero
Este enfoque es el que será utilizado para laoptimización de puntos en las trayectorias de un
robot industrial, que es el objetivo de este proyecto.

3.3 Problemas relacionados con el PAV
Muchos problemas prácticos creen encontrar un modelo de optimización en el Problema del
Agente Viajero. Sin embargo, en muchos de estos casos, la argumentación del PAV no es tan
clara ni tan pura.
A continuación se describen algunos problemas deoptimización que están relacionados con el
PAV.
♦ PAV para grafos en general.
Supongamos que existe un grafo arbitrario G = (V,E), n o completo y deseamos
encontrar el Circuito de Hamilton más corto.
Para resolver este problema podemos hacer lo siguiente: asignamos un peso M
suficientemente grande para cada una de las aristas que faltan y aplicamos el
problema del PAV para un grafo completo. El...