impedance_matrix

Network functions > Impedance functions > impedance_matrix

syntax

impedance_matrix(
   options,
   link_imp,
   link_f1,
   link_f2,
   startPoint_node_rel,
   startPoint_org_rel,     // optional, depending on options
   endPoint_node_rel,
   endPoint_dst_rel,       // optional, depending on options
   ...                     // additional optional arguments
)

description

The impedance_matrix function calculates shortest path impedances between multiple origin zones and multiple destination zones using Dijkstra’s algorithm. It produces an origin-destination (OD) matrix as output.

Unlike impedance_table which treats all start points as a single origin, impedance_matrix supports multiple distinct origin zones, enabling full OD matrix calculations.

The function uses a highly optimized parallel implementation that processes each origin zone independently across multiple CPU cores.

arguments

required arguments

argument	domain	values	description
options	void	String	Configuration string specifying output options (see Impedance options)
link_imp	Link	Float32/Float64	Impedance (cost/distance/time) for each link
link_f1	Link	Node	“From” node for each link
link_f2	Link	Node	“To” node for each link
startPoint_node_rel	StartPoint	Node	Node where each start point connects to the network
endPoint_node_rel	EndPoint	Node	Node where each end point connects to the network

optional arguments (depending on options)

argument	domain	values	description
startPoint_org_rel	StartPoint	OrgZone	Origin zone for each start point (required for multiple origins)
endPoint_dst_rel	EndPoint	DstZone	Destination zone for each end point
startPoint_imp	StartPoint	Float32/Float64	Additional impedance at start points
endPoint_imp	EndPoint	Float32/Float64	Additional impedance at end points
max_imp	void	Float32/Float64	Maximum impedance cutoff
od_max_imp	OrgZone×DstZone	Float32/Float64	OD-specific maximum impedance
link_imp2	Link	Float32/Float64	Alternative link impedance, `alternative(link_imp)`: accumulated along each route, and with pareto the second search criterion
OrgZone_max_imp2	OrgZone or void	as link_imp2	Bound on the second criterion, `pareto(OrgZone_max_imp2)`
imp2_epsilon	OrgZone or void	float, dimensionless	Relative tolerance of the second criterion for epsilon-dominance, a fraction from 0 to 1, `pareto(imp2_epsilon)`, since 20.23.1
link_profile_rel	Link	Profile	Speed profile of each link, null for a fixed impedance, `timedependent(...)`, since 20.24.0
profile_slot_factor	Profile × TimeSlot	Float32/Float64, dimensionless	Speed relative to free flow per profile and time slot, `timedependent(...)`, since 20.24.0
slot_duration	void	as link_imp	Duration of a time slot, `timedependent(...)`, since 20.24.0
departure_time	OrgZone or void	as link_imp	Time of departure, `timedependent(...)`, since 20.24.0

conditions

All Link attributes must have the same domain (Link unit).
The values unit of link_f1 and link_f2 must be the same (Node unit).
startPoint_node_rel values must be valid node indices or null.
endPoint_node_rel values must be valid node indices or null.
link_imp values must be non-negative (negative impedances cause undefined behavior).
Null values in link_imp are treated as impassable links.

result

The function returns a unit<uint32> representing the set of OD pairs, with subitems depending on the options:

subitem	type	description
org_rel	OD→OrgZone	Origin zone for each OD pair
dst_rel	OD→DstZone	Destination zone for each OD pair
impedance	OD→Float64	Shortest path impedance for each OD pair
od_org_node	OD→Node	Entry node for each OD pair (if requested)
od_dst_node	OD→Node	Exit node for each OD pair (if requested)
alt_imp	OD→Float64	Alternative impedance sum (if requested)
link_attr	OD→Float64	Link attribute sum along path (if requested)

With the pareto option (GeoDMS 20.18 and later), routes are searched on (impedance, alternative impedance) with Pareto-dominance pruning and the OD-pair set holds one row per Pareto-optimal route, so several rows per (origin zone, destination zone) combination can occur; the subitems then describe each row’s route, and StartPoint_rel/EndPoint_rel tell which start and end point that route used. See Impedance options for the specification and its requirements.

Since GeoDMS 20.23.1 the pareto section takes an optional imp2_epsilon argument, pareto(imp2_epsilon) or pareto(OrgZone_max_imp2,imp2_epsilon): a relative tolerance for the second criterion, so that per node, and per (origin zone, destination zone), a slower route is only kept when its alternative impedance is more than that fraction below that of the cheapest route kept before it: with 0.01, more than 1% cheaper. That bounds the number of rows per pair when link costs are finely grained, at the price of an approximated front; the first row per pair remains the fastest route. Since 20.23.1 the tolerance is relative; before it was a bucket width in the unit of the second criterion, which is now refused (see Impedance options). The rows of several searches or modes are reduced to a front afterwards with pareto_optimal, or to a thinned front with pareto_optimal_eps.

Since GeoDMS 20.24.0 the timedependent(link_profile_rel,profile_slot_factor,slot_duration,departure_time) section makes the impedance of a link depend on the time at which a route enters it, the departure time plus the impedance so far: link_imp is then the impedance at free flow, and a link with a speed profile is ridden at the relative speed of the time slots it is ridden in, such as the 5-minute speed profiles of TomTom. The time on a link is an integral over its time slots, so a route that enters a link later never leaves it earlier, and the search, also with pareto, stays exact. timedependent_alt(…), with the same arguments, makes the second criterion of pareto time-dependent instead, for a search on distance first with time-dependent travel times. See the timedependent section of Impedance options.

Since GeoDMS 20.23.1 the products of the interaction section (D_i, M_ix, C_j, M_xj, Link_flow and the others) are also correct when a zone has several start points or end points, or when end points and destination zones are numbered differently. See the interaction section of Impedance options for the cases in which results of an older version have to be recalculated.

performance

aspect	indication
time complexity	O(O × (E + N log N)) where O = origins, E = edges, N = nodes
memory	O(N + E + O × D) where D = destinations per origin
parallelization	fully parallel - each origin processed on separate thread

performance tips

Use max_imp to limit search radius and reduce computation
Use sparse result mode for large networks with few connections per origin
Consider using impedance_matrix_od64 for more than 2³² OD pairs
For grid-based problems, consider Griddist instead

example

// Define network
unit<uint32> Node: nrofrows = 1000;
unit<uint32> Link: nrofrows = 3000
{
   attribute<Node>    f1;        // from node
   attribute<Node>    f2;        // to node  
   attribute<float32> impedance; // travel time in minutes
}

// Define zones
unit<uint32> OrgZone: nrofrows = 50;
unit<uint32> DstZone: nrofrows = 100;

// Define connection points
unit<uint32> StartPoint: nrofrows = 50
{
   attribute<Node>    node_rel;    // nearest network node
   attribute<OrgZone> org_rel;     // which origin zone
}

unit<uint32> EndPoint: nrofrows = 100
{
   attribute<Node>    node_rel;    // nearest network node
   attribute<DstZone> dst_rel;     // which destination zone
}

// Calculate OD matrix
unit<uint32> OD := impedance_matrix(
   'bidirectional;startPoint(org_rel);endPoint(dst_rel);cut(OrgZone_max_imp)',
   Link/impedance,
   Link/f1,
   Link/f2,
   StartPoint/node_rel,
   StartPoint/org_rel,
   EndPoint/node_rel,
   EndPoint/dst_rel,
   60f                    // max 60 minutes
)
{
   attribute<OrgZone> org_rel;
   attribute<DstZone> dst_rel;
   attribute<float64> impedance;  // travel time in minutes
}