VENDEDOR VIAJERO.
Este es la problemática más cotidiana y más complicada de solucionar dentro de los problemas logísticos para cualquier empresa. ¿Cual es la manera optima para repartir o recorrer ciertos lugares de la manera más rápida y menos costosa? Esta problemática pertenece a la categoría de NP - Completo, por ende, no posee una solución polinomial optima. Existen aproximaciones heurísticas para esto, que llegan a buenos resultados, pero no podemos tener la certeza de que sean óptimos.
Una solución intuitiva para resolver esto sería evaluar cada una de las opciones, pero a través de un cálculo simple podemos darnos cuenta que este proceso es una permutación de todos los nodos y la complejidad de esto es de n!, lo que si utilizáramos 8 nodos, ya tenemos que evaluar más de 40000 posibilidades. Con 20 o más, ya se hace prácticamente imposible manejar esta cantidad de datos manualmente. Incluso a través de una computadora, necesitamos bastante tiempo y capacidad de procesamiento para calcular estas posibilidades
Para modelar este problema se utiliza un grafo multidireccional, con un peso o costo o determinado entre cada nodo
Aquí podemos ver 4 destinos y la oficina principal, con el costo asociado a cada camino. Para resolver esta situación utilizaremos un software muy usado en temas de estadística y cálculos numéricos, llamado WINQSB.
Para esto, creamos la matriz de adyacencia de este grafo
La forma en que calculara la solución es buscando todos los ciclos posibles para este grafo y retornara el resultado menos, es decir, el menos costoso.
Luego de calcular, el programa nos retorna la siguiente información
El recorrido optimo seria entonces Oficina Central - Lugar 3 - Lugar 4 - lugar 2 - Lugar 1 - Oficina central. El costo total del ciclo es de 195. Gráficamente, el camino se ve así
