Agente Viajero

AGENTE VIAJERO

INTEGRANTES
Saira Melissa Colindres.
 Enmanuel
 Keidy Oseguera.
 Rachel Alonzo.


DESCRIPCIÓN
El problema del agente viajero consiste en
buscar minimizar la distancia, el tiempoo el
costo de realizar una secuencia entre unos
nodos que no necesariamente tienen que ser
ciudades, sino que pueden ser puntos,
estaciones, entre otros.

CARACTERÍSTICAS


TSP se encuentraclasificado como Problema
de optimización Combinatoria.

Las variables que se pueden adoptar
dependen de cada problema, por ejemplo:
Control de semáforos: Número de semáforos
(nodos), tiempo de trasladoentre semáforos,
cantidad de autos que pasan por un punto,
entre otras variables.


Las variables que han sido empleadas por la
mayoría de los investigadores que dan solución
a TSP son:
 Tiempo derecorrido entre ciudades: horas,
minutos, días, semanas, etc.
 Distancia de recorrido entre ciudades:
metros, kilómetros, millas, milímetros, etc.
 Costo de traslado: dinero, desgaste de las
piezas,gasto de energía, etc.

SUS APLICACIONES
Reparto de productos
 Transporte
 Robótica.
 Turismo y agencias de viajes.
 Horarios de transportes laborales y/o
escolares.
 Inspecciones a sitiosremotos.
 Secuencias.


ALGORITMO DE SOLUCIÓN
El Problema del Agente Viajero puede
resolverse de diferentes maneras:
 Enumeración de todas las soluciones
factibles.
 Métodos exactos
 Heurísticas.
Algoritmos genéticos
 Redes neuronales
 Colonia de hormigas (ACO)
 Búsqueda Tabú
 Combinación de propuestas

ALGORITMO BASE
Definir el número de nodos, su posición y el costo por
cada arista (i, j)donde i = ciudad 1 y j = ciudad 2
Elegir el nodo inicial i
Hacer
 Si el nodo más cercano no se ha visitado
Visitar nodo j
 Actualizar lista de nodos visitados
Costo_total = costo_total + costoij
Nodoi = nodo j
Hasta haber visitado todos los nodos
 


CONCLUSIONES


El problema del Agente Viajero (TSP) es un
problema cuya solución ha sido estudiada
desde los inicios de la Inteligencia...