Design maps navigation and ETA (Google Maps)

Dijkstra on a country graph with ~100M nodes explores millions of nodes for a long route, taking seconds of CPU per request: impossible at 10k requests/s. A* with a straight-line heuristic helps a little but not enough on road networks. The answer is preprocessing. Contraction Hierarchies (CH) rank nodes by importance and add 'shortcut' edges that skip unimportant nodes; queries then only go 'upward' in importance from both ends and meet in the middle, exploring a few hundred nodes and answering in about a millisecond. The weakness: CH preprocessing for one set of weights takes minutes or more, so live traffic is awkward. Customizable Route Planning (CRP), used in Bing Maps, splits preprocessing into two parts. A slow, metric-independent part partitions the graph into nested cells and finds boundary nodes. A fast customisation step recomputes the shortcut costs between boundary nodes for new weights in seconds, in parallel per cell. That makes it a good fit for traffic updated every minute and for different vehicle types (two-wheelers, cars, trucks with restrictions). Queries run bidirectionally over the overlay levels and take milliseconds. Shard routing servers by region with overlapping borders, or replicate the whole country graph per server, since it fits in memory.

Live traffic is crowdsourced from phones. Raw GPS points are noisy (5-30 m error, worse between tall buildings), so the first step is map-matching: given a sequence of points, find the most likely path on the road graph. An HMM does this well: candidate road segments near each point are hidden states, emission probability decreases with distance from the point, and transition probability prefers paths whose road distance is close to the straight-line distance between points. Viterbi finds the best path. From matched traces, compute travel time per segment, then aggregate per segment per minute. Clean the data: remove stationary points (a parked car or a delivery rider waiting), separate two-wheelers from cars because two-wheelers move through jams faster in Indian traffic, and use medians, not means. Low-traffic roads have few probes, so blend live estimates with historical speeds weighted by sample count. Privacy matters: rotate session ids, cut off the first and last few hundred metres of each trip, aggregate before storing, and delete raw probes quickly. This pipeline runs in Flink or a similar stream processor, partitioned by geographic region so each worker owns a set of segments.

Summing segment speeds gives a base ETA, but it is biased in known ways. Live speeds describe now, but you will reach a segment 40 minutes from now, so use a time-dependent model: live speed for the first part of the route, blending into the historical profile for the departure-time-plus-offset later. Add turn costs (right turns across traffic in India, U-turns), signal delays and speed limits. Then correct with machine learning: train a model on millions of completed trips (predicted vs actual), with features like route length, road classes, time of day, day of week, weather, events and region. Google Maps and DeepMind described using graph neural networks over 'supersegments' to improve ETA accuracy; gradient-boosted trees on route features are a strong simpler start. Measure accuracy with percentage error, and look at the tail (trips where the ETA was off by more than 20%), not only the average. Also show uncertainty: for long or uncertain routes, a range ('45-60 min') is more honest. Keep updating during navigation: the ETA is recomputed from the current position with fresh traffic, and large changes are explained ('heavy traffic ahead').

Map rendering must not hit the back end for every pan. The world is divided into tiles by zoom level (z) and coordinates (x, y), with 4^z tiles at zoom z. Vector tiles (Mapbox Vector Tile format) carry geometry and labels, and the phone renders them, so one tile serves any screen density, rotation and language, and is far smaller than images. Tiles for low zooms and busy areas are pre-generated; higher zooms are generated on demand from the map database and cached in S3 and the CDN with long TTLs and versioned URLs, so a map update just changes the version. Traffic colours are a separate, short-TTL overlay layer so base tiles stay cacheable. Navigation runs mostly on the device: the app has the route, the tiles along it and the steps, tracks position with GPS and sensors, announces turns, and detects 'off route' (position far from the route for several consecutive fixes). Only then, or for periodic traffic checks, does it call the server for a reroute. Offline maps download a region's tiles and a compact routing graph, which matters in India where highway connectivity drops.

CH gives the fastest queries and is simple to implement with open-source tools (OSRM uses it), but changing weights means slow re-preprocessing. CRP queries are slightly slower but traffic customisation takes seconds. With live traffic as a requirement, CRP (or a CH variant that supports customisation) is the better fit.

Server-driven navigation is easier to update but fails when the network drops and costs round trips. On-device navigation with server-provided routes and periodic traffic checks is resilient and fast. The cost is a bigger app and logic split between client and server.

Raster images are simple and render the same everywhere but are large and fixed in style and language. Vector tiles are small, styleable and rotatable, but need rendering work on the device. Modern apps use vector tiles, keeping raster only for satellite imagery.

Ride-hailing and delivery dispatch ask for many-to-many ETA matrices (for example 50 drivers × 20 orders) constantly. At 10x, these dominate CPU. Use one-to-many algorithms that reuse the search (like PHAST or bucket-based CH queries), cache cell-to-cell travel times for a minute, and give partners a separate, rate-limited cluster.

During evening rush, probes peak with traffic. Kafka absorbs bursts; map-matching scales by region partition. If workers fall behind, drop probes on roads that already have enough samples (sampling) rather than letting all traffic data lag.

Routing servers keep the last weights; after a few minutes they fall back to historical speeds for the current time of week. ETAs get less accurate but routes still work. Alerting tracks snapshot age.

A broken map update can make routes take huge detours. Validate every new graph with thousands of known benchmark routes before rollout, roll out by region gradually, and keep the previous version to roll back.

The app continues with the cached route and tiles and keeps giving turn instructions. Rerouting works on-device with an offline graph if downloaded; otherwise it retries when the network returns.