Agente Viajero

MÉTODOS DE SOLUCIÓN PARA EL PROBLEMA DEL AGENTE VIAJERO.

El problema de distribuir productos desde ciertos depósitos a usuarios finales desempeña un roll de vital importancia en la gestión desistemas logísticos, teniendo en cuenta que si se planifican de manera eficaz y eficiente pueden significar considerables ahorros para cualquier organización. Esos potenciales ahorros justifican en granmedida la utilización de diversas técnicas y herramientas relacionadas íntimamente con la Investigación de Operaciones, y el desarrollo de ciertos algoritmos, que funcionan como facilitadores de laadecuada planificación que se desea llevar a cabo en dichos procesos.

Sin duda alguna, uno de los mayores problemas más importantes dentro de la distribución física de bienes es el problema del agenteviajero, el cual es definido como: “Dada una red y un costo (O distancia, tiempo, etc.) asociados con cada arco, encuentre un ciclo del mínimo costo (O distancia, tiempo, etc.) total que incluya atodos y cada uno de los nodos exactamente una vez”[1], que no es más que el dilema que tendría un vendedor que necesita iniciar en su residencia (depósito), visitar clientes en varias ciudades (nodos)exactamente una vez y luego regresar a su propia ciudad para minimizar el costo total del esfuerzo (Distancia, tiempo, dinero, etc.) escogiendo la mejor u óptima ruta posible. Este tipo de recorridosbajo la teoría de grafos es lo que se conoce como un recorrido Hamiltoniano, donde partiendo de un depósito se debe recorrer todos los vértices (nodos) y regresar al depósito con la menor distanciatotal recorrida.

“El problema del viajante (TSP) es uno de los problemas más famosos (y quizás el mejor estudiado) en el campo de la optimización combinatoria computacional. A pesar de la aparentesencillez de su planteamiento, el TSP es uno de los más complejos de resolver y existen demostraciones que equiparan la complejidad de su solución a la de otros problemas aparentemente mucho más...