El Vendedor Viajero

El problema del vendedor viajero consiste en que dado un deposito y N clientes se desea encontrar la ruta TSP la cual comienza y termina en el deposito esta ruta visita cada cliente una única vez y cuya longitud es minima.

Para este problema se utiliza un solo vehiculo no hay restricciones de capacidad se puede minimizar la distancia, sin ventanas de tiempo, sin restricciones de compatibilidad y maximizar los costos.

En este tipo de problemas las ciudades se le llaman nodos y a los caminos entre las ciudades se le llaman arcos, un arco puede ser dirigido y no dirigido, si es digido se puede ir solo desde el nodo inicial al terminal como una calle con un solo sentido, si el arco no es dirigido significa que se puede recorrer en ambos sentidos, cada arco se le puede asociar una distancia o costo social a evaluar, una capacidad minima o máxima.

El problema del vendedor viajero se situa dentro de un grafo, en este caso tenemos 5 nodos que representan ciudades del oriente del país, donde el vendedor debe desplazarse ofreciendo mercadería, los nodos fueron denominado con los nombre de las ciudades : maturin, Barcelona, el tigre, anaco y pto Ordaz, considerando a demás que para arco existe un costo social, el problema consiste que el vendedor viajero partira desde un nodo pasando por todos nodos del grafo hasta regresar al nodo inicial, esto debe hacerlo considerando el menor costo posible, ahora bien resolveremos este problemas.

Un primer método seria utilizar la intuición y proponer una ruta que se considere como la menos costosa para que el vendedor la recorra, podemos decir que abra una ruta que parte desde MATURIN, BARCELONA , EL TIGRE, ANACO, PTO ORDAZ para luego volver a MATURIN, es decir, hacer la ruta por afuera la suma de los costos asociado de esta ruta seria de 241, también podría trata de hacer una segunda ruta, saliendo de MATURIN, BARCELONA EL TIGRE, PTO ORDAZ, ANACO y volviendo a MATURIN, esta ruta es mayor que la primera por lo tanto esta descartada, asi podemos probar una tercera ruta, MATURIN, BARCELONA,PTO ORDAZ,ANACO, EL TIGRE y por ultimo MATURIN, al ser mas grande también la descartamos y asi podríamos seguir probando por mucho tiempo distintas rutas.

Diapositiva 4

PERO ¿cuantas son las rutas posibles que podría considerar el vendedor viajero?

Si pensamos un poco podemos concluir que si se tiene un conjunto finito de nodos ES DECIR “N” NODOS tenemos una cantidad finita de rutas posibles, en este caso con 5 nodos y haciendo las combinaciones de rutas posibles podemos identificar que tenemos posibles 24 rutas factibles, en términos matematicos podemos usar una herramienta para agrupa de forma distinta una colección de elementos es posible concluir que cuando se tiene N nodos la cantidad de rutas posibles será de (n-1)! , en este caso como “n” vale “5” es posible determinar el numero de rutas calculando el factorial de 4, el factorial es una herramienta matematica que permite realizar permutaciones, es decir resolver el problema de cómo se agrupan una cantidad finita de elementos de orden distinta.

Si observamos cuando se calculan todas las rutas posibles podemos ver que cada una de ellas esta dupliacada es decir el valor de la ruta : MATURIN, EL TIGRE, PTO ORDAZ, ANACO, BARCELONA, MARTURIN es el mismo que MATURIN, BARCELONA, ANACO , PTO ORDAZ, EL TIGRE , MATURIN, en términos matematicos podemos concluir que la formula de (n-1)! Es correcta , sin embargo la cantidad de rutas reales que se van a considerar corresponde a (n-1)!/2 que en el ejemplo nos da 12 rutas posibles.

Este método que acabamos de utilizar y que considera todas las rutas posibles para luego ofrecer la de menor costo es conocido como el METODO DE LA FUERZA BRUTA, este es el método mas efectivo que podemos encontrar ya que no da lugar a error sin embargo este método se puede tornar muy engorroso para una cantidad considerable

...