Vendedor Viajero

INTRODUCCIÓN
En transporte, los modelos estocásticos y su aplicación tratan de resolver problemas y desarrollar algoritmos que optimicen las situaciones en que se desea encontrar una solución de lamanera eficaz.
En este caso, se profundizará acerca de uno de los algoritmos más importantes y utilizados en ingeniería donde se requiera reducir costos y distancias. Hablamos del PROBLEMA DELVENDEDOR VIAJERO.
El Problema del vendedor viajero (TSP en inglés por sus siglas de Traveling Salesman Problem) está catalogado como un NP-HARD (Non-deterministic polynomial-time hard) es decir, se tratade un problema no-determinístico (estocástico) y su dificultad aumenta de manera exponencial con el tamaño del problema a resolver.
TSP uno de los problemas clásicos de optimización, se formula dela siguiente manera: Un agente viajero, partiendo de su ciudad de origen, debe visitar exactamente una vez cada ciudad de un conjunto de ellas (previamente especificado) y retornar al punto de partida.Un recorrido con estas características, es llamado dentro de este contexto un tour.
Consiste fundamentalmente en encontrar el camino mínimo con el cual llegar a todos los puntos de un grafo,saliendo desde un nodo y retornando al mismo (por ejemplo a-b-c-d-e-f-a, en la figura)

Figura 1. Grafo de inicio y fin en mismo nodo (a). TSP
Fuente: Elaboración propia




Formalmente el problemase puede representar como grafo completo orientado. Los nodos pueden representar localidades (puntos de interés, ciudades, comercios, etc) y sus valores asociados a las aristas, las distancias (peso,costo) entre ellas. Se destaca que estas magnitudes jamás toman valores negativos.
La finalidad del problema radica principalmente en que dese un nodo seleccionado como de inicio, se debe visitar elresto una sola vez y regresar al vértice de partida, de forma que una función de coste sea optimizada.

ALGORITMOS DE RESOLUCION DEL TSP
Existen múltiples formas tradicionales de representar y...