Network optimisation algorithm
- 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.
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.
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.
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.
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.
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.
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.
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.
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.
From the LinkSet_cleanedForJFS, we omit all the links that are dead ends, duplicates, or connected with itself.
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.
