## 5 Machine-Learning-Based Transfer Point Optimisation of Journey Profiles (Online)
### Many-to-Many Public Transport Shortest-Path Algorithm  
Algorithm 3 outlines our transfer-zone sequence constrained many-to-many adaptation of RAPTOR. As with standard RAPTOR, the algorithm works in transfer-iterations where each subsequent iteration attempts to find earlier arrival times to stops involving itineraries with one additional transfer (line 13). Within each transfer-iteration, the standard steps of RAPTOR are step 1 (line 14), step 2 (line 15) and step 3 (line 16). Step 1 gathers routes whose stops were reached at earlier times in the previous transfer-iteration, or routes serving origin stops in the first transfer-iteration. Step 2 cycles through those routes, finding earlier arrival times to the stops along it. Step 3 searches for stops that can be reached more quickly via walking connections from the stops reached more quickly via routes in the current transfer-iteration. The differences between our algorithm and RAPTOR are highlighted in bold italics and include steps 4-6. As specified on lines 15 and 16, RAPTOR target pruning no longer applies because we have multiple targets. In contrast to RAPTOR, our algorithm stores full itinerary information for the routes found to all stops. Our proposed approach for storing all itineraries is to store a path string for each stop and number of transfers which specifies the entire itinerary of the corresponding public transport journey. Each time an earlier arrival time to a stop is found, the corresponding path string is set as that of the predecessor stop in the route concatenated with details of how the stop was reached from the predecessor stop. In [9], the authors focus on finding earliest arrival times as quickly as possible, and only state that it is possible to recover itineraries from the algorithm. The path strings of origin stops (_origins_) specify which stop it is and the arrival time, so that the specific origin, of the many possible, is information that gets carried through the algorithm through the string concatenation itinerary storage approach. This itinerary storage approach was found to be more convenient than an approach based on storing references to parent stops, which is an approach that works well for open-network journey planning using Dijkstra-based algorithms. Our adaptation has the added feature that it stores and returns all public transport journeys to stops in the final target transfer zone (_reachedStops_). For the case where journey profiles contain consecutive public transport journey legs, Algorithm 3 builds a many-to-many shortest-path tree through the specified transfer-zone sequence for that multi-leg public transport journey. Step 6 applies transfer-zone sequence pruning so that the specified transfer-zone sequence is adhered to, which can be regarded as a speed-up technique. The adaptation also includes two fail safe mechanisms for cases in which the planned transfer-zone sequence of a journey leg cannot be followed due to real-time schedule information and disruptions. We waive the pruning of stops not in target transfer zones (Step 6) if none are found in the target transfer zones. Furthermore, extra transfer iterations, up to a maximum number, are added when no routes are found to stops in final target transfer zone. ```
1:Inputs:\(origins\), \(transfer\)ZoneSequence, \(maximumTransfers\), \(maximumExtIterations\). 2:\(reachedStops\leftarrow\emptyset\)
3:\(markedStops\leftarrow origins\)
4:\(extralIterationsPerformed=0\)
5:Reset earliest arrival times and \(full\) itineraries associated with all stops and number of transfers except for the stops in \(origins\). 6:for\(k\in\{1..maximumTransfers\}\)do
7:for\(i\in stops\setminus origins\)do
8:\(arrivalTime(i,k)\leftarrow\infty\)
9:\(pathString(i,k)=\emptyset\)
10:endfor
11:endfor
12:Perform the specified number of transfer iterations (information derived from a journey profile). 13:for\(k\in\{1..maximumTransfers\}\)do
14: Step 1. Gather routes reached in the previous round. 15: Step 2.