Network optimisation
After loading and filtering the road network, intermediate nodes that serve no routing purpose are removed through an iterative contraction algorithm. This reduces the number of links and nodes in the network—sometimes dramatically—while leaving shortest-path results completely unchanged. The algorithm is implemented in CreateNetwork_Efficient_T and applied to the OSM car, cycling, and pedestrian networks. The TomTom network is not contracted (its junction structure is already clean).
| Term | Meaning |
|---|---|
| NodeSet | The set of all nodes in the network. Constant throughout all iterations. |
| LinkSet | The set of links between nodes. Rebuilt in each iteration as nodes are contracted. |
| JunctionFreeSection (JFS) | A sequence of consecutive links where all intermediate nodes have exactly two connecting links (i.e., they are not junctions). The whole sequence can be replaced by a single straight link. |
| OD-connection link | A link connecting an origin or destination point to the nearest network node. These are added before contraction and treated as protected links. |
| OD-connection-road-node | A node that is part of an OD-connection link. These nodes cannot be contracted even if they have only two connecting links. |
The algorithm works through repeated passes. Each pass identifies nodes that can safely be removed (non-junctions not used by OD links), replaces the sequences of links around them with single aggregated links, and removes dead ends and duplicates. Passes continue until no further simplification is possible.
The image below shows the structure before simplification. Nodes 1, 2, and 4–8 are regular network nodes; nodes 3 and 9 are OD points. Links a and c–g are regular links; b and h are OD-connection links.
A node is a candidate for deletion if both of the following hold:
- It has exactly two connecting links (i.e., it is not a junction).
- It is not part of an OD-connection link.
In the example, nodes 6 and 7 meet both conditions and are marked WillBeDeleted. Nodes at junctions (3 or more links) and nodes touching OD-connection links are left untouched.
Using the WillBeDeleted flag, each link is classified:
-
IsPartOfJunctionFreeSection: at least one endpoint (
F1orF2) will be deleted. - IsInsideJunctionFreeSection: both endpoints will be deleted.
- IsOnBorderOfJunctionFreeSection: part of a JFS, but not fully inside (i.e., one endpoint is a real junction or OD node).
- IsFinalLink (= UnchangedLink): neither endpoint will be deleted; these links remain as-is.
In the example, links e, f, and g are part of the JFS. Link f is fully inside; links e and g are on the border.
Within the set of links that are inside a JFS, connected_parts is used to group links that belong to the same contiguous section. Each group forms one JFS that will be replaced by a single link.
For each JFS, the two border links (one on each end) are identified. Their outer endpoints—the ones attached to real junctions—become the endpoints of the replacement link. Impedances and distances from all links in the JFS (border links plus interior links) are summed to produce the aggregated impedance and length of the new single link.
In the example, the JFS consisting of links e, f, and g is replaced by a single link from node 4 to node 8.
After merging the JFS, the resulting link set is checked for:
-
Dead ends: a node that appears only once as
F1orF2across all links and is not an OD point. Links leading to such nodes are flaggedToBeOmitted. -
Self-loops: links where
F1 == F2after contraction are removed. - Duplicates: when two links connect the same pair of nodes after collapsing, duplicates are removed (currently regardless of direction).
The remaining links form the IntermediateLinkSet for the next iteration.
The process repeats—finding new JunctionFreeSections in the updated link set, aggregating them, cleaning up—until no further deletions are possible. The number of iterations is configurable via ModelParameters/Advanced/NumberOfItersForNetworkCleanUp (default: 10).
The final network after all passes is shown below. Of the original 9 nodes, only 4 remain.
When a JFS is collapsed, all link attributes are aggregated across the constituent links:
- Impedance: summed (total travel time over the section)
- Distance: summed (total length in km)
- Geometry: replaced by a straight line between the two outer endpoints (used for display only; routing uses the aggregated impedance, not geometry)
For the TomTom network, multiple impedance types (MorningRush, NoonRush, LateEveningRush, Freeflow) are all aggregated simultaneously, so the contracted network retains all time-period variants.
Before contraction begins, the network is filtered to retain only the largest connected component. Disconnected subnetworks—islands in the road graph that cannot be reached from the main network—are identified using connected_parts and removed. This ensures that routing always operates on a fully connected graph, and that OD points are not silently assigned to an isolated subnetwork.
For TomTom, this check is performed on the Junctions-based graph using Check_Connectiveness_T before the OD links are added.