🌉 El problema de los siete puentes
Sobre la historia de los primeros navegantes y guías de viaje, las matemáticas detrás de las aplicaciones de rutas y planos de transportes
Hola, soy Ramiro Aznar y volvemos con más historias, entrevistas y curiosidades en la intersección de la geografía y las tecnologías geoespaciales. Éste es el séptimo episodio, si eres nuevo o nueva aquí, te recomiendo que te suscribas y, también, le puedes echar un ojo a las entregas anteriores donde hablamos de el género y la numeración de las calles, la geocodificación, la viralidad de los mapas, territorios disputados, el GPS y el cerebro espacial.
En esta ocasión trataremos de entender la historia, las matemáticas y el diseño detrás de las aplicaciones de rutas y direcciones, así como los mapas que utilizamos para guiarnos en la red de transporte público de nuestras ciudades. Para ello, la gente de Detalier, un estudio de diseño creativo de Zaragoza, nos contará su proceso para crear la cartografía y señalética del sistema de transporte público urbano de la capital aragonesa. Y por último, Beatriz Hernández, científica de datos e ingeniera de Machine Learning, y que actualmente se encarga del laboratorio de innovación y datos en Paradigma Digital, nos ayudará a comprender las matemáticas y la lógica detrás de los algoritmos de rutas.
De los primeros turistas a las aplicaciones de routing
Orientarse y moverse a través del territorio con determinación supongo que es tan antiguo como la raza humana, desde que nuestros antepasados bajaron de los árboles y se adentraron en la sabana. Pero como europeo, empezaré la historia por los Simpsons de la Historia: los romanos. Conocidos, entre otras muchas cosas, por llenar de caminos todo su Imperio y conectar Europa desde Hispania hasta Palestina. En la mar utilizaban los llamados periplos, documentos donde enumeraban puertos y puntos de referencia, para facilitar el viaje. En tierra tenían los itinerarios, que como su nombre indica, eran un listado de paradas en caminos. Siendo la Tabula Peutingeriana, cuya copia medieval se conserva en la Biblioteca Nacional de Austria en Viena, la más conocida por abarcar todos las rutas existentes en el Imperio Romano1.
De los romanos pasamos a los griegos. El geógrafo griego Pausanias elaboró un impresionante compendio de monumentos o sitios dignos de ser visitados de la Grecia Antigua, algo así como la primera guía turística2. El término "turismo" viene de la raíz griega "tour", un movimiento alrededor de un círculo, y es que, durante la Edad Media, los mapas (o incluso en los tapices del suelo) servían para viajar espiritualmente en lugar de físicamente3. Desde el XVII hasta bien entrados en el XIX los jóvenes aristócratas europeos (y algunos americanos) visitaban las grandes ciudades y parajes naturales del continente, siendo París y Roma paradas obligadas. Estos viajes eran denominados como el Grand Tour. Durante esta época, los atlas empezaron a hacerse muy populares. En Britannia de John Ogilby, por ejemplo, podemos encontrar los primeros mapas de caminos. Las Baedekers, las primeras guías turísticas, tal y como hoy las conocemos, empezaron a aparecer poco después. Éstas fueron sustituidas por las guías azules, siendo las Michelin y las Lonely Planet las más populares.
"Cuánto le debemos a Harry Beck"
En 1933, la ciudad de Londres publicó un revolucionario plano del metro. Este plano, diseñado por Henry (Harry) Beck simplificaba la red en líneas de colores verticales, horizontales y de 45%, diferenciando paradas e intersecciones y, sobre todo, obviando las verdaderas dimensiones de la geografía londinense. El Tube map empezó una larga tradición que continúa hasta nuestros días para representar el transporte urbano como mapas esquemáticos4. Para hablar de planos de transporte público contacté con la gente de Detalier, Javier Lapuerta y Laura Coria junto con Rubén Ariño de Womba Estudio, encargados de diseñar el plano de la red de transporte urbano de Zaragoza.
"Siempre decimos que nuestro diseño no es un mapa de Zaragoza, es un plano de su red de autobuses" me aclaraba Javi nada más comenzar la entrevista. Un plano es un diagrama mucho más esquemático, selectivo y simplificado de una geografía. Pero por esto mismo el reto cartográfico a la hora de tomar decisiones es mucho mayor. Les pedí que me enumerasen los desafíos más importantes que se encontraron durante el proceso.
El primer problema que se encontraron fue visibilizar el entramado de líneas de una manera legible. Laura me explicó la materia prima con la que tendrían que trabajar. "El sistema base de transporte es una red de autobuses, apoyado por una línea de tranvía. No hay metro, todo el transporte público va sobre la superficie. Así, con 36 líneas diurnas (entre las cuales hay dos líneas circulares y tres lanzaderas) y 7 líneas nocturnas, el problema principal es cómo hacer que sean visibles todos los recorridos en formatos pequeños". En el centro este problema se acentuaba ya que multitud de líneas se apelotonaban y confluían en el casco urbano zaragozano. Lo consiguieron, según Javi, "desvirtuando el plano para poder ampliar zonas de mayor confluencia de líneas. Ahí es donde deja de ser un mapa y se transforma en otra cosa."
Además de ampliar o desvirtuar la geografía de las partes con mayor confluencia de líneas, "otra de las decisiones más importantes fue la de probar si con un sistema radial conseguimos que fuera entendible y legible". En mi humilde opinión, ambas decisiones sentaron la base de una cartografía que ha llegado a cosechar éxitos de crítica a nivel profesional pero también a pie de calle.
Calculando ruta…
Hasta ahora hemos hablado solo de un tipo de instrumentos para orientarnos en nuestro viaje: las guías y los mapas. Sin embargo, hoy en día, las compañeras de viaje imprescindibles son las aplicaciones de rutas y direcciones de nuestros móviles. Sin embargo, los aparatos para guiarnos en la carretera tienen un origen bastante remoto y sorprendente.
Los odómetros (o cuentakilómetros) en sus diferentes variedades y formas fueron esenciales para los siguientes pasos en esta evolución tecnológica. Estos instrumentos, que servían para medir distancias, surgieron de manera independiente en la Grecia clásica y en la China de la dinastía Han. Son estos últimos los que desarrollaron el primer sistema de routing que se conoce, el "carro que apuntaba al sur"5. Este artefacto que solía consistir en una carreta de dos ruedas, un mecanismo de engranajes y una figura o muñeco que indicaba el sur, el cual servía como brújula mecánica. Antes de iniciar el viaje se colocaba la figura apuntando al sur, y durante el trayecto la figura permanecía apuntando hacia el sur gracias al sistema de engranajes que estaban conectados con las ruedas del carro.
Con la llegada del automóvil, a principios del siglo XX, empiezan a aparecer dispositivos como el Jones Live Map o Chadwick Road Guide6, discos con instrucciones capaces de rotar en función de la orientación y la distancia recorrida. A finales de los 80, sistemas como el de Etak7 basados en mapas digitales generados por cintas de cassette se empiezan a comercializar. Estas soluciones serán reemplazadas por las nuevas tecnologías que utilizan GPS como TomTom o Garmin, y vendrán ya incorporadas en los propios vehículos. Hoy en día, sin embargo, cualquiera puede navegar usando aplicaciones de cálculo de rutas como Google Maps, Apple Maps u otros servidores de routing.
El camino más corto
La mayoría de estos servicios utilizan algoritmos basados en la teoría de grafos. Recientemente me apunté a este interesante curso sobre el tema impartido por Bea Hernández. Así que aproveché para que nos contase un poco sobre estas estructuras tan peculiares. Bea define los grafos como "un conjunto de nodos y aristas", siendo estas últimas las que conectan un par de nodos. De este modo una red de carreteras o un plano de transporte interurbano como el de Zaragoza se podría simplificar como un grafo. Los vértices o nodos serían las intersecciones, y las aristas serían los caminos.
El primero en darse cuenta de esta analogía fue el matemático suizo Leonhard Euler en 1736, cuando publicó su solución al problema de los puentes de Königsber. Este problema consistía en encontrar un camino que cruzara cada uno de los siete puentes de la ciudad y volviese al punto de origen, pero con la condición que sólo podías atravesar cada uno de los puentes una única vez. Aunque Euler nunca acuñó el término grafo en su manuscrito, sí que utilizó la expresión "geometría de la posición"8, la cual describe perfectamente el fenómeno. Básicamente para resolver el problema de los puentes, el camino no depende de nuestra imaginación o creatividad para hallarlo, sino que es una propiedad emergente de la geometría de las diferentes posiciones de la red de puentes9. Como dice Bea, "son las relaciones las que definen y clasifican a los grafos".
En un grafo podemos definir caminos ("paths" en inglés), que en realidad son subgrafos de nodos siguiendo un determinado orden. El número de nodos que presenta un camino se define como la longitud. En este primer nivel de abstracción, el camino más corto para llegar de un punto a otro punto en un grafo será aquel que presente la menor longitud, o recorra un menor número de nodos. Una vez simplificada nuestra red de carreteras o estaciones de metro en nodos y caminos, podemos aplicar alguno de los llamados algoritmos que buscan la ruta más corta ("shortest path" en inglés) para llegar a nuestro destino de la manera más óptima. Para ello los grafos resultantes deben estar ponderados por un valor de distancia, tiempo, combustible u otra variable que queramos minimizar10. El algoritmo de Dijkstra, por ejemplo, usa estas distancias para recorrer todo el grafo y así obtener el camino más corto.
Bea también citó otro ejemplo de grafos aplicados al mundo cartográfico, el teorema de los cuatro colores. "El teorema dice que cuatro colores son suficientes para colorear un mapa en el que las regiones que comparten una frontera en común no reciban el mismo color. El beef de este problema es que se demostró mediante un ordenador y la prueba no era factible de hacer a mano". Podéis ver en acción cómo implementar esta solución en este estupendo artículo de Alberto Romeu. Es curioso, pero Javi de Detalier nos comentó que iterar a la hora de establecer los colores de las líneas de autobús para que fueran lo más distantes posibles en tramos que compartían recorrido fue de lo más complicado. No sería raro que programas de diseño ya incorporen algoritmos así, ya que en estos últimos tiempos estamos viviendo una verdadera revolución en el campo de las inteligencias generativas. En la siguiente entrega veremos cómo el sector de las tecnologías geoespaciales puede verse afectado por este tsunami de inteligencias artificiales.
Ashworth, M. 2019. Why North is Up. Map Conventions and Where they came from. Bodleian Library. University of Oxford. 224 pp.
Garfield, S. 2013. On the Map. Why the World Looks the Way it Does. Profile Books. 464 pp.
Sáenz-López S., 2021. Pinturas Medievales del Mundo. De Ptolomeo a los satélites: la historia de los mapas. Conferencias Fundación Juan March.
Field, K. 2018. CARTOGRAPHY. Esri Press. 576 pp.
Milner, G. 2017. Pinpoint: How GPS is changing technology, culture, and our minds. W. W. Norton & Company. 322 pp.
La historia de la navegación es fascinante. Los primeros navegantes se guiaban por referencias locales o las estrellas. Los polinesios para poder navegar y colonizar el complejo entramado de las islas del Pacífico, utilizaban un método denominado etak, gracias al cual podían orientarse basándose en función de la posición de las islas cercanas. Recomiendo leer Huth, J. E. 2013. The Lost Art of Finding our Way. Harvard University Press. 528 pp. y el citado Milner, 2017.
Benjamin, A., Chartrand, G. & Zhang, P. 2015. The Fascinating World of Graph Theory. Princeton University Press. 322 pp.
Barabási, A. 2003. Linked: The New Science Of Networks Science Of Networks. Plume Printing. 294 pp.
Cormen, T. H. et al. 2009. Introduction to Algorithms. Third Edition, The MIT Press. 1292 pp.