Flatten SF: el ruteo multiobjetivo entre distancia y ascenso

⏱️ Lectura: 17 min

Flatten SF calcula, dentro del navegador y sobre 160.000 tramos de calle de San Francisco, la ruta a pie o en bici que evita las cuestas más empinadas de la ciudad. Lo logra combinando datos de elevación lidar de 1 metro del programa 3D Elevation del USGS con el grafo de calles de Overture y OpenStreetMap, resolviendo lo que en teoría de grafos se llama ruteo multiobjetivo, es decir, encontrar en vez de una sola ruta óptima el conjunto completo de rutas que compiten entre distancia y ascenso.

📑 En este artículo

1. TL;DR
2. ¿Qué es el ruteo multiobjetivo?
3. Por qué importa
4. Cómo funciona por dentro
5. Ejemplos prácticos y cómo empezar
6. Casos de uso reales
7. Errores comunes y buenas prácticas
8. Comparativa con alternativas
9. Profundizando
10. Preguntas frecuentes
    1. ¿Qué diferencia a Flatten SF de un buscador de ruta más corta tradicional?
    2. ¿Hace falta lidar de alta resolución o sirve con SRTM de 30 metros?
    3. ¿Cómo calcula Flatten SF el ascenso de cada calle?
    4. ¿Flatten SF sirve para planear rutas en bicicleta?
    5. ¿Se puede aplicar esta frontera de rutas óptimas a otra ciudad fuera de San Francisco?
    6. ¿Qué algoritmo usa Flatten SF para hallar rutas pareto-óptimas?
11. Referencias
    1. 📚 Artículos relacionados

TL;DR

• Flatten SF calcula rutas pareto-óptimas entre distancia y ascenso sobre 160.000 tramos de calle de San Francisco.
• El lidar de 1 metro del USGS mide el ascenso real de cada cuadra; el grafo de calles sale de Overture y OpenStreetMap.
• Un pie de ascenso cuesta como 200 pies caminados; pasado ese límite, la ruta deja de valer la pena.
• Sumar el ascenso acumulado, no la diferencia neta entre inicio y final, evita subestimar calles con subidas y bajadas.
• Barrer un peso lambda entre distancia y ascenso en Dijkstra reconstruye la frontera de rutas óptimas.

¿Qué es el ruteo multiobjetivo?

El ruteo multiobjetivo es una técnica de optimización en grafos que busca, en lugar de una sola ruta mínima, todas las rutas que ningún otro camino supera a la vez en dos o más criterios, por ejemplo distancia y ascenso acumulado. Ese conjunto no dominado se llama frontera de Pareto.

Un ejemplo simple ayuda a entenderlo. Si hay dos rutas entre el mismo origen y destino, una de 2,1 km con 18 metros de ascenso y otra de 2,4 km con 30 metros de ascenso, la primera domina a la segunda porque es más corta y más plana al mismo tiempo. Por eso la segunda nunca aparece en la frontera. Ahora imaginá una tercera ruta de 1,8 km con 45 metros de ascenso. Ninguna de las tres domina a las otras dos, porque cada una gana en un criterio distinto, así que las tres quedan en la frontera de Pareto.

Por qué importa

Un algoritmo de ruta más corta no distingue entre una cuadra plana y una escalada de 15% de pendiente, porque ambas valen lo mismo si miden la misma distancia. En una ciudad como San Francisco, con cuestas de más de 20 grados en zonas como Russian Hill o Potrero Hill, esa diferencia decide si alguien camina diez minutos o empuja una bici cargada cuesta arriba.

El mismo problema aparece en decenas de ciudades con relieve marcado, desde La Paz y Medellín hasta Quito y Lisboa. Una aplicación que solo optimiza distancia manda al peatón por la ruta más corta aunque esa ruta suba 80 metros en tres cuadras, cuando a cien metros hay un desvío casi plano que tarda apenas dos minutos más.

Para ciclistas el problema es aún mayor, porque una pendiente de más del 12% puede ser imposible de subir con una bici cargada, y bajarla sin control resulta peligroso.

Las herramientas de accesibilidad llevan el problema un paso más allá. Una persona en silla de ruedas no solo prefiere evitar cuestas, sino que directamente no puede subir una con más de cierto grado de inclinación. Ahí el ruteo multiobjetivo deja de ser una comodidad: se convierte en la diferencia entre una ruta posible y una imposible.

Cómo funciona por dentro

El primer insumo es el terreno. El 3D Elevation Program (3DEP) del USGS cubre buena parte de Estados Unidos con nubes de puntos lidar que resuelven la altura del suelo cada metro. Flatten SF convierte esa nube en un modelo digital de elevación (DEM), una grilla donde cada celda guarda una altura en metros.

El segundo insumo es la calle. El grafo sale de Overture Maps, una fundación creada en 2022 por Amazon, Meta, Microsoft y TomTom bajo la Linux Foundation que limpia y republica los datos de OpenStreetMap en un esquema más fácil de consumir. De ahí salen los 160.000 tramos de calle que forman los nodos y aristas del grafo de San Francisco.

El paso que conecta ambos mundos es el muestreo. Un tramo de calle no es una línea recta entre dos intersecciones, así que Flatten SF toma varios puntos a lo largo de cada segmento, no solo sus dos extremos, consulta la altura de cada punto en el DEM y arma un perfil de elevación. Con ese perfil calcula dos números por arista: la longitud en metros y el ascenso acumulado, que es la suma de todos los tramos donde la altura sube, ignorando los tramos donde baja.

flowchart TD
    A["Lidar USGS 1m (3DEP)"] --> B["Muestreo de elevacion por segmento"]
    C["Grafo de calles Overture / OSM"] --> B
    B --> D["Grafo ponderado: distancia + ascenso"]
    D --> E["Barrido de pesos lambda"]
    E --> F["Frontera de Pareto en el navegador"]

Ese ascenso acumulado es la pieza que hace posible el ruteo multiobjetivo, porque cada arista del grafo queda con dos costos independientes en lugar de uno solo, y el algoritmo de búsqueda tiene que decidir cómo repartirse entre ambos.

El grafo también es dirigido en el sentido del ascenso. Una cuadra que subís caminando hacia el norte es la misma cuadra que bajás si vas hacia el sur, así que cada arista guarda un costo de ascenso distinto según la dirección. Las escaleras se incluyen como arista válida para el modo a pie y se excluyen para el modo en bici, porque nadie sube una bici cargada por una escalera de Telegraph Hill.

Con el grafo ya pesado por distancia y ascenso, calcular una sola ruta pareto-óptima es relativamente simple. Se combinan ambos costos en un solo número usando un peso lambda (costo total = distancia + lambda × ascenso) y se corre un Dijkstra normal sobre ese costo combinado. El truco está en qué hace el slider de la página: en vez de fijar un lambda, lo barre desde 0, donde solo importa la distancia, hasta el límite de 200, el punto donde un pie de ascenso ya cuesta como 200 pies caminados, y en cada paso corre un nuevo Dijkstra. Cada paso entrega un punto distinto de la frontera, y como la ruta más corta pura y la más plana pura son los dos extremos del barrido, mover el slider hacia la derecha nunca acorta la ruta ni le suma ascenso: solo puede empatar o empeorar uno de los dos costos a cambio de mejorar el otro.

Para que esto corra rápido en el navegador con 160.000 segmentos, el grafo ponderado se precomputa una sola vez offline y se sirve como arreglos binarios compactos, por ejemplo coordenadas y costos en Float32Array y listas de adyacencia en arreglos de enteros, en vez de objetos JSON sueltos por nodo. Esa diferencia de formato es la que separa un Dijkstra que responde al instante de uno que tarda segundos por cada movimiento del slider.

Ejemplos prácticos y cómo empezar

Flatten SF en sí es un sitio cerrado para visitar, no una librería para instalar, pero la técnica de combinar lidar, grafo de calles y frontera de Pareto se puede probar con herramientas abiertas en cualquier ciudad con datos disponibles. Esta sección monta una versión mínima en Python y JavaScript, no una réplica completa, para ver cada pieza funcionando por separado.

Dependencias necesarias: Python 3.10 o superior con pip, y las librerías osmnx, networkx y rasterio.

python3 -m venv .venv
source .venv/bin/activate
pip install osmnx networkx rasterio

En Windows (PowerShell) el equivalente en una sola línea es: python -m venv .venv; .venv\Scripts\Activate.ps1; pip install osmnx networkx rasterio.

Con el entorno listo, descargar el grafo caminable de una ciudad toma dos líneas:

import osmnx as ox

grafo = ox.graph_from_place("San Francisco, California, USA", network_type="walk")
print(type(grafo))

Salida esperada:

<class 'networkx.classes.multidigraph.MultiDiGraph'>

OSMnx descarga el grafo desde OpenStreetMap vía Overpass y lo devuelve como un MultiDiGraph de NetworkX, listo para correr algoritmos de camino mínimo con las librerías estándar de grafos en Python.

El segundo paso es calcular el ascenso de una arista a partir de su perfil de elevación. Esta función resume la idea central del proyecto en seis líneas:

function ascensoAcumulado(elevaciones) {
  let ascenso = 0;
  for (let i = 1; i < elevaciones.length; i++) {
    const delta = elevaciones[i] - elevaciones[i - 1];
    if (delta > 0) ascenso += delta;
  }
  return ascenso;
}

console.log(ascensoAcumulado([10, 12, 11, 15, 14]));

Salida esperada: 6. El perfil sube 2 metros (de 10 a 12) y después 4 metros más (de 11 a 15), así que el ascenso acumulado es 6 aunque el punto final (14) quede por debajo del punto más alto del tramo (15). Si en cambio se calculara la diferencia neta entre el primer y el último valor, el resultado sería apenas 4, subestimando el esfuerzo real de subir y bajar en la misma cuadra.

El tercer paso combina distancia y ascenso en un solo costo y barre el peso lambda para construir la frontera:

function costoCombinado(arista, lambda) {
  return arista.distanciaMetros + lambda * arista.ascensoMetros;
}

function fronteraDePareto(grafo, origen, destino, pasos = 20) {
  const puntos = [];
  for (let i = 0; i <= pasos; i++) {
    const lambda = (i / pasos) * 200;
    const ruta = dijkstra(grafo, origen, destino, (arista) => costoCombinado(arista, lambda));
    puntos.push({ lambda, ruta });
  }
  return puntos;
}

dijkstra() es una implementación estándar de camino mínimo con función de costo personalizada, no incluida aquí por brevedad. fronteraDePareto barre lambda de 0 a 200 en 20 pasos y guarda la ruta óptima de cada paso, el mismo mecanismo que mueve el slider de Flatten SF.

Para confirmar que el muestreo de ascenso está bien calculado, sumá a mano las elevaciones de los puntos de una sola arista y compará el resultado contra el campo ascensoMetros que generaste. Si no coinciden, el muestreo del DEM probablemente está tomando muy pocos puntos a lo largo del tramo.

sequenceDiagram
    participant U as Usuario
    participant N as Navegador
    participant G as Grafo precomputado
    U->>N: mueve el slider a un nuevo lambda
    N->>G: corre Dijkstra con costo distancia + lambda*ascenso
    G-->>N: devuelve la ruta pareto-optima
    N-->>U: dibuja la ruta y las alternativas tenues
    Note over N,G: el grafo ya esta en memoria, no hay viaje al servidor

Casos de uso reales

Rutas peatonales en ciudades con relieve extremo. San Francisco, La Paz, Medellín o Hong Kong tienen barrios donde dos rutas de la misma distancia pueden diferir en decenas de metros de ascenso, y una app que solo mide distancia manda al usuario por la peor opción buena parte de las veces.

Ciclismo urbano y bicicletas de carga. Una pendiente de más del 10% puede ser el límite físico para una bici con carga, así que esta optimización de rutas por pendiente no solo ahorra esfuerzo sino que define qué rutas son viables y cuáles no.

Accesibilidad para sillas de ruedas. Fijar un tope duro de pendiente, por ejemplo nunca más de 5%, y resolver la ruta más corta dentro de ese límite es el mismo problema de fondo, pero con una restricción en lugar de una preferencia continua.

Planificación urbana y ciclovías. Un municipio puede usar la misma frontera para encontrar los corredores más planos entre dos puntos de la ciudad y priorizar ahí la infraestructura ciclista nueva.

Errores comunes y buenas prácticas

Usar la diferencia neta de elevación en vez del ascenso acumulado. Una calle que sube 20 metros y después baja 15 tiene una diferencia neta de apenas 5 metros, pero quien la camina sube los 20 metros completos; si el grafo solo guarda la diferencia neta, subestima el esfuerzo real.

⚠️ Ojo: el ascenso de una calle no es simétrico: la cuesta que subís caminando hacia el norte es la bajada que bajás hacia el sur, así que el grafo debe guardar el costo por dirección, no por segmento.

Usar SRTM de 30 metros cuando hace falta precisión de cuadra. SRTM resuelve el terreno en celdas de unos 30 metros, así que puede promediar una escalera empinada de una sola cuadra con el llano de alrededor; el lidar de 1 metro de USGS, donde está disponible, resuelve esa misma cuadra en cientos de celdas.

No precomputar el grafo ponderado. Calcular distancia y ascenso de cada arista en cada consulta es costoso con decenas de miles de segmentos; conviene calcularlo una sola vez offline y servir el grafo ya pesado, en un formato binario compacto, para que el navegador solo tenga que correr Dijkstra.

Permitir escaleras en modo bici. Si el grafo no distingue el tipo de vía (highway=steps en OpenStreetMap), un ciclista puede recibir una ruta que literalmente no se puede pedalear.

Comparativa con alternativas

Ninguna de las alternativas conocidas resuelve exactamente el mismo problema de la misma forma. La tabla compara el enfoque de Flatten SF con las opciones más comunes para quien necesita evitar cuestas.

Profundizando

El barrido de pesos lambda es simple y corre rápido en el navegador, pero tiene una limitación matemática. Si la frontera de Pareto tiene una zona no convexa, hay rutas óptimas que ningún peso lineal puede encontrar, porque el barrido solo visita los puntos que son óptimos para alguna combinación lineal de los dos costos. Para capturar la frontera completa, incluidas esas rutas, hace falta un algoritmo multiobjetivo propiamente dicho, como NAMOA* o una variante de Dijkstra con múltiples etiquetas por nodo, donde cada nodo guarda varias combinaciones de distancia y ascenso no dominadas en lugar de una sola distancia mínima.

💭 Clave: la frontera de Pareto no muestra una respuesta: muestra todas las respuestas válidas, y cuál de ellas elegís depende de cuánto esté dispuesto a caminar de más el usuario por cada metro de cuesta que se ahorra.

La contrapartida de NAMOA* es el costo computacional. Cada nodo puede terminar con varias etiquetas activas en vez de una sola, así que la búsqueda explora más estados que un Dijkstra de un solo objetivo. Para una ciudad del tamaño de San Francisco, con 160.000 tramos, correr esa búsqueda completa en cada clic del slider sería demasiado lento en el navegador, así que el barrido de pesos lineales es, en la práctica, el compromiso entre precisión matemática y velocidad de respuesta.

Otro detalle que cambia el resultado es cada cuántos metros se muestrea el perfil de elevación dentro de una sola arista. Muestrear solo los dos extremos de una cuadra larga y curva puede esconder una subida intermedia; muestrear cada 5 o 10 metros captura esa subida, al costo de generar y almacenar más puntos por segmento durante el preprocesamiento.

flowchart LR
    A["Ruta A: 2.1 km, 18 m de ascenso"] --> C{"Domina a la ruta B?"}
    B["Ruta B: 2.4 km, 30 m de ascenso"] --> C
    C -->|"si, A es mas corta y mas plana"| D["B se descarta"]
    C -->|"no, cada una gana en un criterio"| E["ambas quedan en la frontera"]

📖 Resumen en Telegram: Ver resumen

Tu próximo paso: cloná el grafo caminable de tu propia ciudad con osmnx.graph_from_place() y calculále el ascenso acumulado a cada arista usando un DEM gratuito de tu zona (SRTM si no hay lidar) antes de intentar la frontera de Pareto completa.

Preguntas frecuentes

¿Qué diferencia a Flatten SF de un buscador de ruta más corta tradicional?

Flatten SF no entrega una sola ruta: entrega un control deslizable que recorre toda la frontera de rutas pareto-óptimas entre distancia y ascenso, mientras que un buscador tradicional optimiza un solo número y descarta el resto.

¿Hace falta lidar de alta resolución o sirve con SRTM de 30 metros?

Depende de la escala de la pendiente que quieras capturar. SRTM alcanza para colinas grandes, pero una escalera o una rampa de una sola cuadra puede perderse en una celda de 30 metros; el lidar de 1 metro que usa Flatten SF resuelve esa misma cuadra con precisión de vereda.

¿Cómo calcula Flatten SF el ascenso de cada calle?

Muestrea varios puntos a lo largo de cada tramo en el modelo digital de elevación derivado del lidar y suma solo los tramos donde la altura sube, ignorando las bajadas; ese total es el ascenso acumulado de la arista.

¿Flatten SF sirve para planear rutas en bicicleta?

Sí, con una diferencia clave: el modo bici excluye las aristas marcadas como escalera, que sí están disponibles para el modo a pie, porque nadie sube una bici cargada por una escalinata.

¿Se puede aplicar esta frontera de rutas óptimas a otra ciudad fuera de San Francisco?

Sí, la receta es genérica: un grafo de calles de Overture u OpenStreetMap, un modelo digital de elevación de la zona (lidar si existe, SRTM si no) y un Dijkstra pesado por un lambda que combine distancia y ascenso.

¿Qué algoritmo usa Flatten SF para hallar rutas pareto-óptimas?

Según describe el propio sitio, corre un Dijkstra sobre un costo combinado de distancia y ascenso, barriendo el peso lambda entre 0 y el límite de 200 pies de caminata por cada pie de ascenso para trazar la frontera completa.

Referencias

• Flatten SF: el proyecto original de Drew Edwards, con enlace a los datos y el análisis completo.
• 3D Elevation Program (3DEP), USGS: fuente de los datos lidar de 1 metro usados para calcular el ascenso.
• Overture Maps Foundation: fundación que publica el grafo de calles derivado de OpenStreetMap.
• OpenStreetMap: fuente original y colaborativa del grafo de calles global.
• OSMnx: librería de Python usada en los ejemplos para descargar grafos de calles caminables.

📱 ¿Te gusta este contenido? Únete a nuestro canal de Telegram @programacion donde publicamos a diario lo más relevante de tecnología, IA y desarrollo. Resúmenes rápidos, contenido fresco todos los días.

Imagen destacada: Foto de Thuy Duong Nguyen en Unsplash