Origin Destination matrix (trip table)

An origin destination matrix (trip table) relates origins to destinations. The relation is the travel impedance, based on Dijkstra calculations, see Shortest path and the Dijkstra algorithm.

The OD matrix is the pivot of most accessibility work: routing produces it, and every location-based indicator in Accessibility indicators is an aggregation over it.

matrix versus table

matrix(left) versus table(right) with as impedance travel time in minutes

• In the matrix the number of rows and colums are the same.  

• In the table each row describes the impedance between one origin and one destination. This format can also be used if not all impedances are relevant, e.g. if the cut off is used to only calculate distances within 1 kilometer or 15 minutes.

With the GeoDMS matrices can be transformed to tables and vice versa, see the configuration example: Convert OD long to wide format. In this example long is a synonym for table and wide for matrix.

size

A full matrix grows with the product of origins and destinations, which is what makes the format choice practical rather than cosmetic. One million origins against one million destinations is $10^{12}$ cells, which is not storable. Three things keep matrices tractable, and all three produce a table rather than a matrix:

• a cut-off on impedance, discarding pairs beyond a threshold
• a destination set that is much smaller than the origin set (facilities versus dwellings)
• aggregating on the fly, computing the indicator per origin without ever storing the pairs

Choose the spatial units with this in mind; see Zoning and spatial units.

in the GeoDMS

The impedance functions produce either form. impedance_matrix returns the wide result, impedance_table the long one, and the impedance options cut, limit and euclid are what keep the long form from becoming the full product. The od section adds the route itself per pair, as a sequence of links.

Requesting od-pair output is the expensive choice: without it, memory stays proportional to the network rather than to the number of pairs. See impedance warning.

applications

We calculated a PC4 travel time matrix containing the travel time from each Dutch postcode zone (PC4) to every other zone, over 16 million pairs. It is available for download, see Applications.