## 5 Machine-Learning-Based Transfer Point Optimisation of Journey Profiles (Online)
### Many-to-Many Open-Network Shortest-Path Algorithm  
Algorithm 2 presents our target transfer-zone-directed many-to-many shortest-path algorithm with speed ups for open transport networks. The algorithm is designed to grow a many-to-many shortest-path tree from specified nodes in the origin transfer zone (_origins_) to nodes in the destination transfer zone (_reachedNodes_). The algorithm is based on the main steps of [PERSON]'s algorithm (lines 6-10, 20-21, 38-45), but also makes use of three different speed-up techniques. Both of the first two speed-up techniques are based on partitioning transport network nodes into clusters, each with defined boundary nodes; for this, Algorithm 1 is used. Firstly, the _arc flag_ speed up (lines 25-30) is used to avoid the consideration of paths with edges known not to lie on any shortest paths from _arc flag boundary nodes_ to any _arc flag boundary regions_ overlapping with the target transfer zone (_endTransferZone_). Secondly, the _cross-region edge label_ speed up (lines 32-36) is used avoid the consideration of paths with edges, not in either the origin or destination transfer zone, that are known not to be in any _cross-region edge label_ boundary zone shortest paths; Section 5.1.1 provides further details. Thirdly, the algorithm is provided with a dummy target destination location (_dummyDestination_) somewhere within the target destination transfer zone, which is used to simulate the goal-directed A* speed up of [PERSON]'s algorithm, in which the candidate list is sorted according to lower bound estimates (\"as the crow flies\") of the arrival times at the dummy destination from the given node's location. This has the effect of prioritising the resolution of shortest paths closer to the target transfer zone. The algorithm terminates when it is known that the shortest paths to all of the target transfer-zone nodes have been resolved. Figure 3: Flow chart for the machine-learning prediction guided transfer point optimisation procedure. ```
1:Inputs: origins, startTransferZone, endTransferZone, dummyDestination, maxSpeed, numberOfNodesInTargetTransferZone. 2://Initialise candidate list, the set and number of target nodes reached. 3:\(candidateList\gets origins\)
4:\(reachedNodes\leftarrow\emptyset\)
5:\(nodesInTargetTrans\)\(ferZoneScanned=0\)
6:while\(|candidateList|>0\)do
7://Resolve and scan the unresolved node with the lowest heuristic score and store the origin associated with the resolved path. 8:\(nodeToScan\leftarrow candidateList(1)\)
9:\(candidateList\gets candidateList\setminus\{nodeToScan\}\)
10:\(nodeToScan.currentLegStartNode\gets nodeToScan.parentNode.currentLegStartNode\)
11:if\(transferZone(nodeToScan)=endTransferZone\)then
12:\(nodesInTargetTrans\)\(ferZoneScanned=nodesInTargetTrans\)\(ferZoneScanned+1\)
13:\(reachedNodes\gets reachedNodes\cup\{nodeToScan\}\)
14:endif
15://Check if termination criterion is satisfied. 16:if\(nodesInTargetTrans\)\(ferZoneScanned=numberOfNodesInTargetTrans\)\(ferZone\)then
17:Return reachedNodes
18:endif
19://Consider whether shorter paths to nodes linked to nodeToScan can be found. 20:\(edgesOut\gets nodeToScan.edgesOut\)
21:for\(edge\in edgesOut\)
22://Apply speed ups. 23:\(edgePruned=false\)
24://Arc flag speed up. 25:if\(arcFlagBoundaryNode(nodeToScan)\)then
26:\(edgePruned=true\)
27:if\(edge.onASHortestPathToSomeWhereInATargetArcFlagBoundaryZone\)\((endTransferZone)\)then
28:\(edgePruned=false\)
29:endif
30:endif
31://Cross region edge label speed up. 32:if\((transferZone(nodeToScan)\
eq startTransferZone)\)\(\vee\)\((transferZone(nodeToScan)\
eq endTransferZone)\)then
33:if\(-edge.crossRegionShortestPathEdge\)then
34:\(edgePruned=true\)
35:endif
36:endif
37:if\(-edgePruned\)then
38:\(nextNode=edge.endNode\)
39:\(newPathTime=nodeToScan.pathTime+edge.time\)
40:if\(newPathTime<nextNode.pathTime\)then
41://Shorter path to \(nextNode\) found, update candidate list and store new parent node.