Dijkstra functions
From ObjectVision
This page reflects the dijkstra functions of GeoDMS 7.212. See GeoDms Setups for installing GeoDMS 7.212 or later.
The dijkstra functions:
- determine the minimum impedance of the routes through a network of nodes and links with given link-impedance
- for each combination of given origins and destinations.
The user can filter the set of origin destination combinations (further: od-pairs) in two ways:
- by setting a maximum impedance (per origin) and/or
- a maximum amount of visited destination mass per origin.
Furthermore, the user can specify the production of additional results per origin, destination, link, or od-pair such as:
- the specification of an an alternative link impedance measure, to be aggregated over the found routes.
- interaction results: trip generation, distribution, and network flow assignment, following Alonso's Theory of Movements.
Origin and destination zones can be specified as a set of startPoints or endPoints that relate to the network nodes with an optional additional Impedance per startPoint and/or endPoint.
When no od-pair related output is requested, the memory usage remains proportional to the memory size of the given network and calculation time remains proportional to the number of actually visited nodes (plus some initialization time proportional to the size of the network).
Contents |
Entities
Key entities of the arguments and results of these functions are:
- Node
- a set of abstract locations, connected by links.
- Link
- a set of connections between nodes identified by two mappings, \(f_1: \text{Link}\rightarrow\text{Node}\), and \(f_2: \text{Link}\rightarrow\text{Node}\) indicating the start and end node for each link.
- OrgZone
- a set of origins
- DstZone
- a set of destinations
- startPoint
- a set of combinations of origins and nodes (thus allowing multiple nodes per origin and multiple origins per node).
- endPoint
- a set of combinations of destinations and nodes (thus allowing multiple nodes per destination and multiple destinations per node).
Depending on the given arguments, it may well be that these entities are not distinctive, for example: OrgZone may be equal to DstZone.
Relevant value-units are:
- Impedance
- a non-negative numerical expression of travel resistance for which comparison and addition make sense.
- Impedance2
- a non-negative numerical expression of an alternative travel resistance for which addition make sense. If no alternative impedance is given, Impedance2 is set equal to Impedance.
- Mass
- a non-negative numerical expression of OrgZone related demand or DstZone related supply
Functions
There are only three preferred dijkstra operations:
- dijkstra_s(...): when all given startPoints have to be considered as a single origin zone, resulting in:
- an attribute DstZone->Impedance with the lowest route Impedance per destination zone.
- optional attributes as sub-items depending on the used options.
- dijkstra_m(...) when startPoints can relate to multiple origin zones, resulting in
- a unit<uint32> reflecting the set of all or all found od-pairs
- optional attributes as sub-items depending on the used options.
- dijkstra_m64(...), similar to dijkstra_m(...), but resulting in a unit<uint64> in order to accommodate more than \(2^{32}-2\) od-pairs.
All these operations require at least the following four arguments:
- \( \text{options}: \{\emptyset\} \rightarrow \text{String} \), a String parameter indicating function options, described below.
- \( \text{impedance}: \text{Link} \rightarrow \text{Impedance} \), a Measure (Float32 or Float64) attribute of Links with the Impedance per Link.
- \( \text{f1}: \text{Link} \rightarrow \text{Node} \), a Node attribute of Link indicating the from node of each link.
- \( \text{f2}: \text{Link} \rightarrow \text{Node} \), a Node attribute of Link indicating the to node of each link.
Note that dijkstra can run different OrgZones in parallel, up to the number of cores of the running machine, as their tree growing is independent. This does not affect dijkstra_s, as that only grows one tree.
options specification
The options parameter indicates how to calculate routes, which additional arguments are given and which results are to be produced. Each section is separated by a ';', starts with a label and indicates comma separated extra arguments between '(' and ')'. Optional results are specified by name after a ':'. All sections, extra arguments and products must be specified in the order of the following description. All labels and names are case-sensitive and no intermediate spaces are allowed.
link direction
The first section is obligatory and indicates the allowed traversal direction of each link. It can be
- directed: only routes from a startPoint to an endPoint that traverses each link forward from node \(\text{f1}\) to node \(\text{f2}\) are considered and not vice versa.
- bidirectional: also backward traversal is considered through each link, from node \(\text{f2}\) to node \(\text{f1}\).
- bidirectional(link_flag): indicates an additional argument \(\text{Link}\rightarrow\text{Bool}\), a boolean attribute of \(\text{Link}\), that indicates for each link if it is to be considered as bidirectional. False indicates forward traversal only.
startPoints
The optional startPoint(Node_rel, impedance, OrgZone_rel):max_imp specifies a set of origin zones.
- the Node_rel, optional for dijkstra_m, indicates the presence of an additional argument: \(\text{startPoint}\rightarrow\text{Node}\), a Node attribute of startPoint in order to select a subset of nodes as startPoints. Required for the dijkstra_s function. Default: when omitted with the dijkstra_m function, all Nodes are considered as startPoints and startPoint := Node.
- the optional impedance indicates the presence of an additional argument: \(\text{startPoint}\rightarrow\text{Impedance}\), as departure impedance attribute of startPoint, useful mainly when origin zones contain multiple startPoints with specific departure impedances. Default value when omitted: zero.
- the OrgZone_rel, optional for dijkstra_m and not allowed for dijkstra_s, indicates the presence of an additional argument: \(\text{startPoint}\rightarrow\text{OrgZone}\), an origin zone attribute of startPoint, in order to define multiple startPoints per origin zone. Default for the dijkstra_m function when omitted: all startPoints are considered as separate origin zones. This option is not allowed with the dijkstra_s, where all startPoints are assumed to belong to the same origin zone.
- the optional max_imp, indicates the production of a sub-item \(\text{OrgZone}\rightarrow\text{Imp}\), an Imp attribute of OrgZone, named MaxImp that contains the maximum impedance for each OrgZone for all connected DstZones. This is especially useful in combination with the limit(OrgZone_max_mass,DstZone_mass) option with which one can produce the distance to the n-th unit of a DstZone specific quantity. When all Nodes are considered as separate OrgZones, one can specify startPoints:max_imp. This option is available in GeoDMS 7.168 and later versions.
- when no additional arguments are indicated, this section should be omitted; startPoint() is non-allowed syntax.
- when no startPoints are specified (not allowed with dijkstra_s), all Nodes are considered as separate origin zones.
endPoints
The optional endPoint(Node_rel, impedance, DstZone_rel) specifies a set of destination zones.
- the optional Node_rel indicates the presence of an additional argument \(\text{endPoint} \rightarrow \text{Node} \), a Node attribute of endPoint in order to select a subset of nodes as endPoints. Default: all Nodes are considered as separate endPoints
- the optional impedance indicates the presence of an additional argument \(\text{endPoint} \rightarrow \text{MeasureType} \), an arrival impedance attribute of endPoint, useful mainly for when Destination Zones contain multiple endPoints.
- the optional DstZone_rel indicates the presence of an additional argument \(\text{endPoint} \rightarrow \text{DstZone} \), a destination zone per endPoint, in order to define multiple endPoints per DstZone. Default: each endPoint is considered as a separate destination.
- when no additional arguments are indicated, this section should be omitted; endPoint() is non-allowed syntax.
- when no endPoints are specified, all Nodes are considered as separate destination zones.
filters
The optional cut(OrgZone_max_imp) specifies that a maximum route impedance will limit the route search, which requires as additional argument: \(\text{OrgZone}\rightarrow\text{Impedance}\), an impedance attribute of the origin zones or a single impedance limit parameter that is applied for all origin zones.
The optional limit(OrgZone_max_mass,DstZone_mass) specifies that a maximum amount of destinations per origin zone will limit the route development, which requires 2 additional arguments:
- \(\text{OrgZone}\rightarrow\text{Mass}\) or \(\{\emptyset\}\rightarrow\text{Mass}\) (must have the same ValuesType as Impedance), a Mass attribute of OrgZone or a single Mass parameter, that sets a maximum on the amount of Mass to be reached at the DstZones.
- \(\text{DstZone}\rightarrow\text{Mass}\) or \(\{\emptyset\}\rightarrow\text{Mass}\) (must have the same ValuesType as Impedance), a Mass attribute of DstZone or a single Mass parameter, that indicates a Mass for each DstZone, which is accumulated until the limit is reached for each OrgZone.
alternative impedance
The optional alternative(link_impedance):alt_imp specifies that an alternative link impedance is to be used to calculate an impedance per od-pair for further use in the interaction potential calculation.
- This requires an additional argument: \(\text{Links}\rightarrow\text{Impedance2}\), an alternative impedance per link, where Impedance2 must have the same values type as the original impedance, but may have a different metric.
- the optional product alt_imp indicates the production of an Impedance2 attribute of the resulting od-pair entity named alt_imp with the total alternative impedance of the found routes for each od-pair.
- when this section is omitted, the original Impedance is used in the interaction calculation and the unit Impedance2 is set to be equal to Impedance.
- when not filtering applies, some od-pairs may represent combinations without connecting route. The impedance is MAX_VALUE<ImpType> there but the alt_imp is <null> there. Both values will not be taken into account in an interaction distribution.
interaction
The optional interaction(OrgZone_min,DstZone_min,v_i,w_j,dist_decay,alpha,beta,gamma,OrgZone_alpha):D_i,M_ix,C_j,M_xj,Link_flow indicates the application of a free or origin constrained interaction model following the thoughts and notation of Alonso's General Theory of Movement (GTM) with a fixed supply elasticity per destination of 1 (thus \(\beta_j = 1.0\); no constraint on the destination side).
- the optional OrgZone_min indicates an additional argument: \(\text{OrgZone}\rightarrow\text{Impedance2}\) which can also be a single value (an attribute of void), indicating a minimum (alternative) impedance to be used for each destination to avoid infinite auto interaction potential for each origin. Default value is 0.
- the optional DstZone_min indicates an additional argument: \(\text{DstZone}\rightarrow\text{Impedance2}\) which can also be a single value, indicating a minimum (alternative) impedance to be used for each origin to avoid infinite auto interaction potential for each destination. Default value is 0.
- the obligatory v_i indicates an additional argument: \(\text{OrgZone}\rightarrow\text{Mass}\) which can also be a single value, indicating a trip generation weight per origin, aka \( v_i \).
- the obligatory w_j indicates an additional argument: \(\text{DstZone}\rightarrow\text{Mass}\) which can also be a single value, indicating a trip distribution weight per destination, aka \( w_j \).
- the optional dist_decay indicates an additional argument \( \gamma: \text{Float32}\) that indicates the rate of distance decay. The used interaction potential \(t_{ij}\) is calculated as \( t_{ij} := d_{ij}^{-\gamma} \).
- \( \gamma = 1.0 \) thus indicates \( t_{ij} = 1/d_{ij} \)
- If no route exists from \(i\) to \(j\) (which can be visible in the results when no filtering was applied), \(t_{ij}\) is set to \(0\).
- \( \gamma = 0.0 \) indicates \( t_{ij} = 1 \), even when \( d_{ij} \le 0 \), except when no route exists.
- \( \gamma = -1.0 \) indicates \( t_{ij} = d_{ij} \)
- when \( d_{ij} \le 0 \) and \( \gamma \ne 0.0 \), \( t_{ij} \) is set to zero, to avoid incorporating infinite potentials when no minimum impedances nor departure or arrival impedances were specified. Auto-interaction is then excluded, but included when \( \gamma = 0.0 \).
- the optional alpha,beta,gamma indicate three additional arguments that can be used to alternatively define \( t_{ij} \) as a log-logistic distance decay function of \( d_{ij}\): \( t_{ij} := \left({1+ exp\left( \alpha + \beta \cdot \ln(d_{ij}) + \gamma \cdot d_{ij} \right) }\right)^{-1} = \left({1+ exp\left( \alpha \right) \cdot d_{ij}^{\beta} \cdot exp\left( d_{ij} \right)^{\gamma } }\right)^{-1} \).
- note that either dist_decay or alpha,beta,gamma must be specified in an interaction section.
- the optional 'OrgZone_alpha indicates an additional argument: \(\text{OrgZone}->\text{Float32}\) which can also be a single value, indicating the elasticity of origin's supply for the amount of demand alternatives. \( \alpha = 1.0 \) indicates an elastic model; \( \alpha = 0.0 \) indicates a push model with fixed supply \( v_i \) per origin.
Calculated products (at least one should be specified):
- the optional D_i, indicates the production of a sub-item \(\text{OrgZone}\rightarrow\text{Mass}\), a Mass attribute of OrgZone, named D_i, aka \(D_i\), defined as \( D_i:= \sum\limits_{j} w_j \cdot t_{ij}\).
- the optional M_ix, indicates the production of a sub-item \(\text{OrgZone}\rightarrow\text{Mass}\), a Mass attribute of OrgZone, named M_ix, aka \(M_{ix}\), defined as \( M_{ix} := v_i \cdot\ D_i^\alpha = \sum\limits_{j} v_i \cdot w_j \cdot t_{ij} \cdot D_i^{(\alpha-1)}\). Note that when \(D_i = 0\), \( D_i^\alpha \) is assumed to be zero, even if \(\alpha = 0\), in order to respect the fact that if there is no demand potential at all, it cannot be raised to a set demand whatever the elasticity.
- the optional C_j, indicates the production of a sub-item \(\text{DstZone}\rightarrow\text{Mass}\), a Mass attribute of DstZone, named C_j, aka \(C_j\), defined as \( C_j:= \sum\limits_{i} v_i \cdot t_{ij} \cdot D_i^{(\alpha-1)}\).
- the optional M_xj, indicates the production of a sub-item \(\text{DstZone}\rightarrow\text{Mass}\), a Mass attribute of DstZone, named M_xj, aka \(m_{xj}\), defined as \( M_{xj}:= w_j \cdot C_j = \sum\limits_{i} v_i \cdot w_j \cdot t_{ij} \cdot D_i^{(\alpha-1)}\).
- the optional Link_flow, indicates the production of a traffic flow network assignment, a sub-item \(\text{Link}\rightarrow\text{Mass}\), a Mass attribute of Link, named Link_flow, aka \(LF_l\), defined as \( LF_l := \sum\limits_{l \in i \rightarrow j} v_i \cdot w_j \cdot t_{ij} \cdot D_i^{(\alpha-1)}\).
Traceback production
the optional node:TraceBack (only available for dijkstra_s) produces a sub-item \(\text{TraceBack}: \text{Node} \rightarrow \text{Node} \), a Node attribute of Node, indicating for each node which previous node of the grown tree(s) traces back to the origin of startPoint Node(s).
For the dijkstra_m function, producing this info is complicated by the fact that a trace back would be available for each origin.
od-pair specification and attribute production
the optional od:impedance,OrgZone_rel,DstZone_rel,LinkSet, indicates the production of a specific kind of od-paid entity and related attributes.
- the optional impedance indicates the production of a sub-item \(\text{impedance}: \text{OD} \rightarrow \text{Impedance} \), an attribute with the lowest route impedance per found od-pair. This impedance includes startPoint(impedance) and endPoint(impedance) but not OrgZone_min nor DstZone_min.
- the optional OrgZone_rel indicates the production of a sub-item \(\text{OrgZone_rel}: \text{OD} \rightarrow \text{OrgZone} \), an attribute with the OrgZone of each od-pair.
- the optional DstZone_rel indicates the production of a sub-item \(\text{DstZone_rel}: \text{OD} \rightarrow \text{DstZone} \), an attribute with the DstZone of each od-pair.
- the optional LinkSet indicates the production of a sub-item \(\text{LinkSet}: \text{OD} \rightarrow \text{Link-sequence} \), an attribute with the sequence of Links of each od-pair route.
When no od-pair related products are requested (including no alt_imp), the memory footprint of the operation will be greatly reduced as intermediate potentials and route flows per od-pair are produced per OrgZone and directly aggregated to the OrgZone, DstZone, and/or Link level and no storage is required per od-pair simultaneously for different OrgZones.
production of \(t_{ij}\) and \(M_{ij}\)
In order to get \(t_{ij}\) and \(M_{ij}\), the calculated interaction potential and trip flow per od-pair, one can recalculate them from the results available from od:impedance,OrgZone_rel,DstZone_rel
- When no alternative link impedance is given, define as extra sub-item of the resulting od-pair unit:
attribute<Float32> t_ij := impedance >= 1e+38f ? 0.0f : distDecay == 0.0f ? 1.0f : impedance^-distDecay;
Note that \(t_{ij} >= \text{max_dist}\) only for od-pairs without available route, which only appears in results when no filtering option was used. If filtering was used and it is known that distDecay is non-zero, the above can be simplified to
attribute<Float32> t_ij := impedance^-distDecay;
- When alternative(link_imp):alt_imp is used, use:
attribute<Float32> t_ij := !IsDefined(alt_imp) ? 0.0f : distDecay == 0.0f ? 1.0f : alt_imp^-distDecay;
- When OrgZone_min or DstZone_min were specified , replace the last impedance measure (impedance or alt_imp) by
- max_elem(impedance, min_imp[OrgZone_rel]) when min_imp is given per origin zone,
- max_elem(impedance, min_imp[DstZone_rel]) when min_imp is given per destination zone, or just
- max_elem(impedance, min_imp) when it is a single value parameter, applied for all od-pairs.
- The \(M_{ij} \) can then be calculated with
attribute<Float32> M_ij := D_i[OrgZone_rel] <= 0.0f ? 0.0f : t_ij*D_i[OrgZone_rel]^(demand_alpha-1.0f);
- if the demand for each zone i is assumed to be inelastic , i.e. demand_alpha == 0f, this can be simplified to
attribute<Float32> M_ij := D_i[OrgZone_rel] <= 0.0f ? 0.0f : t_ij*(1.0f / D_i)[OrgZone_rel];
An example of this can be found in the operator test configuration at /Network/UnTiled/dijkstra_all_interaction.
Addtional notes
- Filtering with cut or limit is an essential tool for limiting the computation effort when modelling network flow due to local traffic with many origins and destinations. The implementation only processes localized data per OrgZone when such filtering is applied, making the computation time per OrgZone independent of the network size after initial initialization. For example, the processing of 4000 PC4 zones (both Origin and Destination) on the OpenStreetMap network of the Netherlands with boundary extensions took 10 minutes when pcut was set to 1800[sec], resulting in an OD set of 750.000 pairs, thus approximately an average of 175 destinations per origin (of the 4000 potential destinations), whereas processing all od-pairs took several hours. The generation of Link_flow (Network Assignment) from the 4000 PC4 origins to all 5.000.000 nodes as destinations with a cut of 5 minutes took approximately 1 minute to produce. See item /Analyses/PC4_2_PC4/MakeOD/OD_impcut5min_all_na/UsedLinks/LinkFlow in the oda configuration and its [MapView];
- one can model constrained supply by iteratively adjusting \( w_j \) with \( C_j^{\beta_j-1} \) with \(\beta_j\) as supply elasticiy parameter.
- one can model a congested network equilibriumby iterative application of the network assignment by implementing a feedback loop (http://en.wikipedia.org/wiki/Transportation_forecasting) on the link impedances.
- by assigning a heterogeneous set of transport users (mode, income, trip purpose, etc.) in slices of, say 10% per slice, one can also obtain a balanced load of the network and the choice of startPoints per
- by using short cuts for interactions between many small zones and larger cuts for interaction between a smaller number of larger zones, one can obtain a balanced load of the network within a reasonable amount of computation time.
- one can generate route counts per link with interaction(v_i,w_j,dist_decay,OrgZone_alpha):D_i,C_j,Link_flow by setting \( v_i = w_j = \alpha_i = 1.0 \) and \( \gamma = 0.0 \). The resulting \(D_i\) and \(C_j\) are total route counts per origin an destination.
- one can generate link counts per od-pair with alternative(link_impedance):alt_imp by providing 1.0 as alternative link impedance.
Impossible, unlikely or possible speedup optimizations
- Pre processing, overview: http://algo2.iti.kit.edu/schultes/hwy/dynamic.pdf
- using highway hierarchies along the lines of http://algo2.iti.kit.edu/schultes/hwy/distTable.pdf, and http://algo2.iti.kit.edu/schultes/hwy/esaHwyHierarchiesSlides.pdf
- edge reduction
- transit node routing and separators
- A* methods, geometric containment and goal direction search, useful only for individual OD-pairs.
Links
- For a discussion of Alonso's General Theory of Movements (GTM), see:
- Alonso's General Theory of Movement: Advances in Spatial Interaction Modeling, de Vries, Nijkamp and Rietveld The changed notation can be reverted by applying the following rewrite rules: \( T_{ij} \rightarrow M_{ij}; F_{ij} \rightarrow t_{ij}; O_i \rightarrow M_{ix}; D_j \rightarrow M_{xj}; A_i \rightarrow D_i^{-1};B_j \rightarrow C_j^{-1}; V_i \rightarrow v_i; W_j \rightarrow w_j; c_{ij} \rightarrow d_{ij}; \gamma_1 \rightarrow \gamma \)
- Example code can be found in the oda configuration, more specifically in configuration file cfg/stam/analyses/PC4_2_PC4.dms. See in oda for example
- item /Analyses/PC4_2_PC4/MakeOD/OD_impcut_td/DstMass in MapView.
- item /Analyses/PC4_2_PC4/MakeOD/OD_impcut_na/LinkFlow in MapView.
- [Screenshot of /Analyses/PC4_2_PC4/MakeOD/OD_impcut_na/LinkFlow in MapView]
- [Screenshot of /Analyses/PC4_2_PC4/MakeOD/OD_impcut5min_all_na/UsedLinks/LinkFlow in MapView]
- more basic (and contrived) examples can be found in the GeoDms regression tests, more specifically: in the Network section thereof.