Network optimisation algorithm

Overview

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

Glossary

• OD-connection-road = the link from/to an origin/destination point. Result of a connect-operator.
• NodeSet = set of a 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 are together a link without junctions.

Assumptions

1. A node can be deleted if the number of connecting links == 2, while it is not an OD-connection-link

Details

In this image, nodes 1 to 6 are regular nodes in the network. Node 7 is an OD-point. Links a to e are regular links, and f is an OD-link.

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 and not part of an OD-connection-link (assumption 1). That would be Node 5. 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.