Network optimisation

After the road network is read and the origins, destinations and stops are connected to it, the model removes the nodes that serve no routing purpose. This makes the network much smaller, so the route searches run faster. Templates/CreateNetwork_Efficient_T does this for the networks built from road segments: walking, cycling (OSM or the Fietsersbond) and the OSM car network. The TomTom network is not contracted: its junctions already form a clean network, and its time-dependent link times need every link to be one road element in one direction (see Private transport).

Terms

Term Meaning
NodeSet All nodes of the network: the road nodes and the connected locations. It is the same in every pass.
LinkSet The links between the nodes. Each pass builds a new one.
one-way link (IsOneDirection) A link that can only be used from its first node F1 to its second node F2. A two-way link can be used in both directions.
junction-free section (JunctionFreeSection) A run of consecutive links whose inner nodes each have exactly two links, so none of them is a junction. The run can be replaced by one link.
connection link A link from an origin, destination or stop to the road network, made by connect_ne before the contraction.
connection node The node of a location, or the node where its connection link meets the road (IsOD_connection_road of the node). It is never removed, even when it has two links.

Before the contraction: the largest connected part

The model keeps only the road segments of the largest connected part of the road network, the part with the most nodes (Templates/Check_Connectiveness_T, IsInMainNetwork). Islands that cannot be reached from that part are dropped before the locations are connected, so no origin, destination or stop is connected to a road from which it cannot reach the rest of the network. The TomTom network applies the same check to its graph of junctions.

Overview

The contraction works in passes. Each pass finds the nodes that can go, replaces the links around them by one link, and removes dead ends, self-loops and duplicate links. The number of passes is fixed by ModelParameters/Advanced/NumberOfItersForNetworkCleanUp (10); a pass that finds nothing to remove leaves the network as it is.

The image below shows a network before the contraction. Nodes 1, 2 and 4 to 8 are road nodes, nodes 3 and 9 are locations. Links a and c to g are road links, b and h are connection links.

image

The steps of a pass

1. Mark the nodes to remove

A node is removed (WillBeDeleted) when all three hold:

  • it has exactly two links, so it is not a junction;
  • it is not a connection node;
  • both links are two-way, or both are one-way with one arriving at the node and the other leaving it (DirectionAllowsMerge).

The third condition makes the link that replaces a section usable in exactly the directions in which the section itself can be used. Other nodes with two links stay: where a one-way and a two-way link meet, one link for both would get one of the directions wrong, and where two one-way links both arrive or both leave, the node cannot be passed at all. A network with many one-way links therefore contracts somewhat less, in exchange for unchanged routes (#134).

In the example nodes 6 and 7 meet all three conditions. Junctions, with three or more links, and connection nodes stay.

With WillBeDeleted each link gets one of these flags:

  • IsPartOfJunctionFreeSection: at least one end node (F1 or F2) is removed;
  • IsInsideJunctionFreeSection: both end nodes are removed;
  • IsOnBorderOfJunctionFreeSection: one end node is removed and the other stays; these are the border links of a section (ConnectorLink);
  • IsFinalLink: no end node is removed, so the link stays as it is (UnchangedLinkSet).

In the example links e, f and g form a section: f lies inside it, e and g are its border links.

3. Group the removed nodes into sections

connected_parts over the links inside sections groups the removed nodes: removed nodes joined by inside links belong to the same section, and a removed node between two border links is a section on its own. A section without border links is a closed ring without a junction, and is dropped (IsNonCyclic_JFS).

The two border links of a section give the end nodes of the new link: their nodes that stay. The impedance and the distance of the new link are the sums over the border links and the inside links. The junction penalties are already part of the impedance of each link (see Walking and cycling legs), so the sum keeps them. Because of the third condition of step 1, the links of a section are either all two-way or all one-way in the same direction. In the second case the new link is one-way, and its F1 and F2 follow the direction of the first border link, so it runs the same way as the section.

In the example links e, f and g become one link from node 4 to node 8.

image

The new links and the unchanged links together are checked, and a link goes (ToBeOmitted) when it is one of these:

  • a dead end: a link to a node that has no other link and is not a location (IsDeadEnd_and_NotOD);
  • a self-loop: a link whose two end nodes are the same, which is what a ring through one junction becomes;
  • a duplicate: one of two or more links between the same two nodes that can be used in the same directions, that is two-way links between the same nodes in either order, or one-way links with the same F1 and F2. The first stays, with per impedance type the lowest impedance of the group and the distance of that link. A one-way link next to a two-way link, or two one-way links in opposite directions, are not duplicates, and both stay.

The remaining links form the IntermediateLinkSet, the input of the next pass.

image

6. Repeat

The next pass starts from the IntermediateLinkSet, because removing dead ends and duplicates can leave new nodes with two links. After the last pass the network of the example has 4 of its 9 nodes left.

image

FinalNodeSet and FinalLinkSet hold the result, and OrgNode_rel and DestNode_rel of FinalNodeSet give the node of each origin and destination.

  • Impedance per impedance type (Classifications/ImpedanceTypes: walking, cycling, e-bike and car, at free and congested speeds): the sum over the section in seconds, junction penalties included.
  • Distance per impedance type: the sum in km.
  • Geometry: a straight line between the two end nodes, for display only; the search uses the impedance.

Effect on routes

The contraction leaves every shortest route between locations and its impedance unchanged, on networks where every link is two-way, as the OSM networks for walking and cycling are, and on networks with one-way links, as the Fietsersbond network and the OSM car network are. A route through a removed node runs along its whole section anyway, and the new link can be used in the same directions as the section (step 1). A dead end that is not a location lies on no route between locations. Duplicate links can be used in the same directions, so a route takes the fastest of them, and that impedance stays. Only the last digits of an impedance can differ, because the impedances of a section are added in a different order.

On the Fietsersbond network this was checked with the cycling times from all origins to all stops within 15 minutes, for the 2025 origins and stops: they are equal to those over the network before the contraction (#134).