La solución del problema del viajante con la ayuda de la gestión económico-matemático de simulación

Definición del problema:

El problema del Vendedor Viajero, también conocido como Problema del Viajante, es un problema que a primera vista parece sencillo de resolver, pero en la práctica es un problema matemático en el cual su solución representa un gran problema. Esto ocurre dado que en teoría se conoce la forma de resolverlo, pero en la práctica aquella solución no es aplicable debido al gran tiempo computacional que demanda, inclusive para conjuntos pequeños de ciudades.

Para su solución se han aplicado distintas técnicas computacionales, entre ellas heurísticas, redes de Hopfield, algoritmos genéticos, etc.

En qué consiste el problema:

Consiste en un agente de ventas que tiene “n” ciudades por visitar, comenzando y terminando en la misma cuidad, visitando solamente una vez cada cuidad, y haciendo que el recorrido sea el costo mínimo, este costo puede estar expresado en términos de tiempo o distancia, es decir recorre el mínimo de kilómetros o lleva a cabo un torn en el menor tiempo posible.

El problema consiste en encontrar una ruta que, empezando y terminando en la misma ciudad, recorra sólo una vez las ciudades restantes y que a la vez esta ruta sea la mínima posible.

Los costos son simétricos en el sentido de que viajar desde la ciudad X a la ciudad Y tiene el mismo costo que viajar desde la ciudad Y a la ciudad X. La condición de visitar todas las ciudades implica que el problema se reduce a decidir en qué orden las ciudades van a ser visitadas.

Complejidad computacional:

El problema del Vendedor Viajero es un problema NP

Completo en un orden de complejidad exponencial.

No existe una solución polinómica.

Podemos aplicar técnicas heurísticas ,obteniendo

Soluciones aproximadas en un 97% ,no necesariamente

optimas.

Pseudocódigo:

Algoritmo 2-Òptimo

Un movimiento 2-opt consiste en eliminar dos aristas, para posteriormente conectar los 4 vértices que quedaron desconectados de una forma distinta, obteniendo una nueva ruta

El algoritmo trabaja con una variable, en este caso x = 1. Mientras este valor sea uno, se marcan todos los vértices como no visitados y a x se le asigna el valor 0, x = 0. Bajo estas dos nuevas condiciones, mientras queden vértices a ser explorados, se selecciona un vértice i y se examinan todos los movimientos 2-opt que incluyan la arista del vértice i al siguiente vértice de la ruta. Si con alguno de los movimientos hechos se reduce el la longitud de la ruta, se realiza el mejor movimiento y se actualiza el valor de x a x = 1, en caso contrario se asigna el vértice i como visitado y se sigue con el ciclo.

A continuación un pseudo-código del algoritmo 2-óptimo[1]:

begin

R = (y1, y2, ……, yn) //la actual ruta

repeat

max <- 0;

for i <- 1 to (n-2) do

for j <- (i+2) to n or n(n-1) do //el ultimo caso solo se da

cuando i = 1

if (w(xi) + w(xj)) – (w(yp) + w(yq)) > max then

begin

max <- (w(xi) + w(xj)) – (w(yp) + w(yq));

save i and j

end;

if max > 0 then R <- R – {xi, xj} U {yp, yq}

until max=0

end

Análisis asintótico del algoritmo:

Todos los algoritmos requeridos para resolverlos requieren

tiempo exponencial en el peor caso. Es decir, son sumamente

difíciles de resolver.

— El análisis asintótico seria: N!

Por que con forma aunmente los nodos exitiras mas rutas por recorrer.

Estructuras de datos utilizadas:

Fue mediante arboles.

El problema lo represente mediante grafos

El problema se puede moldear fácilmente mediante un grafo completo dirigido, en donde los vértices son las ciudades y los arcos son los caminos, dichos arcos deben de tener un peso, y este representa la distancia que hay entre dos vértices que están conectados por medio de dicho arcos.

Ejemplos:

Ejemplo # 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=10

A-C=9 B-D=4

A-D= 8 C-D=15

Se representa mediante el grafo siguiente:

Solución por medio de fuerza bruta:

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.

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

En esta imagen la represento en color rojo

Ahora también lo podemos hacer por la técnica de heurística – mediante el vecino más cercano

Si nos damos cuenta analizamos del nodo A es menos distancia digiriese hacia el nodo B y del nodo B es menos distancia dirigirnos hacia el nodo C y de ahí hacia el nodo D y por ultimo regresar hacia el nodo A.

La solución nos salió igual que la que calculamos por

...