# An Algorithm for Generating a Diverse Set of Multi-Modal Journeys
## 3 Routing Algorithm
### Search Algorithm  
The proposed algorithm uses states to represent (partial) paths. A state \(\sigma_{p}\) is defined to hold the following information concerning a path \(P\):  
\[\sigma_{P}=(i,a,\mathcal{J}_{i},\mathcal{T}_{i},\mathcal{M}_{i}) \tag{1}\]  
where \(i\) is the last vertex visited in path \(P\) and \(a\) is the arc used to reach this vertex, such that \(h(a)=i\). Variable \(\mathcal{J}_{i}\) is the time at which vertex \(i\) is reached, while \(\mathcal{T}_{i}\) corresponds to the number of transfers made along the path. A transfer is counted each time a different mode of transport is employed in the sequence of the solution path. However, to avoid penalizing short transfers by foot, a threshold parameter \(\pi\) is employed. What this means is that as long as the walking duration is less than \(\pi\), it will not count as an additional transfer. For example, the walk itself when changing between two buses located very close to each other at a transport hub will not be counted if it does not take longer than \(\pi\). Finally, \(\mathcal{M}_{i}\) is the set of modes of transport used along the path. Journey time and number of transfers are widely employed objectives in the literature [6; 21; 22; 23]. However, we introduce \(\mathcal{M}_{i}\) as an additional variable in a state to enable differentiating between solutions that use different modes of transport, and can thus be considered diverse. Algorithm 1 extends a state along each outgoing arc \(a\) of \(\sigma_{p}(i)\) in \(G\), thereby producing a new state in which the partial path is extended from the current node \(t(a)\) (which equals \(\sigma_{P}(i)\)) to the next node \(h(a)\). The variables in the states are updated as follows:  
\[\mathcal{J}_{h(a)} =\left\{ \begin{array}{ll}\mathcal{J}_{t(a)}+w(\mathcal{J}_{t(a) },a)+d(a)&\quad\text{if $a$ is a timeabled arc}\\ \mathcal{J}_{t(a)}+d(a)&\quad\text{otherwise}\end{array} \right. \tag{2}\] \[\mathcal{T}_{h(a)} =\left\{ \begin{array}{ll}\mathcal{T}_{t(a)}&\quad\text{if $a$ is a footpath arc and $d(a)\leq\pi$}\\ \mathcal{T}_{t(a)}+1&\quad\text{otherwise}\end{array} \right.\] (3) \[\mathcal{M}_{h(a)} =\mathcal{M}_{t(a)}\cup m(a) \tag{4}\]  
Note that \(\mathcal{M}_{i}\) is implemented as a set containing only unique values corresponding to the modes of transport used in path \(P\) and will therefore not be updated if the path continues using the same mode of transport. If the partial path is extended with a timetabled arc, the earliest possible departure time at node \(t(a)\) is always selected. A state is considered feasible if \(\mathcal{J}_{i}\) is less than or equal to the user's latest arrival time \(t^{\text{end}}\). States associated with paths that do not respect this condition are not extended. Using the information stored in the states, we can determine conditions to define when one path dominates another, thereby allowing some states to be discarded. Consider two states \(\sigma_{P}\) and \(\sigma_{P}^{\prime}\) that have reached the same node \(i\). State \(\sigma_{P}\) dominates \(\sigma_{P}^{\prime}\) when all of the following conditions hold with at least one strict inequality:  
\[\mathcal{J}_{i} \leq\mathcal{J}_{i}^{\prime} \tag{5}\] \[\mathcal{T}_{i} \leq\mathcal{T}_{i}^{\prime}\] (6) \[\mathcal{M}_{i} \leq\mathcal{M}_{i}^{\prime} \tag{7}\]  
The algorithm iterates through all elements in a priority queue \(Q\) that prioritizes partial paths that have the earliest arrival time at the destination vertex. This arrival time is calculated by the path's current time plus an estimation of the additional time required to reach the destination. More specifically, the priority cost is set to \(\sigma_{P}(\mathcal{J}_{i})+\theta(\sigma_{P}(i))\), where \(\sigma_{P}(\mathcal{J}_{i})\) is the time in the state associated with path \(P\) and \(\theta(\sigma_{P}(i))\) is a lower bound on theestimated remaining time to destination.