MODELO DEL AGENTE VIAJERO

Modelo del Cajero Viajante

I

OBJETIVOS

 Conocer y aplicar el concepto del algoritmo del agente viajero.

 Utilizar el WinQsb o el Lindo como herramientas de software para encontrar una solución.

 Interactuar con los modelos.

II

TEMAS A TRATAR

 Algoritmo del Agente viajero.

 Modelamiento de problemas.

III

MARCO TEORICO

Modelo del Agente Viajero

Dada la siguiente Red:

Modelo del Agente Viajero: Si la Red mostrada arriba representa alternativas de visita del alcalde de Seatle a todas las demás ciudades, pasando por cada una de ellas por una sola vez y los datos de los arcos representan distancias de recorrido en kilómetros ¿Cuál debería ser la trayectoria de desplazamiento, suponiendo que se considera como alternativa de traslado el tramo 2 a 6 ó 6 a 2 con 700 kms. de distancia? ¿Cuál es la distancia total recorrida?

Uso del WinWsb:

Utilizando la opción Network Modeling eligiendo el tipo de problema Problema del agente viajero (Traveling Salesman Problem).

Ingresamos los datos de las distancias entre pares de nodos (la distancia de i a j es la misma que de j a i), agregamos también la distancia de 700 kms. entre los nodos 2 y 6, y 6-2 pedimos la solución del problema eligiendo el Método de Ramificación y Acotamiento (Branch and Bound Method).

Obtenemos la siguiente solución:

La trayectoria de desplazamiento es la mostrada en la gráfica siguiente:

La distancia total recorrida es 6024 Kms.

Modelo Matemático para el problema del Agente Viajero:

Para formular el modelo matemático, en vista de que todos los arcos tienen la misma distancia del nodo i al nodo j que del nodo j al nodo i, podemos utilizar una sola variable por cada arco de la red a efectos de simplificación:

Min 599x12+180x13+497x14+700x26+420x27+691x28+432x34+200x35+345x47+138x56+291x510+526x67+

440x78+432x711+621x712+102x89+452x912+280x1011+114x1013+155x1114+108x1115+140x1116+

469x1215+180x1219+120x1314+386x1316+118x1317+207x1415+403x1619+425x1718+314x1819

St

x12+x13+x14=2

x12+ x26+x27+x28 =2

x13+x34+x35=2

x14+x34+x47=2

x35+x56+x510=2

x26+X56+x67=2

x27+x47+x67+x78=2

x28+x78+x89=2

x89+x912=2

x510+x1011+x1013=2

...