Network optimisation algorithm

Routing cost grows with the number of nodes in the network, but most nodes in a road network carry no routing information: they are shape points along a road, or they sit in dead ends that no route can pass through. Removing them, while preserving the aggregated length and impedance of what was removed, leaves routing results unchanged and makes Dijkstra substantially faster. On national road networks the node count typically falls by an order of magnitude.

The procedure in summary:

• make sure links are not doubled (i.e. with a return trip), and if necessary reverse the start and end nodes
• transform the link set from arcs to segments (i.e. links with only two nodes)
• remove dead ends in the network (a node with only one link)
• remove nodes from a junction-free section, and aggregate the relevant data fields (original link length and impedance)
• repeat removing dead-end and junction-free sections until no more nodes are removed

Nodes that carry an OD connector are excluded from deletion, because removing them would move the origin or destination.

Glossary

• OD-connection-road = the link from/to an origin/destination point. Result of a connect-operator.
• NodeSet = set of nodes in the network. This is unchanged from the beginning to the end of the script
• LinkSet = set of links between nodes in the network. This is repeatedly created in each iteration
• JunctionFreeSection = a set of links that together form a link without junctions.

Detailed description

In this image, nodes 1 and 2 and 4 to 8 are regular nodes in the network. Nodes 3 and 9 are OD-points. Links a and c to g are regular links, and b and h are OD-links.

Prep

We use iterations, where in Iter0, we start with the LinkSet_src from the CreateInitialLinkSet. In later iterations, we start with the IntermediateLinkSet from the previous iteration.

The unique locations are constant over the iterations. However, the LinkSet is not constant over iterations, so we need a new Link_rel in the location set. In the NodeSet, which is the same domain as the NodeSet_src and thus constant over the iterations, we define the nodes that can be deleted.

Identify WillBeDeleted nodes

The first step is to identify the nodes that can be deleted because they are not junctions (number of connecting links == 2) and are not part of an OD-connection-link (If a node is used in the link between an OD-point and the network, it is an OD-connection-road-node).

In this case, junctions 6 and 7 have only 2 connecting roads and are not OD-connecting-points. And are therefore earmarked as WillBeDeleted.

Identify JunctionFreeSections

Then, we use the NodeSet/WillBeDeleted to identify which links in the LinkSet are part of the JunctionFreeSection.

• IsPartOfJunctionFreeSection is defined as the F1 OR the F2 WillBeDeleted.
• IsInsideJunctionFreeSection is defined as the F1 AND the F2 WillBeDeleted.
• IsOnBorderOfJunctionFreeSection is defined as IsPartOfJunctionFreeSection AND NOT IsInsideJunctionFreeSection.
• IsFinalLink = UnchangedLink are those links that will not change.

In this case, links e, f, and g are IsPartOfJunctionFreeSection. Whereas, link f is the only one earmarked as IsInsideJunctionFreeSection. Furthermore, links e and g are IsOnBorderOfJunctionFreeSection.

LinksInsideJunctionFreeSection

This is a subset of all links that are inside the JFS, as defined in the NodeSet. In our case, only link f. We check these links using the connected_parts-operator, which links are together one JFS.

ConnectorLink

This set comprises all the links that are on the edges of the JFS. So, in this case, links e and g. Here we see which of the nodes is the one that WillBeDeleted, or the one which connects to the unchanged link.

JunctionFreeSection

From the connected_parts in LinksInsideJunctionFreeSection, we derive the distinct JunctionFreeSections. Here, we find the Connectorlinks on either side of the JFS and collect the relevant attributes from those links (e.g. impedance and length). Furthermore, here, we create a new F1 and F2 of the endpoints of the two connector links. In our example, from link e, node 4 is the endpoint, and from link g, node 8 is the endpoint.

We now aggregate the collected attribute values from the connector links with the links inside the JFS. Now, we have a new link, a straight line with all the attributes correctly aggregated. In our example, a link from node 4 to node 8.

LinkSet_cleanedForJFS

Now, we combine the unchanged links with the new straight-line JFS.

• At this point, we check for deadends. If the F1 and F2 of this domain only occur once in the NodeSet and it is not an OD-point. If so, we earmark the link as ToBeOmitted. In the example, that is nodes 1 and 4.
• We also check if a link is connected with itself if F1 == F2.
• And lastly, we check for duplicates. N.B. at the moment, regardless of its direction.

IntermediateLinkSet

From the LinkSet_cleanedForJFS, we omit all the links that are dead ends, duplicates, or connected with itself.

Repeat

Again, look for JunctionFreeSections and simplify them. Clean and look for deadends, duplicates and connections with itself.

Repeat until nothing needs to be cleaned anymore.

From the original 9 nodes, only 4 remain.