En el año 1832 se publicó en un periódico de la ciudad de Ilmenau (Alemania) un pequeño aviso en una publicación que decía “El Agente Viajero: Qué debe hacer para recibir pedidos y asegurar resultados exitosos en sus negocios – Palabras de un Repartidor”. Este pequeño manual, que traía algunos ejemplos de rutas óptimas para recorrer ciertas regiones de Alemania y Suiza, presentaba tal vez por primera vez al mundo uno de los problemas de optimización más estudiados de la historia: El Problema del Agente Viajero (TSP por sus siglas en inglés).

El problema en principio es muy sencillo: Dado un conjunto de ciudades a visitar, un agente viajero debe encontrar la ruta que le permita visitar todas las ciudades una única vez, asegurando que la distancia que recorra sea mínima. Sin embargo, la complejidad matemática que implica este problema ha capturado la atención de la comunidad científica por décadas.

Una búsqueda rápida en cualquier base de datos académica arrojará con seguridad cientos de miles de artículos científicos que mencionan o se ocupan de resolver el Problema del Agente Viajero, o problemas derivados de este. Las características matemáticas de este problema han despertado el interés de la comunidad científica por siglos, lo que ha llevado al desarrollo de múltiples algoritmos o metodologías que dan solución óptima a este problema.

Aunque el concepto vio la luz en la segunda década del siglo XIX, fue hasta 1930 que la primera formulación matemática de este problema se propuso. El matemático austrohúngaro Karl Menger propuso la formulación matemática del problema que “Para un conjunto dado de puntos con coordenadas conocidas(..)” buscaba encontrar el camino que los conectara, recorriendo la menor distancia posible.

El Agente Viajero y SAS:

Y en este sentido SAS no se queda atrás. Desde su concepción, las soluciones de optimización de SAS han incluido componentes que permiten encontrar rutas óptimas bajo la construcción de un modelo matemático que represente el TSP, y la última entrega de la plataforma SAS Viya no es la excepción a la regla.

Dentro de la solución SAS Optimization on Viya se encuentran disponibles una serie de comandos (Action Sets) dedicados exclusivamente a resolver el Problema del Agente Viajero. Estas acciones son accesibles a través de las interfaces de programación de SAS o incluso utilizando lenguajes Open Source haciendo uso de los paquetes swat y sasoptpy que permiten a estas herramientas comunicarse con el ecosistema SAS y dar solución rápida a problemas de optimización.

El Agente viajero por Colombia usando SAS y Python:

Veamos ahora un ejemplo de cómo resolver este problema utilizando SAS Optimization on Viya y Python juntos, para ayudar a un turista a planear su primera visita a Colombia.

Suponga que su amigo viene de visita de EE.UU. y quiere conocer 10 ciudades de Colombia. Usted, como buen amigo, quiere recomendarle la mejor ruta que le permita visitar estas 10 ciudades y regresar a Bogotá para tomar su vuelo de regreso. La tabla a continuación resume el tiempo que toma moverse entre ciudades:

Con esta información disponible en el servidor CAS de SAS Viya lo primero que debemos hacer es conectarnos al servidor, y cargar las acciones necesarias para trabajar el problema.

Una vez conectados al servidor, creamos una conexión a la tabla en memoria que contiene la información de los orígenes, destinos y tiempos de desplazamiento. Esta tabla, llamada “links_opt”  está almacenada en la librería “Public”. Para ello utilizamos la siguiente sentencia de código:

Hasta ahora hemos abierto una conexión con el servidor CAS y con la Tabla que contiene la información que nos interesa. Con esta información disponible procederemos ahora a resolver el TSP que nos permitirá encontrar la ruta para recorrer estas 10 ciudades en el menor tiempo posible.

Para resolver este problema, utilizaremos el CASAction tsp disponible en el conjunto de acciones de Optimización sobre redes dentro de SAS Optimization. Esta sentencia construirá el modelo matemático necesario para encontrar la ruta óptima y resolverá el problema utilizando los solvers de SAS disponibles en el servidor.

Finalmente almacenamos los resultados del problema en una tabla en CAS para que pueda ser consultada en el futuro.

Conclusión:

 

SAS y Python se unen para permitir dar solución rápida a uno de los problemas de optimización más estudiados en el mundo. Utilizando código Python, logramos en este ejemplo identificar la ruta óptima para visitar 10 ciudades de Colombia dados unos tiempos de desplazamiento entre esas ciudades, y resolvimos el problema utilizando los solvers de SAS.

¿Quieres saber más?