Modelando el Problema del Viajante de Comercio desde los principios fundamentales

El Arte del Viajante de Comercio Modelando el Problema desde sus Principios Fundamentales

👁️ Este es el artículo #2 de la serie que cubre el proyecto “Un Sistema Inteligente de Soporte a Decisiones para el Turismo en Python“. Te animo a que lo consultes para obtener una visión general del proyecto completo. Si solo te interesa cómo modelar el TSP, estás en el lugar correcto, ya que este artículo es autocontenido. Si también te interesa resolver el problema, no solo modelarlo, te encantarán los próximos 5 artículos de la serie. Créeme, te proporcionarán lo que necesitas y lo que no sabías que necesitabas 😉

Tabla de contenidos

1. Motivación y propósito

2. Comprensión de los datos

3. Definir un modelo conceptual a partir de la descripción del problema

4. Construir un modelo matemático a partir del modelo conceptual

• 4.1. Colocar los datos en Conjuntos y Parámetros
• 4.2. Codificar las decisiones en Variables
• 4.3. Definir el Objetivo
• 4.4. Crear las Restricciones

1. Motivación y propósito

Este artículo continúa justo donde el artículo para sprint 1 se quedó. No es necesario haberlo leído para entender lo que haremos aquí, pero permíteme hacer un breve resumen (si ya leíste el artículo anterior, siéntete libre de saltar a la sección 2). En pocas palabras, expusimos los problemas comunes que enfrentan los turistas al planificar un viaje, y nos propusimos construir un sistema que pueda ayudarnos a planificar viajes de manera más efectiva, acelerando la toma de decisiones o incluso automatizando por completo el itinerario para cualquier viaje dado. Observamos que planteado así, el problema es demasiado complejo, por lo que lo descomprimimos y llegamos a su versión esencial, y lo llamamos el problema mínimo valioso. Al final, concluimos que tomó la forma del Problema del Vendedor Viajero (TSP), donde las “ciudades” que el proverbial vendedor debe visitar corresponden, en nuestra versión, a los “sitios de interés” de una ciudad que un turista desea visitar.

Entonces, como punto de partida, primero debemos formular y resolver el TSP, y una vez que eso esté hecho, estaremos en una base sólida para avanzar hacia una solución más sofisticada y general a nuestro problema de planificación de viajes. Elegimos este enfoque porque esta serie de artículos también enseña un enfoque ágil para modelar en Investigación de Operaciones (IO), por lo que muchas de las lecciones, consejos y trucos que encontrarás aquí son aplicables a cualquier tipo de problema al que te puedas enfrentar en IO en general.

Volviendo a nuestro negocio, tenemos la descripción del problema del TSP:

• Todo lo que necesitas saber para desarrollar usando modelos de lenguaje grandes
• Una introducción al Deep Learning para datos secuenciales
• Buscar semántica moderna para imágenes

• Objetivo: caminar la menor distancia posible
• Requisitos: visitar cada sitio solo una vez, y regresar al sitio de partida original (en nuestro caso, el hotel).

Dado que sabemos que este problema no es nuestro problema real, sino una simple aproximación a él, queremos construir un modelo del problema, ya que un modelo se puede refinar, ampliar y ajustar; y sabemos que necesitaremos hacer eso para llegar a una solución a nuestro problema real. Por lo tanto, nuestro objetivo es construir un modelo, en lugar de encontrar una solución directa o idear algún tipo de algoritmo heurístico que encuentre una solución por ti. Una vez que aprendas a razonar de esta manera hacia dicho modelo, tendrás una buena comprensión para ir y leer el artículo del próximo sprint, donde implementaremos el modelo en Python.

2. Comprender los datos

Si recuerdas de nuestra última etapa, la entrada básica para el TSP es una lista de lugares que queremos visitar en un solo día. En este prototipo, estamos utilizando París, así que he elegido estos ocho lugares famosos e imprescindibles:

• Sacre Coeur
• Louvre
• Montmartre
• Port de Suffren
• Arco de Triunfo
• Av. Champs Élysées
• Notre Dame
• Torre Eiffel

Dado que el problema consiste en encontrar un recorrido de distancia mínima, los datos reales que necesitamos son datos de distancia, que dependen de los lugares y sus posiciones geográficas relativas. Cómo calcular los datos de distancia a partir de ubicaciones geográficas se tratará en la etapa 4, ya que cubrirlo ahora implicaría un desvío (con el juego de palabras incluido) que te distraería del enfoque principal aquí: la construcción del modelo.

Por ahora, considera que se te dan las distancias entre todas las posibles parejas. Se proporcionarán en un archivo CSV en el próximo sprint cuando implementemos el modelo en Python. Los datos se ven así:

Llamaremos a esta tabla la matriz de distancias. Nótese que, aunque no es especialmente digno de una postal, el hotel también se incluye en la matriz, ya que cuenta como otro lugar que debe estar en el recorrido final. Para este MVP, mantendremos las cosas simples y utilizaremos una matriz de distancias simétrica, que es una forma elegante de decir que la distancia de 𝐴 a 𝐵 es la misma que la distancia de 𝐵 a 𝐴, para cualquier A y B. En escenarios más avanzados, esto no tiene por qué ser cierto en gran medida, lo que hace que esta aproximación sea ineficaz.

3. Definir un modelo conceptual a partir de la descripción del problema

Ahora nos encontramos en la etapa representada por el bloque verde en el diagrama de flujo siguiente:

El propósito del modelo conceptual es expresar el problema usando palabras, pero en un formato estandarizado, para que la relación entre “oraciones” y “objetos matemáticos” quede clara más adelante en la fase posterior (formulación del modelo matemático). Podemos postular nuestro modelo conceptual de la siguiente manera:

(Conocer)

Datos (conjuntos y parámetros):

• La lista de lugares para visitar
• La distancia entre cualquier par de lugares

(Necesitamos decidir)

Decisiones: En qué orden visitar los lugares

(De manera que)

Objetivo: Minimizar la distancia total recorrida

(De manera que)

Restricciones:

• Todos los lugares son visitados
• Cada lugar se visita solo una vez
• El último lugar visitado es el lugar desde el que empezamos (hacemos un recorrido cerrado)

👁️ Sigue buenas prácticas y, en práctica, la bondad te seguirá

Tal vez hayas pensado que el modelo conceptual parece bastante trivial y no muy diferente del enunciado del problema “simple” con el que empezamos el artículo. Y tendrías razón. Para problemas pequeños como este, puede ser un paso repetitivo. Pero para problemas más grandes, esta etapa es indispensable y tratar de construir un modelo matemático sin tener primero un modelo conceptual generalmente se traduce en caos (requisitos poco claros o vagos, malas formulaciones, código con errores, modelos inviables, etc.) Por lo tanto, es fundamental que construyamos la disciplina ahora y pasemos por esta etapa aquí también, incluso si el valor marginal en nuestro caso simple es muy bajo. Enfócate en buenos hábitos y obtendrás buenos resultados.

4. Construcción de un modelo matemático a partir del modelo conceptual

Acabamos de llegar a la “etapa 3” del flujo de trabajo, en verde a continuación. La etapa del “modelo matemático“, probablemente la etapa más desafiante de todas, es donde el lenguaje natural se convierte en matemáticas.

Es en esta etapa donde ni siquiera se permite la menor cantidad de ambigüedad.

Un modelo matemático bien definido vale cien aclaraciones

En esta etapa de nuestro flujo de trabajo, construimos un modelo puro para el TSP, y en la próxima fase (cubierta en “sprint 3“) construiremos una instancia del modelo a partir del conjunto de datos CSV que explicamos anteriormente, con la ayuda de Python.

📝 Repaso teórico: “modelo abstracto” vs “instancia del modelo”

Los modelos matemáticos (en RO) están compuestos por “componentes”. Estos son todos los elementos (ecuaciones, datos, etc.) que representan colectivamente un problema de una cierta estructura. Lo que realmente define un modelo es su estructura, es decir, cómo se relacionan sus componentes entre sí, independientemente de los valores numéricos particulares que tomen esos componentes en cualquier ejemplo dado.

Una instancia del modelo es una “materialización” específica de un “modelo abstracto” con datos concretos. Por lo tanto, normalmente definimos modelos abstractos y luego los poblamos con datos de escenarios particulares, lo que genera instancias del modelo. Estas instancias del modelo son las que optimizamos para obtener resultados concretos.

En las secciones siguientes, hablaré brevemente sobre los componentes que conforman un modelo y sus propósitos, mientras los defino. Si no eres principiante y ya conoces las funciones de los componentes del modelo, siéntete libre de saltar estas explicaciones y pasar directamente a las definiciones matemáticas.

4.1. Poniendo los datos en Conjuntos y Parámetros

Todos los datos que necesitamos se encuentran en el dataframe mostrado en la Figura 2.1. Podríamos mantener los datos solo allí, recuperando todos los números de ese dataframe al crear las restricciones y objetivos del modelo. De hecho, muchas personas lo hacen, pero es un mal hábito que no es escalable con el tamaño del modelo. A medida que la complejidad del modelo crece, este enfoque requiere cada vez más código de enlace (para lidiar con operaciones de dataframe) que podrían evitarse si los datos se mantuvieran organizados en otras estructuras de datos más orientadas a la construcción de modelos de optimización. Estas estructuras de datos son los conjuntos y parámetros de un modelo.

💡 Estructuras de datos diferentes para satisfacer diferentes necesidades

En caso de que te estés preguntando “¿Por qué crear conjuntos y parámetros cuando ya tenemos los datos que necesitamos en una tabla?”, la respuesta breve es: porque hacerlo facilita la construcción del modelo, lo hace más general y menos propenso a errores.

Los “conjuntos” son los componentes del modelo utilizados para almacenar las principales “entidades” o “elementos” de un problema, mientras que los “parámetros” se utilizan para almacenar las propiedades numéricas de esas entidades o de sus relaciones. En nuestro ejemplo, los sitios son las principales “entidades”, por lo que se almacenarán en un conjunto, y las distancias entre pares de sitios son las “propiedades numéricas” de sus relaciones, por lo que se almacenarán como parámetros. A nivel de implementación, también es muy útil hacer esta categorización porque cada componente cumple una función diferente que facilitará la construcción del modelo:

• La función de los conjuntos es el almacenamiento y manipulación conveniente de índices. Estos índices son los ID o nombres que representan las diferentes “entidades” del problema, y se utilizan para indexar parámetros de manera conveniente para la creación de restricciones y objetivos.

• La función de los parámetros es el almacenamiento y manipulación conveniente de las propiedades numéricas de las “entidades” por las que están indexadas, y estos son los números que aparecen realmente en las restricciones y objetivos.

Desde nuestro modelo conceptual, tenemos:

• La lista de sitios para visitar, que definimos como el conjunto 𝕊:

La frase “indexado por 𝑖, 𝑗” se coloca junto a la definición del conjunto para indicar que cuando los índices 𝑖 o 𝑗 se utilizan en el modelo, representan miembros de 𝕊. De esta manera, cuando tenemos varios conjuntos y, por lo tanto, múltiples índices en uso, es más fácil recordar qué significa cada índice.

• La distancia entre cualquier par de sitios, que definimos como el parámetro indexado 𝐷ᵢⱼ:

El parámetro se llama “indexado” simplemente para indicar que no es un parámetro escalar (es decir, un solo número), sino una matriz 2D de números. Para obtener un número de este parámetro indexado, es necesario especificar dos índices, 𝑖 y 𝑗, que a su vez se tomarán del conjunto 𝕊.

𝕊 y 𝐷ᵢⱼ son los únicos “componentes de datos” presentes en el modelo conceptual. Pero eso no debería limitar nuestra capacidad de crear otros conjuntos o parámetros que sean útiles al construir un modelo.

A modo de ilustración, observe que los índices de 𝐷ᵢⱼ, 𝑖 y 𝑗, son miembros de 𝕊 pero no pueden coincidir. Si lo hicieran, la distancia sería cero, lo cual es un dato trivial. Además, nunca volveríamos de un lugar a sí mismo, por lo que es inútil considerar pares (𝑖, 𝑖) en absoluto. Por lo tanto, es útil limitar las combinaciones que los pares (𝑖, 𝑗) pueden tomar, para que la modelización sea más fácil (y los errores menos probables). Con este fin, creamos ahora otro conjunto, 𝔸, derivado de 𝕊, que contiene todos los pares (𝑖, 𝑗) de sitios diferentes. Cada par representa un arco que conecta el sitio 𝑖 con el sitio 𝑗, de ahí el símbolo 𝔸.

📝 Un arco es simplemente un “enlace dirigido” entre dos nodos de una “red”. Solo piense en un arco (𝑖, 𝑗) como un vector que comienza en 𝑖 y termina en 𝑗. Cuando el “enlace” entre dos nodos no está dirigido (es decir, la dirección es irrelevante), se utiliza la palabra “borde”, ya que decir “arco no dirigido” todo el tiempo sería muy largo. Las personas en la Teoría de Grafos también les gusta ser eficientes.

Una propiedad interesante de 𝔸 es que es el dominio sobre el cual 𝐷ᵢⱼ está definido, y como veremos al implementar el modelo en Python, definir dicho dominio explícitamente lo hace reutilizable para otros componentes del modelo, y eso también es conveniente.

• Conjunto de arcos posibles entre sitios diferentes:

4.2. Codificación de decisiones en variables

Dado que estamos construyendo un modelo para que nos diga qué acciones debemos tomar, y estas acciones prescritas nos son desconocidas antes de que el modelo esté optimizado, debemos codificar en variables todas las posibles acciones que podríamos tomar.

Pero, ¿cómo definimos tales acciones potenciales? Según nuestro modelo conceptual, la “decisión” genérica que necesitamos tomar es el “orden en el cual visitar los sitios”. Este “orden” se refiere a un camino entre todos los caminos posibles que podríamos seguir al hacer un recorrido. La idea clave es que un camino está compuesto por una secuencia de arcos que conectan nodos individuales (es decir, sitios). Por lo tanto, decidir hacer un camino particular es en realidad decidir recorrer una secuencia particular de arcos. Estas “decisiones atómicas” sobre si recorrer o no un arco específico que conecta dos sitios son las decisiones que queremos codificar como variables.

“Si ir o no desde el sitio A al sitio B” es claramente una decisión binaria: o voy, o no voy. Debido a esta naturaleza, las variables de decisión deben ser binarias (es decir, tomando solo los valores 0 o 1) y se definen solo para arcos válidos (para los cuales el conjunto derivado 𝔸 es útil ahora). En términos matemáticos:

Hay una variable de decisión única para cada arco posible (𝑖, 𝑗), pero cuando se optimiza el modelo, solo nos interesan las variables que toman el valor 1, ya que indican qué arcos deben ser recorridos. Por ejemplo, si la variable 𝛿ᵢⱼ, con 𝑖=hotel y 𝑗=Louvre, toma el valor 1, significa que debemos ir desde el hotel al Louvre como parte de nuestro recorrido.

4.3. Definir el objetivo

Imagina que tenemos 4 puntos, 𝑎, 𝑏, 𝑐, 𝑑, y seguimos el camino 𝑎 → 𝑏 → 𝑐, en el que el punto 𝑑 no se visita. Su distancia total es la suma de las distancias de sus arcos: 𝐷ᵃᵇ + 𝐷ᵇᶜ. Pero, si no sabemos de antemano qué camino seguiremos, ¿cómo representamos la distancia total de este camino desconocido?

💡 Precisamente porque el camino óptimo es desconocido, necesitamos una expresión que cubra todos los caminos posibles, pero que se reduzca a la distancia del “mejor camino” cuando se optimice el modelo.

Al aprovechar el hecho de que cualquier arco recorrido (𝑖, 𝑗) tendrá 𝛿ᵢⱼ = 1, y cualquier arco no recorrido (𝑖′,𝑗′) tendrá 𝛿ᵢᑊⱼᑊ = 0, podemos crear una expresión que, una vez que se hayan decidido las variables, se redusca a la distancia total del camino recorrido. La forma de hacer esto es “sumar todas las potencialidades”, es decir, hacer la suma de todas las distancias de arco posibles 𝐷ᵢⱼ ponderadas por sus “variables de arco” binarias 𝛿ᵢⱼ, y permitir que los 0’s y 1’s que tomen esas variables decidan qué distancias permanecen (𝐷ᵢⱼ × 1 = 𝐷ᵢⱼ) y cuáles desaparecen (𝐷ᵢⱼ × 0 = 0), en la expresión de la distancia total. Esta “suma de potencialidades” representa la distancia total que tomará el recorrido final, por lo que será nuestro objetivo (llamado 𝑍) a minimizar.

Matemáticamente, esto se expresa como:

Observa cómo la suma a la derecha se ha vuelto más fácil de leer (y de implementar) gracias al uso de 𝔸, el dominio (conjunto de índices) tanto para 𝐷ᵢⱼ como para 𝛿ᵢⱼ.

Además, debes tener en cuenta que el objetivo constituye nuestra definición de calidad. Dado que queremos minimizarlo, un valor más bajo es mejor que un valor más alto, por lo que claramente, el valor mínimo es el mejor valor. Los valores de las variables de decisión 𝛿ᵢⱼ que corresponden a este valor “mejor” del objetivo constituyen la solución (óptima) al problema, y se encontrarán mediante el proceso de optimización.

4.4. Creación de las restricciones

A partir de nuestro modelo conceptual, tenemos:

1. Se visitan todos los sitios.
2. Cada sitio se visita solo una vez.
3. El último sitio visitado es el sitio desde el que comenzamos (realizamos un recorrido cerrado).

Nos damos cuenta de que el requisito (1) ya está “incluido” en el requisito (2), ya que si cada sitio se visita solo una vez, eso implica que se visitan todos los sitios. Por lo tanto, descartamos la necesidad de una restricción separada para el requisito (1) y nos enfocamos en cómo modelar el requisito (2) como una restricción.

Decir que “cada sitio se visita solo una vez” es lo mismo que decir que “cada sitio se entra y se sale solo una vez”. Y esa frase, a su vez, es equivalente a estas dos frases juntas: “cada sitio se entra solo una vez” y “cada sitio se sale solo una vez”. Vamos a modelar las “frases” por separado:

• Cada sitio se entra solo una vez:

Es útil leer toda la expresión de derecha a izquierda. Si primero ves sobre qué índices se define la restricción, interpretar el significado de la definición de la restricción en el lado izquierdo será más fácil. Yo leería esta restricción en voz alta como:

para cada sitio 𝑗 perteneciente al conjunto de todos los sitios 𝕊, la suma de todos los arcos potenciales 𝛿ᵢⱼ que llegan a 𝑗 debe ser igual a 1, lo que significa que solo debe ocurrir un arco entrante en 𝑗. O, más coloquialmente: cada sitio debe ser visitado desde solo un sitio.

• Cada sitio se sale solo una vez:

Yo leería esta restricción como:

para cada sitio 𝑖 perteneciente al conjunto de todos los sitios 𝕊, la suma de todos los arcos potenciales 𝛿ᵢⱼ que parten de 𝑖 debe ser igual a 1, lo que significa que solo debe ocurrir un arco saliente en 𝑖. O, más coloquialmente: cada sitio debe partir hacia solo otro sitio.

Únicamente nos queda el requisito (3). Indica que la ruta óptima debe terminar en el mismo sitio desde el que comenzamos, o equivalentemente, que la ruta debe ser un recorrido (un lazo cerrado). Aquí hay una posible línea de razonamiento que se puede tener a simple vista: “Dado que ya hemos creado restricciones para garantizar que cada sitio se entra y sale una vez, esto implica que la ruta resultante debe ser cerrada, ya que es imposible que cualquier sitio sea un “sumidero” (es decir, un sitio tiene un arco entrante pero no arcos salientes) o sea una “fuente” (es decir, un sitio tiene un arco saliente pero no arcos entrantes). Por lo tanto, las dos restricciones anteriores, presumiblemente, obligan a que la trayectoria final sea un lazo cerrado“.

¿Es correcta esa línea de razonamiento? Vamos a tomar un enfoque experimental. Asumamos que esta razón es correcta y tratemos de resolver el modelo tal como está ahora. Cuando veamos la solución, veremos si parece correcta o si algo está mal. Si los resultados son incorrectos (o no tienen sentido de ninguna manera), siempre podemos volver atrás y revisar nuestra lógica (algo que sucede todo el tiempo en proyectos de la vida real). La implementación, solución y “validación experimental” es lo que se cubre en nuestro “próximo sprint”, donde se crea un modelo en Python, se resuelve, se inspecciona y se reformula en base a los resultados que obtenemos.

Así concluimos aquí (tentativamente) la etapa de “formulación del modelo matemático”. Siguiente parada: la “implementación del modelo informático”, realizada en Implementando, resolviendo y visualizando el problema del vendedor viajero con Python.

Habrá más artículos de más “sprints” en camino, así que si tienes ganas de ser mi compañero en este viaje, mantente atento y consulta la línea de tiempo del proyecto en la sección 3 del primer artículo de esta serie, para navegar hacia el sprint que desees y seguir el trabajo que se está realizando allí.

También siéntete libre de seguirme, hacerme preguntas en los comentarios, darme retroalimentación o contactarme en LinkedIn.

¡Gracias por leer y nos vemos en el próximo! 📈😊

Referencias:

• Wikipedia. El problema del vendedor viajero

We will continue to update Zepes; if you have any questions or suggestions, please contact us!