INVESTIGACIÓN DE OPERACIONES

Tema: Problema del Agente Viajerofcq

Problema del Agente Viajero

En el Problema del Agente Viajero, el objetivo es encontrar un recorrido completo que conecte todos los nodos de una red, visitándolos tan solo una vez y volviendo al punto de partida, y que además minimice la distancia total de la ruta. 

Problema del Agente ViajeroAlgoritmo 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 iHacerSi el nodo más cercano no se ha visitadoVisitar nodo jActualizar lista de nodos visitadosCosto_total = costo_total + costoijNodo i = nodo jHasta haber visitado todos los nodos

Problema del Agente Viajero

Modelo del agente viajero:

Problema del Agente Viajero

Modelo del agente viajero:

Problema del Agente ViajeroEjemplo 1:Un estudiante tiene que visitar 4 bibliotecas las cuales se representan A-B-C-D.

Y su punto de partida es la cuidad o nodo A.

¿Qué ruta debe seguir para que el costo sea mínimo?

La distancia entre los puntos es:A-B=7 B-C=10A-C=9 B-D=4A-D= 8 C-D=15

Problema del Agente Viajero

Se representa mediante el grafo siguiente:

Problema del Agente Viajero

Esta solución se trata de checar todos los caminos posibles.En este ejemplo nos dice que el punto de partida es de la cuidad A .Ya que tenemos todos los caminos posibles eliminamos los inversos, ya que es lo mismo y es perdida de tiempo también andar checándolos.:

Problema del Agente Viajero

Ahora de los 3 caminos inversos, sustituimos por los valores que representa cada distancia de un nodo a otro. Y lo calculamos, el camino que sea menor, eses es la trayectoria que andamos buscando

Problema del Agente ViajeroEjemplo 1:Un estudiante tiene que visitar 4 bibliotecas las cuales se representan A-B-C-D.

Y su punto de partida es la cuidad o nodo A.

¿Qué ruta debe seguir para que el costo sea mínimo?

La distancia entre los puntos es:A-B=7 B-C=10A-C=9 B-D=4A-D= 8 C-D=15

Problema del Agente ViajeroEjemplo 2:

Problema del Agente Viajero

Problema del Agente Viajero

Problema del Agente Viajero

Problema del Agente Viajero

¡Ejercicio!Un repartidor de mercancías tiene encargos en varias ciudades, las cuales se representan A-B-C-D-E, y debe iniciar en la cuidad A¿Qué ruta debe seguir para que el costo sea mínimo?Las distancias son:A-B=7 A-E=20 B-E=11 D-E=17A-C=9B-C=10 C-D=15A-D=8 B-D=4 C-E=5

Problema del Agente Viajero

Se representa mediante el grafo siguiente:

Problema del Agente Viajero

Se obtienen los caminos posibles:

Problema del Agente Viajero

Ahora vamos a eliminar lo inversos.Estos son los caminos que nos quedaron después de eliminar los inversos y sustituyendo los valores de las distancias dadas.

A-B-D-C-E-A=7+4+15+5+20=51A-B-D-E-C-A=7+4+17+5+9=42A-B-C-D-E-A=7+10+15+17+20=69A-B-E-D-C-A= 7+11+17+15+9=59A-D-C-B-E-A=8+15+10+11+20=64A-D-C-E-B-A=8+15+5+11+7=46A-D-E-B-C-A=8+17+11+10+9=55A-D-E-C-B-A=8+17+5+10+7=47A-D-B-C-E-A=8+4+10+5+20=47A-D-B-E-C-A=8+4+11+5+9=37A-C-D-B-E-A=9+15+4+11+20=59A-C-B-D-E-A=9+10+4+17+20=60

Problema del Agente Viajero

Representación del grafo:

Problema del Agente Viajero

Representación del grafo:

Como nos podemos dar cuenta el más optimo es el de 37 kilómetros de distancia.

Bibliografía/Referencias

Taha, Hamdy A. Investigación de operaciones. 7a. edición. México: Pearson Educación, 2004.ISBN 970-26-0498-2

http://www.uaeh.edu.mx/scige/boletin/tlahuelilpan/n3/e5.html

http://www.ingenieriaindustrialonline.com/herramientas-para-el-ingeniero-industrial/investigación-de-operaciones/problema-del-agente-viajero-tsp/