Maps and routing

Why did the nearest rider arrive last?

At 12:40 on a Thursday the dispatcher from lesson 6.2 offers a pickup to the rider closest to the kitchen. Closest as the crow flies: 600 metres away, across the Thursday market.

Nobody can ride through a market. The rider goes round by the arterial, waits at two signals, and reaches the kitchen nine minutes later. Another rider, a kilometre away on the far side, would have taken four. The dispatcher measured distance as if the city were an open field with nothing in the way.

The cause is in how matching estimates travel time: it takes the straight-line distance and allows three minutes a kilometre. The accurate version computes, for each order, the real route from each of the five nearest riders over the road network, one-way lanes and all. With a plain search, each route takes a moment on a laptop. Scale it before reading on: twenty orders a batch, five candidate riders each, a batch every twenty seconds. That is a hundred routes every twenty seconds, all through lunch, and the time adds up.

A maps API would answer the routes, at a price per request that grows with every order, and it knows nothing about the market. Running an engine of your own raises a different question: how can a route across a city of a million junctions take milliseconds?

Think about how you reach the station yourself. You do not consider every lane in the city. You think about getting out of your own lanes to the main road, and along the main road to the station. A road map is a graph, and the fastest route is a shortest path. The textbook algorithm searches the whole neighbourhood of the start, ring by ring. Real routing engines work more like your head does: they remember, in advance, how to cross each part of the city, and think lane by lane only near the two ends.

Lanes at the ends, exits in the middle

Dijkstra’s algorithm

Grow the set of junctions whose fastest time from the start is known, always adding the closest one next, until the destination is added.

For example: From the kitchen the search settles the junctions one minute away, then two minutes, and so on outward in every direction, including the directions that lead away from the customer.

A* and an admissible heuristic

Dijkstra with a sense of direction: order junctions by time so far plus an estimate of the time still to go. If the estimate never overestimates, the answer is still exact.

For example: Straight-line distance to the customer divided by the top speed of any road. No real route can be faster than that.

Buy the routes, or run the engine?

The dispatcher needs about five route queries per order, a batch every twenty seconds, all lunch. Where they come from is a real choice.

The case for the API is strong, and for customer-facing maps and turn-by-turn navigation the provider is the better choice. The dispatcher’s question is narrower: many short trips in one city, often, with local closures only the business knows. That favours running the engine, with the straight-line estimate kept as the fallback when it is down.

What to remember

1. A road network is a weighted directed graph; the fastest route is a shortest path, and one-way lanes and closures are edges and weights.
2. Dijkstra settles junctions outward in order of time; A* adds a lower bound on the time left and stays exact if the bound never overestimates.
3. Real engines precompute: contraction hierarchies, or tiles with shortcuts between their edge junctions, so a query searches lanes only near its two ends.
4. Tiles pay off at city scale, because a large tile has few edge junctions compared with the junctions inside it. Keep the partition fixed and recompute only the weights of tiles a closure touches.

Precompute how to cross the middle of the map; search lane by lane only at the two ends.

In the real world

The toy leaves out what makes real routing hard: turn costs and banned turns, time-dependent traffic, roads that change speed by the hour, map errors, and the size of the graph. Production engines also answer many-to-many questions (every rider to every pickup) in one call, which is exactly the dispatcher’s query, and is far cheaper than asking for each pair separately.

The idea that carries over is the one from lesson 6.1, one step further: split the map into cells, so that most questions are answered by a few cells and a little precomputed knowledge about the rest.