El Problema del Viajante, o en inglés `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.
Este problema consiste en: dado un conjunto de ciudades y la distancia entre cada par de estas ciudades, encontrar el recorrido cuya distancia total recorrida se la mínima posible, pasando una única vez por cada uno de los destinos y regresando a la ciudad de origen.
Algunas de las aplicaciones más interesantes de esta casuística se incluyen en problemas de scheduling, producción y planificación de rutas en empresas de distribución logística y transporte.
La simplicidad aparente del planteamiento del problema es engañosa, ya que el esfuerzo para resolverlo escala de forma exponencial en un caso real, como se puede ver a continuación:
Para 5 ciudades existen 12 rutas diferentes, para 10 ciudades existen 181.440 rutas diferentes, y para 25 ciudades hay más de 7 cuatrillones de rutas posibles.
Un ordenador que calcule un millón de rutas por segundo necesitaría demasiados años para resolverlo. Dicho de otra forma, si se hubiera comenzado a calcular al comienzo de la creación del universo (hace unos 13.400 millones de años) todavía no se habría terminado de calcular.
La siguiente imagen explica gráficamente de manera muy clara la complejidad del problema a tratar:
En decide4AI hemos organizado un webinar como expertos en optimización matemática, en el que presentamos una solución dinámica y eficiente del Problema del Viajante o TSP (Travelling Salesman Problem). Una aproximación basada en la 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.
¿Interesado en asistir al seminario web? El evento «Resolución eficiente del problema del viajante: Solución dinámica basada en callbacks» tendrá lugar el próximo miércoles 23 de septiembre a las 13:00 h CET. El registro es gratuito. ¡Te esperamos!
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...
