Flatten SF: Multi-Objective Routing Between Distance and Elevation Gain

⏱️ Reading time: 15 min

Flatten SF calculates, inside the browser and across 160,000 street segments in San Francisco, the walking or biking route that avoids the city’s steepest hills. It does this by combining 1-meter lidar elevation data from the USGS 3D Elevation Program with the street graph from Overture and OpenStreetMap, solving what graph theory calls multi-objective routing: finding, instead of a single optimal route, the complete set of routes that trade off between distance and elevation gain.

📑 En este artículo

1. TL;DR
2. What Is Multi-Objective Routing?
3. Why It Matters
4. How It Works Under the Hood
5. Practical Examples and How to Get Started
6. Real-World Use Cases
7. Common Mistakes and Best Practices
8. Comparison With Alternatives
9. Going Deeper
10. Frequently Asked Questions
    1. What makes Flatten SF different from a traditional shortest-route finder?
    2. Do you need high-resolution lidar, or does 30-meter SRTM work?
    3. How does Flatten SF calculate the elevation gain of each street?
    4. Can Flatten SF be used to plan bike routes?
    5. Can this frontier of optimal routes be applied to another city besides San Francisco?
    6. What algorithm does Flatten SF use to find Pareto-optimal routes?
11. References

TL;DR

• Flatten SF computes Pareto-optimal routes between distance and elevation gain across 160,000 street segments in San Francisco.
• USGS 1-meter lidar measures the real elevation gain of every block; the street graph comes from Overture and OpenStreetMap.
• One foot of elevation gain costs as much as 200 feet walked; beyond that limit, the route stops being worth it.
• Adding up cumulative elevation gain, not the net difference between start and end, avoids underestimating streets with ups and downs.
• Sweeping a lambda weight between distance and elevation gain in Dijkstra reconstructs the frontier of optimal routes.

What Is Multi-Objective Routing?

Multi-objective routing is a graph optimization technique that looks, instead of for a single shortest route, for all the routes that no other path beats simultaneously on two or more criteria, for example distance and cumulative elevation gain. That non-dominated set is called the Pareto frontier.

A simple example helps illustrate this. If there are two routes between the same origin and destination, one 2.1 km long with 18 meters of elevation gain and another 2.4 km long with 30 meters of elevation gain, the first dominates the second because it is both shorter and flatter at the same time. That’s why the second never shows up on the frontier. Now imagine a third route of 1.8 km with 45 meters of elevation gain. None of the three dominates the other two, because each one wins on a different criterion, so all three end up on the Pareto frontier.

Why It Matters

A shortest-path algorithm doesn’t distinguish between a flat block and a climb with a 15% grade, because both count the same if they measure the same distance. In a city like San Francisco, with slopes of more than 20 degrees in areas like Russian Hill or Potrero Hill, that difference decides whether someone walks for ten minutes or pushes a loaded bike uphill.

The same problem shows up in dozens of cities with pronounced relief, from La Paz and Medellín to Quito and Lisbon. An app that only optimizes for distance sends pedestrians down the shortest route even if that route climbs 80 meters over three blocks, when a nearly flat detour just a hundred meters away takes only two minutes longer.

For cyclists the problem is even bigger, because a grade of more than 12% can be impossible to climb with a loaded bike, and riding it down without control is dangerous.

Accessibility tools take the problem a step further. A person in a wheelchair doesn’t just prefer to avoid hills, they simply can’t climb one past a certain grade. There, multi-objective routing stops being a convenience: it becomes the difference between a route that’s possible and one that isn’t.

How It Works Under the Hood

The first input is the terrain. The USGS 3D Elevation Program (3DEP) covers much of the United States with lidar point clouds that resolve ground height at every meter. Flatten SF converts that point cloud into a digital elevation model (DEM), a grid where each cell stores a height in meters.

The second input is the street. The graph comes from Overture Maps, a foundation created in 2022 by Amazon, Meta, Microsoft, and TomTom under the Linux Foundation that cleans up and republishes OpenStreetMap data in a schema that’s easier to consume. That’s where the 160,000 street segments that form the nodes and edges of San Francisco’s graph come from.

The step that connects both worlds is sampling. A street segment isn’t a straight line between two intersections, so Flatten SF takes several points along each segment, not just its two endpoints, looks up the height of each point in the DEM, and builds an elevation profile. From that profile it calculates two numbers per edge: the length in meters and the cumulative elevation gain, which is the sum of all the stretches where height goes up, ignoring the stretches where it goes down.

flowchart TD
    A["USGS 1m Lidar (3DEP)"] --> B["Per-segment elevation sampling"]
    C["Overture / OSM street graph"] --> B
    B --> D["Weighted graph: distance + elevation gain"]
    D --> E["Lambda weight sweep"]
    E --> F["Pareto frontier in the browser"]

That cumulative elevation gain is the piece that makes multi-objective routing possible, because every edge in the graph ends up with two independent costs instead of just one, and the search algorithm has to decide how to trade off between them.

The graph is also directed with respect to elevation gain. A block you climb walking north is the same block you descend if you go south, so each edge stores a different elevation cost depending on direction. Stairs are included as a valid edge for walking mode and excluded for biking mode, because nobody carries a loaded bike up a staircase on Telegraph Hill.

With the graph already weighted by distance and elevation gain, calculating a single Pareto-optimal route is relatively simple. Both costs get combined into a single number using a lambda weight (total cost = distance + lambda × elevation gain), and a normal Dijkstra runs on that combined cost. The trick is in what the page’s slider does: instead of fixing a lambda, it sweeps it from 0, where only distance matters, up to the limit of 200, the point where one foot of elevation gain already costs as much as 200 feet walked, running a fresh Dijkstra at each step. Each step produces a different point on the frontier, and since the purely shortest route and the purely flattest route are the two extremes of the sweep, moving the slider to the right never shortens the route or adds elevation gain to it: it can only tie or worsen one of the two costs in exchange for improving the other.

For this to run fast in the browser with 160,000 segments, the weighted graph is precomputed once offline and served as compact binary arrays, for example coordinates and costs in Float32Array and adjacency lists in integer arrays, instead of loose JSON objects per node. That format difference is what separates a Dijkstra that responds instantly from one that takes seconds for every slider movement.

Practical Examples and How to Get Started

Flatten SF itself is a closed site for visiting, not a library to install, but the technique of combining lidar, a street graph, and a Pareto frontier can be tried out with open tools in any city with available data. This section builds a minimal version in Python and JavaScript, not a full replica, to see each piece working separately.

Required dependencies: Python 3.10 or higher with pip, and the osmnx, networkx, and rasterio libraries.

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

On Windows (PowerShell), the equivalent in a single line is: python -m venv .venv; .venv\Scripts\Activate.ps1; pip install osmnx networkx rasterio.

With the environment ready, downloading a city’s walkable graph takes two lines:

import osmnx as ox

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

Expected output:

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

OSMnx downloads the graph from OpenStreetMap via Overpass and returns it as a MultiDiGraph from NetworkX, ready to run shortest-path algorithms with Python’s standard graph libraries.

The second step is calculating the elevation gain of an edge from its elevation profile. This function summarizes the project’s core idea in six lines:

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]));

Expected output: 6. The profile climbs 2 meters (from 10 to 12) and then 4 more meters (from 11 to 15), so the cumulative elevation gain is 6 even though the final point (14) ends up below the highest point of the segment (15). If instead the net difference between the first and last value were calculated, the result would be just 4, underestimating the real effort of going up and down within the same block.

The third step combines distance and elevation gain into a single cost and sweeps the lambda weight to build the frontier:

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() is a standard shortest-path implementation with a custom cost function, not included here for brevity. fronteraDePareto sweeps lambda from 0 to 200 in 20 steps and stores the optimal route at each step, the same mechanism that drives Flatten SF’s slider.

To confirm the elevation sampling is calculated correctly, manually add up the elevations of the points along a single edge and compare the result against the ascensoMetros field you generated. If they don’t match, the DEM sampling is probably taking too few points along the segment.

sequenceDiagram
    participant U as User
    participant N as Browser
    participant G as Precomputed graph
    U->>N: moves the slider to a new lambda
    N->>G: runs Dijkstra with cost distance + lambda*elevation gain
    G-->>N: returns the Pareto-optimal route
    N-->>U: draws the route and the faint alternatives
    Note over N,G: the graph is already in memory, no server round trip

Real-World Use Cases

Pedestrian routing in cities with extreme relief. San Francisco, La Paz, Medellín, or Hong Kong have neighborhoods where two routes of the same distance can differ by dozens of meters of elevation gain, and an app that only measures distance sends users down the worse option a good part of the time.

Urban cycling and cargo bikes. A grade of more than 10% can be the physical limit for a loaded bike, so this slope-based route optimization doesn’t just save effort, it determines which routes are viable and which aren’t.

Wheelchair accessibility. Setting a hard slope cap, for example never more than 5%, and solving for the shortest route within that limit is fundamentally the same problem, but with a constraint instead of a continuous preference.

Urban planning and bike lanes. A municipality can use the same frontier to find the flattest corridors between two points in the city and prioritize new cycling infrastructure there.

Common Mistakes and Best Practices

Using net elevation difference instead of cumulative elevation gain. A street that climbs 20 meters and then drops 15 has a net difference of just 5 meters, but whoever walks it climbs the full 20 meters; if the graph only stores the net difference, it underestimates the real effort.

⚠️ Watch out: a street’s elevation gain isn’t symmetric: the climb you walk going north is the descent you walk going south, so the graph must store cost per direction, not per segment.

Using 30-meter SRTM data when block-level precision is needed. SRTM resolves terrain in cells of about 30 meters, so it can average out a steep one-block staircase with the flat ground around it; USGS 1-meter lidar, where available, resolves that same block across hundreds of cells.

Not precomputing the weighted graph. Calculating distance and elevation gain for every edge on each query is expensive with tens of thousands of segments; it’s better to calculate it once offline and serve the already-weighted graph in a compact binary format, so the browser only has to run Dijkstra.

Allowing stairs in biking mode. If the graph doesn’t distinguish the type of way (highway=steps in OpenStreetMap), a cyclist can get a route that literally can’t be pedaled.

Comparison With Alternatives

None of the known alternatives solve exactly the same problem in the same way. The table compares Flatten SF’s approach with the most common options for anyone who needs to avoid hills.

Going Deeper

Sweeping lambda weights is simple and runs fast in the browser, but it has a mathematical limitation. If the Pareto frontier has a non-convex region, there are optimal routes that no linear weight can find, because the sweep only visits points that are optimal for some linear combination of the two costs. To capture the full frontier, including those routes, a proper multi-objective algorithm is needed, such as NAMOA* or a variant of Dijkstra with multiple labels per node, where each node stores several non-dominated combinations of distance and elevation gain instead of a single minimum distance.

💭 Key point: the Pareto frontier doesn’t show one answer: it shows all the valid answers, and which one you pick depends on how much extra walking the user is willing to do for every meter of climb saved.

The trade-off with NAMOA* is computational cost. Each node can end up with several active labels instead of just one, so the search explores more states than a single-objective Dijkstra. For a city the size of San Francisco, with 160,000 segments, running that full search on every slider click would be too slow in the browser, so the linear weight sweep is, in practice, the compromise between mathematical precision and response speed.

Another detail that changes the result is how many meters apart the elevation profile is sampled within a single edge. Sampling only the two endpoints of a long, curving block can hide an intermediate climb; sampling every 5 or 10 meters captures that climb, at the cost of generating and storing more points per segment during preprocessing.

flowchart LR
    A["Route A: 2.1 km, 18 m elevation gain"] --> C{"Does it dominate Route B?"}
    B["Route B: 2.4 km, 30 m elevation gain"] --> C
    C -->|"yes, A is shorter and flatter"| D["B is discarded"]
    C -->|"no, each wins on one criterion"| E["both stay on the frontier"]

Your next step: clone the walkable graph of your own city with osmnx.graph_from_place() and calculate the cumulative elevation gain for each edge using a free DEM for your area (SRTM if there’s no lidar) before attempting the full Pareto frontier.

Frequently Asked Questions

What makes Flatten SF different from a traditional shortest-route finder?

Flatten SF doesn’t deliver a single route: it delivers a slider that travels across the entire frontier of Pareto-optimal routes between distance and elevation gain, while a traditional route finder optimizes a single number and discards the rest.

Do you need high-resolution lidar, or does 30-meter SRTM work?

It depends on the scale of the slope you want to capture. SRTM is enough for large hills, but a staircase or ramp on a single block can get lost inside a 30-meter cell; the 1-meter lidar that Flatten SF uses resolves that same block with sidewalk-level precision.

How does Flatten SF calculate the elevation gain of each street?

It samples several points along each segment in the digital elevation model derived from the lidar and adds up only the stretches where height goes up, ignoring the descents; that total is the edge’s cumulative elevation gain.

Can Flatten SF be used to plan bike routes?

Yes, with one key difference: biking mode excludes edges marked as stairs, which are available for walking mode, because nobody carries a loaded bike up a staircase.

Can this frontier of optimal routes be applied to another city besides San Francisco?

Yes, the recipe is generic: a street graph from Overture or OpenStreetMap, a digital elevation model for the area (lidar if it exists, SRTM if not), and a Dijkstra weighted by a lambda that combines distance and elevation gain.

What algorithm does Flatten SF use to find Pareto-optimal routes?

As the site itself describes, it runs a Dijkstra on a combined cost of distance and elevation gain, sweeping the lambda weight between 0 and the limit of 200 feet walked for every foot of elevation gain to trace the full frontier.

References

• Flatten SF: the original project by Drew Edwards, with a link to the data and the full analysis.
• 3D Elevation Program (3DEP), USGS: source of the 1-meter lidar data used to calculate elevation gain.
• Overture Maps Foundation: foundation that publishes the street graph derived from OpenStreetMap.
• OpenStreetMap: the original, collaborative source of the global street graph.
• OSMnx: Python library used in the examples to download walkable street graphs.

📱 Enjoy this content? Follow @programacion on Telegram for daily tech content in Spanish: quick summaries, fresh content every day.

Featured image: Foto de Thuy Duong Nguyen en Unsplash