13.4 Origin-Destination Matrices

Key takeaways

• An OD matrix is an N × M table of travel times or distances between origins and destinations.
• Efficient engines compute large OD matrices by re-using Dijkstra / CH graph state.
• Feeds logistics optimisation, gravity models, and accessibility analysis.

Introduction

A single route answers "how long from A to B?" An origin-destination (OD) matrix answers "how long from each of these N origins to each of these M destinations?" — a central input for logistics, trade, and accessibility analysis. This lesson covers its generation and common uses.

Structure

Rows = origins; columns = destinations; cells = travel cost (time or distance).

For N=M=1000 that's 10⁶ cells; for N=10 000 M=10 000, 10⁸ cells. Size matters.

Efficient computation

Naive: run Dijkstra N times (one per origin), recording cost to every destination. O(N × (E+V) log V) — slow for large N.

Smart:

• One-to-many: each Dijkstra call returns costs to all nodes; filter to destinations. O(N) Dijkstra calls = good.
• Many-to-many with CH: contract graph once, then each query is milliseconds. Scale to millions of OD pairs per minute.
• Batch APIs — OSRM's /table, Mapbox's Matrix API, Valhalla's sources_to_targets.

Python:

1import requests
2resp = requests.get(
3  f'http://osrm.example.com/table/v1/driving/{";".join(coords)}',
4  params={'annotations': 'duration,distance'}
5)
6matrix = resp.json()  # durations[i][j] in seconds

Use cases

Logistics optimisation

Vehicle routing problems (VRP) take OD matrices as inputs: given capacities, time windows, and penalties, find routes that cover all orders. Solvers (OR-Tools, Jsprit, VROOM) consume the matrix.

Gravity models

In transport and retail:

$$T_{ij} = \frac{A_i \cdot B_j}{d_{ij}^\beta}$$

Trips between zones fall off with distance β; the OD matrix supplies distances.

Accessibility metrics

Define accessibility of zone i as:

$$A_i = \sum_j \text{opportunities}j \cdot f(d{ij})$$

where f is a decay function. A full OD matrix lets you compute accessibility for every origin zone.

Trade / migration flows

Gravity models of trade and migration use OD matrices of distances or travel times.

Computing populations-per-zone

A common preprocessing step: aggregate population / opportunities by zone, then compute zone-to-zone matrices. Zones can be:

• Administrative districts.
• TAZs (Traffic Analysis Zones).
• Hex grids (H3 level 7–8).
• Census blocks.

Fewer, larger zones → smaller matrix, faster computation. More, smaller zones → more detail.

Asymmetry

For directed networks with one-way streets, d[i][j] ≠ d[j][i]. Always compute both directions if you need to route in either.

Memory

A 10 000 × 10 000 matrix of Float32 is 400 MB. A 100 000 × 100 000 is 40 GB. At scale, keep only the cells you need (top-k destinations per origin) or use sparse formats.

Time-dependent OD

When traffic varies, compute the matrix at representative times (AM peak, off-peak, PM peak) or hourly. Storage multiplies; use selectively.

Exporting and visualising

• CSV / Parquet for numerical analysis.
• Sankey diagrams for flow visualisation (desire lines).
• Choropleth of "total accessible jobs from zone X".
• Animated maps for time-dependent matrices.

Self-check exercises

Summary

• OD matrix = N × M travel costs between origins and destinations.
• Batch engines (OSRM, Valhalla) scale via CH preprocessing.
• Feeds logistics, gravity models, accessibility, trade flows.
• Memory scales as N × M — design zones to match use.

Further reading

• OSRM /table API documentation.
• VROOM / OR-Tools for VRP solvers.
• Wilson, A. G. — A family of spatial interaction models.
• Conveyal R5 documentation — transit + road OD at scale.