Learning to Score Alternative Routes

A neural network trained on the CRP hierarchy predicts route quality faster than any classical heuristic can compute it

The Problem with Alternative Routes

Navigation systems almost always present users with more than one route. This is partly about accommodating preferences the system cannot infer, partly about hedging against uncertainty in travel time predictions, and partly about the psychological value of apparent choice. The algorithmic challenge is to generate alternatives that are distinct yet high quality. A route that detours wildly is technically diverse but useless; three routes that differ by a single block are technically high quality but uninformative.

The dominant approach in practice is the via-node method. First run a bidirectional search from origin and destination. Any node reached by both the forward and backward search trees lies on some path connecting the two endpoints and is a candidate "via-node." The shortest path from A to B through a via-node C is just the concatenation of the shortest path from A to C and from C to B. The question is which via-nodes to select.

The standard heuristic is the plateau method: score each via-node by the length of its "plateau," the portion of the via-path that belongs to both the forward and backward shortest-path trees. A long plateau indicates the via-node lies on a natural corridor; a short plateau suggests a detour is required to reach it. This works tolerably but produces "cuspy" routes: paths with localised, absurd detours. Zhai et al. (2024) illustrate this with a Seattle example in which a route leaves a highway, loops through a residential neighbourhood to pass through a via-node, then returns to the same highway. The overall length penalty is mild but no human would accept the route.

Uniform Stretch and Why It Is Expensive

The paper's quality criterion is "uniform stretch," following a definition from Abraham et al. (2013). The stretch of a path is its cost divided by the optimal cost. The uniform stretch is the maximum stretch of any subpath. A low-stretch route that contains a single terrible subpath has high uniform stretch. This is exactly what "cuspy" means: locally poor even if globally acceptable.

Computing uniform stretch exactly is expensive. A path with n edges has O(n squared) subpaths, each requiring a shortest-path computation. A faster method exists using modified edge weights, but even this requires multiple Dijkstra searches per candidate. When a single bidirectional search can produce hundreds of candidate via-nodes, evaluating uniform stretch for all of them at query time is prohibitive. The paper reports that exact computation of uniform stretch for 30 alternatives takes over 34 seconds on average across their test metros.

The T-test, proposed by Abraham et al. in the same 2013 paper, is a heuristic approximation. It examines a single subpath centred on the via-node: if this subpath is a shortest path, the via-node passes. The T-test is fast but coarse. It proves too aggressive in practice, rejecting many good via-nodes whose problems (if any) lie elsewhere on the path. The paper's precision-recall analysis shows this clearly: at recall levels around 0.7, the T-test's precision falls well below 0.5.

The paper's central idea is that a neural network can learn to predict uniform stretch without computing it. Train on examples where uniform stretch has been computed offline; at inference, the network provides instant predictions. The computational cost shifts from query time to training time.

Architecture: CRP and BERT

The model is built on top of CRP, and this is not incidental. The CRP hierarchy provides a multi-resolution decomposition of the road network that the model exploits directly.

Recall that CRP partitions the graph into regions at multiple levels. Level 1 might have four thousand regions; level 6 might have two or three. Each level has boundary nodes where edges cross between regions. The model learns vector embeddings for three types of entity: individual nodes, partitions at each hierarchical level, and boundary nodes at each level. With six levels and a 64-dimensional embedding space, this representation encodes the road network's structure at multiple spatial scales.

The query encoding module takes an origin-destination pair (s,t)(s, t) and assembles a sequence: the embeddings of ss and tt, plus the embeddings of their containing partitions at each of the six CRP levels. This gives a 14-element input sequence. The module that processes this sequence is BERT, the bidirectional transformer from Devlin et al. (2019). Where BERT ordinarily processes text tokens, this version processes graph entities. Self-attention allows the elements to interact, producing a query encoding that captures the spatial relationship between origin and destination at every resolution from neighbourhood to metropolitan area.

A classification head then takes the query encoding and a candidate via-node's embedding and outputs the probability that the via-node produces a via-path with uniform stretch at most 2.0. At inference, candidates scoring below a threshold are rejected; the survivors are ranked by path length.

This architecture is worth contrasting with other approaches to learning on graphs. Graph neural networks in the style of Veličković et al. (2019) or Ibarz et al. (2022) propagate information through the graph's adjacency structure via message-passing rounds. This is natural for tasks where the graph topology is the primary input but scales poorly to graphs with millions of nodes. The CRP-based embedding sidesteps this by leveraging the precomputed hierarchical partition. The model never sees the raw adjacency structure; it sees the hierarchy of regions and boundary nodes that CRP has already computed. This is a pragmatic design choice that sacrifices generality (the model is tied to CRP) for scalability (it works on networks with 1.5 to 2 million nodes).

Training and Results

The training set consists of 10 million randomly sampled origin-destination pairs. For each pair, a bidirectional CRP search identifies candidate via-nodes, and offline computation determines each candidate's true uniform stretch. The model trains for approximately 50 epochs until convergence. Training time is reported as "tens of hours," and the model occupies 1.2 GB for a 1.5-million-node network.

Evaluation uses three metropolitan road networks: Seattle, Paris, and Bangalore, each containing 1.5 to 2 million nodes. The test set is 100 random origin-destination pairs per city. The primary metric is non-cuspy diversity: the diversity of returned routes (total distinct edge length divided by optimal path length), excluding routes with uniform stretch above 2.0.

The model outperforms both the plateau heuristic and the T-test across all three metros and all numbers of alternatives tested (5 through 30). The improvement is substantial. At 30 alternatives, approximate non-cuspy diversity values are:

Method Seattle Paris Bangalore
Plateau ~3.3 ~4.5 ~4.8
T-test (T=0.01) ~3.2 ~4.2 ~4.5
Model prediction ~4.2 ~5.8 ~6.2
Uniform stretch filter (oracle) ~5.0 ~7.0 ~7.5

The "uniform stretch filter" is the oracle baseline: compute exact uniform stretch for every candidate, which takes over 34 seconds per query and is therefore impractical. The model approaches this ceiling while scoring candidates in under 10 milliseconds. Total latency for generating 30 alternatives is approximately 210 milliseconds, dominated by path expansion (converting CRP shortcuts back into explicit paths) rather than by the model itself.

The precision-recall analysis is perhaps more revealing than the aggregate metric. At recall 0.7, the model maintains precision above 0.8. The plateau heuristic at the same recall level has precision below 0.5. The T-test is worse still: for larger threshold values it becomes so aggressive that only a handful of candidates survive, making diverse alternative generation impossible.

What This Paper Is and Is Not

This paper demonstrates a pattern that is likely to recur across routing: using learned models to approximate quantities that are well-defined but expensive to compute at query time. Uniform stretch is not a vague concept; it has a precise mathematical definition. The difficulty is computational, not conceptual. A learned model, trained on offline ground truth, amortises the computation across millions of future queries.

The approach is conservative in the best sense. It does not replace CRP; it builds on CRP. It does not propose a new routing paradigm; it improves an existing step (via-node scoring) within an existing pipeline (via-node alternative generation). The classical infrastructure provides the graph decomposition, the candidate generation, the path expansion. The learned component provides fast approximation of a single, specific quality metric.

The paper's discussion section gestures toward broader applications: learning to predict path overlap for fast clustering, learning to incorporate traffic variability or user preferences. These are natural extensions of the same principle. If a quantity can be computed offline for training data, it can probably be approximated online by a learned model. Whether the approximation is accurate enough depends on the specific quantity and the specific architecture, but the template is clear.

The limitation is equally clear. This approach requires that the target quantity be computable offline in the first place. Uniform stretch, however expensive to compute, is well-defined given a road network and a path. User preferences, natural language constraints, multi-stop itineraries -- these do not reduce to a single computable quantity. For those, something more is needed.

References