Este artículo es un resumen del webinar «Resolución eficiente del problema del viajante: Solución dinámica basada en callbacks» que se impartió el pasado 23 de Septiembre. El webinar trató sobre la complejidad computacional del problema del viajante, y cómo solucionarlo a través de una solución dinámica basada en callbacks, con ejemplo de aplicación y resultados.
¿Te perdiste el webinar y te gustaría poder verlo?
En el día a día, nuestros sistemas de toma de decisiones deben actuar de forma resolutiva en especial cuando la complejidad de la situación supone un problema para responder a tiempo.
Tal y como contábamos en el artículo «Buscando una solución eficiente para el Problema del Viajante«, el Problema del Viajante o TSP (Travelling Salesman Problem) es uno de los casos más estudiados en Investigación Operativa (OR Operational Research) y en las demás ciencias de computación. El planteamiento del problema es: dada una lista de ciudades y distancias, se debe visitar cada ciudad exactamente una vez y regresar al origen con la ruta más corta posible.
La aparente simplicidad de este problema es engañosa, ya que como veíamos en el artículo: para 5 ciudades existen 12 rutas diferentes, para 10 ciudades existen 181.440 rutas diferentes, y para 30 ciudades hay más de 4 quintillones de rutas posibles.
Este problema se planteó por primera vez en 1930 y desde entonces se ha logrado ir teniendo la solución óptima de este problema, cada vez con un mayor número de ciudades. Algunos de los hitos importantes han sido:
En el problema de crear el tour más corto entre las 24,978 ciudades de Suecia de 2004, se tardó 7 años en tiempo de CPU para encontrar la solución y otros 85 años para garantizar que la solución era óptima.
El objetivo de este webinar es por lo tanto obtener una solución óptima en un tiempo admisible.
Es importante puntualizar que se está exponiendo un problema en el que existe una única ruta, con un único medio de transporte, intentando hacer el problema lo más sencillo posible. Pero la realidad es mucho más complicada ya que en los casos reales existen muchas más opciones, flota, tiempos de recogida y entrega, restricciones, etc.
En este webinar presentamos una aproximación basada en descomposición del problema y resolución por etapas, usando callbacks de manera dinámica para introducir al sistema los datos relevantes en cada etapa.
Para ello, vamos a utilizar técnicas de Programación Lineal, un campo de Optimización Matemática que se encarga de maximizar o minimizar funciones objetivo. Los beneficios de utilizar técnicas de Programación Lineal son: que nos garantizan encontrar la solución óptima, y que existen solvers muy potentes en este campo.
En el webinar se hace un acercamiento entre la representación gráfica del problema y el modelo de programación lineal.
¿Quieres ver cómo modelamos el problema con programación lineal?
En próximos vídeos de nuestro canal de Youtube mostraremos la implementación y el desarrollo de este modelo de Programación Lineal, añadiendo un enlace a un repositorio para la descarga del código.
Si tienes alguna duda sobre el tema, puedes contactar directamente con nosotros, y si quieres saber más sobre decide4AI, y mantenerte al tanto de futuros webinar o acciones, síguenos en las redes sociales (Linkedin, Twitter, Youtube).
La certificación tipo es un procedimiento reconoc...
La gestión de riesgos es hoy crítica para la fij...
Si piensas en productos de consumo, es probable qu...
