Un problema sencillo de optimización de redes

Dado que los recursos son limitados, en cualquier sistema se presentan situaciones donde es necesario alcanzar óptimos de diseño o explotación. En esta entrada quisiera plantear un problema clásico de topología aplicado a la ingeniería del transporte, con algunos conceptos matemáticos sencillos, dejando con ello la puerta abierta a profundizar para aquéllos a quienes les despierte curiosidad y deseen investigar en materia de algoritmos, matemáticas, etc.

Supongamos, de manera genérica, que debemos diseñar una red vial para conectar cuatro núcleos de idéntica importancia ubicados en los vértices de un cuadrado, y que están inmersos en un espacio isotrópico bidimensional, es decir, un plano donde todas las propiedades son iguales en cualquier dirección. La única restricción impuesta es que la longitud total de dicha red sea mínima.

En primera instancia se nos ocurren múltiples soluciones posibles. Observando la Figura 1, tendríamos una primera solución (color rojo). Sin pérdida de generalidad podríamos suponer la longitud del lado del cuadrado igual a 1, con lo que esa alternativa inicial tendría una longitud de red igual a 3. Otra solución posible es la planteada en color amarillo donde, con la misma longitud de red que en la roja, se reduce la distancia de trayecto del caso más desfavorable de 3 a 2 unidades. Finalmente todos llegaríamos a la conclusión de que hay un diseño de red óptimo en forma de equis, como muestra el grafo verde de la parte inferior derecha de la Figura 1. Haciendo un número rápido para obtener la longitud de red, el resultado es 2·√2 ≈ 2.828.

Figura 1. Primeras soluciones para el diseño de la red viaria.

No obstante la solución óptima no es ninguna de las anteriores. Hay una configuración geométrica cuya longitud total es menor (Figura 2) y que se asemeja a una doble Y. En este último caso, resolviendo el problema trigonométrico se llega sin dificultad al resultado: una longitud de 1+√3 ≈ 2.732. Como vemos se ha acortado la distancia total sensiblemente, alcanzando el valor óptimo.

Figura 2. Solución óptima con longitud mínima de red.

Este problema matemático de optimización combinatoria se conoce como Problema de árbol de Steiner, para el que existen diversos métodos de resolución. En configuraciones complejas se prestan muy bien para su resolución mediante algoritmos heurísticos, capaces de explorar soluciones más allá de óptimos locales como los de la Figura 1.

Aunque este problema planteado se ha desarrollado en un contexto teórico idealizado, ciertamente es posible encontrar este patrón en redes viarias existentes. En ocasiones es necesario unificar corredores para dos o más rutas por motivos diversos (coste de construcción y explotación, orografía, impacto ambiental, etc.). En concreto, se exhiben a continuación ejemplos en la red de carreteras en España con ánimo exclusivamente ilustrativo. En primer lugar, la Figura 3 muestra la forma de doble Y de la red de carreteras entre las ciudades de Córdoba, Jaén, Granada y Lucena.

Figura 3. Ejemplo de la red de carreteras en Andalucía.

En la Figura 4 se representa la conexión entre Lugo, León, Benavente y Orense, con un extenso tramo común.

Figura 4. Ejemplo de la zona noroeste (Castilla y León y Galicia).

Por último, en la Figura 5 puede observarse otro ejemplo de patrón en doble Y con un corredor común para conectar las localidades de Aranda de Duero, Soria, Almzán y Segovia.

Figura 5. Ejemplo de la red de carreteras en Castilla y León.

Por supuesto, la red es mucho más compleja (afortunadamente) que aquellas conexiones que se muestran y las conexiones perimetrales de los ejemplos dados tienen otras alternativas más ventajosas. No obstante los trayectos diagonales sí se efectúan normalmente por las vías resaltadas.