How Modern Map Routing Engines Calculate Journeys in Milliseconds

Beyond Dijkstra: How OSRM and Valhalla Decouple Static Topology from Real-Time Traffic to Solve Global Pathfinding at Scale

Hey there! Have you ever paused to think about what actually happens when you open up a map application on your phone, type in a destination that is hundreds of miles away, and instantly get an optimal route? It is one of those everyday conveniences that we take completely for granted, yet the engineering underneath is truly spectacular. If you have ever experimented with basic pathfinding algorithms in computer science classes, you know how quickly graph traversal can get out of hand. If we were to run a standard Dijkstra or A-star algorithm on a global scale road network containing over a billion segments, the server would instantly run out of memory or leave you waiting for minutes.

To solve this massive computational challenge, routing engineers do not calculate paths by searching every single intersection in real time. Instead, the magic lies in extreme mathematical pre-computation and a clever separation of the physical road layout from dynamic traffic updates. Let us sit down and explore exactly how modern map routing engines pull off this incredible feat in mere milliseconds.

The Library Analogy

To understand how this works conceptually, imagine you are trying to find the absolute shortest walking route between a specific book on a shelf in a library in New York and another book on a shelf in a library in Los Angeles. If you tried to calculate the route by measuring every single corridor, hallway, street, and highway step-by-step across the entire North American continent, you would spend years calculating.

Instead, you rely on a pre-calculated index of shortcuts. This index has already computed the exact distances between the front doors of all major libraries in the world. To find your route, you only need to calculate the local path from your specific book shelf to the front door of the New York library. From there, you take the pre-calculated highway shortcut directly to the front door of the Los Angeles library, and finally, you navigate the local shelves to the destination book. This simple conceptual shift of separating local details from major transit networks is how modern routing engines bypass scanning millions of local roads.

Under the Hood: The Deep Dive

Core Routing Mechanisms and Contraction Hierarchies

To understand the core mechanisms, we have to look at how a road network is represented mathematically. The map is treated as a graph where intersections are vertices and road segments are edges. Because a standard search explores the graph radially in all directions, running it at a continental scale is highly inefficient. To bypass this, early modern routing engines introduced a preprocessing technique called Contraction Hierarchies.

During an offline preprocessing phase, every single vertex in the graph is sorted by a heuristic importance rank. The engine then contracts these nodes one by one, starting from the least important local streets up to the most important highway junctions. When a node is contracted, its adjacent neighbors are temporarily connected. If the shortest path between any two neighbors relies on the node being removed, the algorithm creates a shortcut edge directly between those neighbors, bypassing the contracted node.

When a user requests a route, a bidirectional search runs from both the origin and the destination simultaneously. The critical optimization here is that the search only relaxes edges that lead to nodes of a strictly higher rank. Because both search spaces quickly ascend to the highest-ranking highway networks, they meet at a maximum-rank node almost instantly, entirely bypassing the local streets in between. However, the limitation of Contraction Hierarchies is their sensitivity to live updates. If a traffic jam occurs, the pre-computed shortcut weights become invalid, and rebuilding the hierarchy for an entire continent can take hours.

Dynamic Routing with Customizable Route Planning

To resolve this dynamic traffic limitation, engineers developed Customizable Route Planning, which is implemented in systems like the Open Source Routing Machine as Multi-Level Dijkstra. This approach completely decouples the static physical topology of the road network from dynamic metrics like live speeds. The architecture is split into three distinct steps.

First, during the Metric-Independent Preprocessing phase, the road network is partitioned into multiple levels of loosely connected geographic cells. The boundary nodes of these cells are connected to create a high-level overlay graph, ignoring edge costs entirely. This phase is computationally heavy but only needs to run when the physical roads change.

Second, during the Metric Customization phase, the system instantly ingests real-time traffic updates and recomputes the edge weights only for the affected boundary cells. Because the cell partitions are static, the engine only updates pre-allocated metric tables for those specific cells, which takes just a few seconds.

Third, during the Query Phase, the system executes a bidirectional Dijkstra search that operates on the high-level overlay graph while resolving the local origin and destination details within their specific boundary cells.

This partitioning relies heavily on a clean separation of the graph using the Inertial Flow algorithm. To create balanced cells with as few crossing roads as possible, the algorithm applies a spatial sorting function to compare the latitude and longitude coordinates of the vertices. It selects a set of source and sink nodes on opposite sides of the geographic area and runs a maximum-flow algorithm, such as Dinic’s, to find the minimum cut. The graph is recursively bisected until the subgraphs reach the target cell size, forming the multi-level structures required for fast queries.

ETA Prediction via Spatiotemporal Graph Neural Networks

While finding the physical path geometry is a solved graph-routing problem, predicting the exact travel time requires understanding future traffic states. This is where deep learning steps in, utilizing Graph Neural Networks to model relational and spatial dependencies across the network. Predicting traffic on an individual segment level is computationally unscalable, so routing engines aggregate the road network into larger subgraphs called Supersegments that share traffic volume.

The system runs an Encode-Process-Decode architecture. The encoder takes node-level features like historical speeds and segment lengths and projects them into high-dimensional latent representations. The processor then runs a message-passing algorithm where nodes update their internal states by aggregating data from their topological neighbors. With each layer of message passing, the network understands traffic propagation further down the road. Finally, the decoder transforms these representations into travel time predictions for varying future horizons. To stabilize the training across thousands of highly variable road structures, engines utilize MetaGradients to dynamically optimize the learning rate hyperparameter during training.

Map Matching with Hidden Markov Models

To generate the real-time speeds that feed these models, systems must ingest millions of noisy GPS coordinates from active navigators and fleet vehicles. Because GPS signals bounce off buildings and drift, raw coordinates rarely align with the digital road network. Translating these coordinates into a contiguous route is accomplished using Hidden Markov Models.

In this architecture, the candidate road segments are treated as hidden states, while the noisy GPS coordinates are the observations. The model calculates the Emission Probability, which measures the geometric likelihood that a GPS coordinate belongs to a candidate segment based on perpendicular distance. It also calculates the Transition Probability, which measures the physical likelihood of a vehicle moving between candidate segments by comparing the shortest routing distance against the straight-line distance. The system then runs the Viterbi Algorithm over the sequence of points to decode the single most likely path of hidden states, successfully mapping the noisy telemetry to the road graph.

End-to-End Data Flow

The entire life cycle of map routing is a continuous, highly concurrent data loop. It begins when millions of client devices transmit timestamped GPS pings containing their coordinates and heading. These payloads hit an ingestion layer powered by a messaging broker like Google Cloud Pub/Sub or Apache Kafka, which immediately persists the messages to ensure high availability.

A stream processing engine, such as Apache Flink, consumes this raw telemetry in real-time and runs the Hidden Markov Model Map Matching algorithm using spatial R-trees to find candidate segments. Once the noisy GPS points are bound to precise segment identifiers, the system calculates real-time speeds and updates an in-memory Redis Cluster key-value store.

When a user requests a route, the API Gateway translates the request payload into Protocol Buffers and forwards it via gRPC to the core Routing Engine. The engine query dynamically pulls the latest traffic speeds from the Redis Cluster to evaluate the edge costs for the affected geographical cells. It then executes a bidirectional search across the pre-calculated tile hierarchy to generate the optimal path geometry.

This sequence of road segments is immediately passed to the Graph Neural Network, which fuses historical data with the live state to output predicted travel times. Finally, a narrative engine translates the physical path into human-readable driving directions, and the API Gateway serializes the geometry and ETA back to the user’s device.

The Tech Stack

Building a production-grade routing infrastructure requires high-performance engines paired with modern microservices. The industry standard routing engines each have distinct design philosophies.

The Open Source Routing Machine is written in modern C++ and relies heavily on loading the entire pre-processed graph into memory. This design delivers extremely fast query speeds and high throughput, making it ideal for massive distance matrices, though it requires servers with up to several hundred gigabytes of RAM.

Valhalla, also written in C++, takes a different approach by utilizing a tiled hierarchical data structure. This allows it to run in memory-constrained environments, even offline on mobile devices, by loading only the necessary geographic tiles on demand. It features a highly modular architecture including Baldr for managing tiled base data, Sif for dynamic runtime costing and traffic penalties, Thor for core path generation, Odin for directions, and Meili for map matching.

Another popular option is GraphHopper, which is written in Java and offers great flexibility for enterprise integrations, supporting both contraction hierarchies and custom weighting profiles.

Behind these routing engines sits a robust infrastructure plane. Engines communicate using gRPC and Protocol Buffers because standard JSON introduces unacceptable serialization overhead and bandwidth bloat when transmitting massive coordinate arrays. High-speed event streaming via Cloud Pub/Sub handles the ingestion of incoming telemetry, while an in-memory Redis Cluster acts as the hot cache for dynamic segment speeds. Traditional spatial databases like PostgreSQL with PostGIS are utilized to maintain point-of-interest records and base map metadata, relying on read replicas and connection poolers like PgBouncer to manage the query load.

The Senior Dev Perspective: Trade-offs & Challenges

When scaling a global geospatial system, you constantly run into tough engineering trade-offs. The first major challenge is balancing Memory Footprint versus Query Latency. OSRM optimizes for absolute speed by loading the entire global graph into RAM, which drives up horizontal scaling costs significantly. Valhalla mitigates this cost by using geographical tiles, but this introduces minor latency penalties whenever the engine has to perform disk or cache lookups for missing tiles.

The second challenge is navigating Consistency versus Availability during Dynamic Updates. Shifting to Multi-Level Dijkstra allows us to inject real-time traffic updates in seconds. However, if a traffic speed update occurs asynchronously while a long-distance route query is actively executing, the engine risks returning a disjointed or sub-optimal path because it is calculating the route across mismatched state data.

Finally, there is the dilemma of Pushing Live Reroutes via Long Polling versus WebSockets. Having client apps constantly poll the server for better routes creates millions of redundant pathfinding queries that can easily overwhelm your compute cluster. Moving to a stateful push architecture using WebSockets solves this by tracking which active segments drivers are currently traversing. If a major incident occurs, the system pushes a reroute payload only to the affected connections. This shifts the architectural bottleneck away from CPU-heavy pathfinding to memory-heavy state management, requiring your infrastructure to maintain millions of persistent TCP connections.

Fascinating Realizations

• Routing operates on trees, not graphs. Complex road networks are filled with infinite loops that make traversal difficult. Customizable Route Planning and Contraction Hierarchies solve this by using geometric cuts to partition the graph into disconnected sub-trees, transforming a tangled web of roads into a clean tree structure where pathfinding becomes a fast common-ancestor lookup.
• Privacy was the real bottleneck behind bad ETAs. In early systems, calculating travel times on rural roads was incredibly difficult due to privacy constraints. If only one driver is on a remote road, updating the public map with their speed explicitly leaks their location. Systems had to wait for multiple drivers to pass before updating, leading to outdated ETAs. DeepMind’s GNNs bypassed this by using graph topologies to infer speeds on quiet roads based on similar structural segments elsewhere.
• Traffic modeling mirrors thermodynamics. The deep learning models used to predict traffic jams were originally derived from physics research aimed at understanding the thermodynamics of glass molecules. Scientists realized that traffic delays propagate backward through a road network in a way that is mathematically identical to how physical stress and frustration propagate through molecular structures.

Have you ever worked with geospatial data, map engines, or real-time telemetry pipelines? How did you handle the trade-offs between memory footprints and query latency in your own projects? Let us chat about it in the comments below!