# An Algorithm for Generating a Diverse Set of Multi-Modal Journeys
## 4 Computational Study
### Diversity Analysis  
As discussed in Section 3.1, in addition to journey time and number of transfers, the used mode of transport \(\mathcal{M}_{i}\) is also taken into account as a dominance criterion. While this increases the number of non-dominated states, it enables us to differentiate between solutions that employ diverse modes of transport to reach the destination. The experiment discussed in this subsection analyzed the impact of including \(\mathcal{M}_{i}\) as a dominance criterion on algorithm performance and solution diversity. Table 4 compares the performance of three configuration settings of the algorithm: (i) using all three dominance criteria, (ii) using journey time \(\mathcal{J}_{i}\) and number of transfers \(\mathcal{T}_{i}\) as dominance criteria, and (iii) using journey time \(\mathcal{J}_{i}\) as the only dominance criterion, essentially solving a shortest path problem. Solution diversity is quantified by computing the similarity between journeys returned by the algorithm. Therefore, in addition to the average run time in milliseconds, standard deviation of run time and the average number of solutions found (# Sols.), a similarity metric \(\text{Sim}_{1}\) is also reported. This metric is the weighted Jaccard distance and ranges from 0 to 1, reflecting how many arcs are shared between solutions [15]. A value of 0 indicates that journeys share no arcs whereas a value of 1 indicates that all journeys are identical. The weighted Jaccard distance is computed by Equation (9), where \(S_{P}\) is the set of arcs in path \(P\) and \(L(S_{P})\) is the length of the arcs in set \(S_{P}\). Note that when only journey time \(\mathcal{J}_{i}\) is considered, the similarity metric cannot be computed as only one solution is returned.  
\[\text{Sim}_{1}(S_{P_{i}},S_{P_{j}})=\frac{L(S_{P_{i}}\cap S_{P_{j}})}{L(S_{P_{ i}}\cup S_{P_{j}})} \tag{9}\]  
The results demonstrate that the number of solutions is clearly affected by the number of dominance criteria included. The setting that resulted in the highest number of solutions is when all three criteria are included. However, this also negatively impacts the required computation time. When comparing the single-objective setting against including all three dominance criteria, the required run time doubled or even almost tripled depending on  
\begin{table}
\begin{tabular}{l r r r r r r r r} \hline \hline  & \multicolumn{3}{c}{**London**} & \multicolumn{3}{c}{**New York City**} & \multicolumn{3}{c}{**Belgium**} \\ \cline{2-10}  & **Arcs** & **Run Time** & **Quality** & **Arcs** & **Run Time** & **Quality** & **Arcs** & **Run Time** & **Quality** \\ \hline No pre-processing & 6039 & 10 \(\pm\) 6 & 100.0 & 32,769 & 25 \(\pm\) 10 & 100.0 & 596,739 & 833 \(\pm\) 418 & 100.0 \\ Graph cutting & 6039 & 6 \(\pm\) 6 & 97.7 & 32,769 & 17 \(\pm\) 12 & 99.4 & 596,739 & 392 \(\pm\) 313 & 95.7 \\ Vertex merging & 5784 & 6 \(\pm\) 4 & 96.2 & 11,257 & 16 \(\pm\) 10 & 98.2 & 199,470 & 362 \(\pm\) 301 & 90.4 \\ Arc pruning & 3611 & 5 \(\pm\) 3 & 95.4 & 5945 & 12 \(\pm\) 7 & 97.8 & 117,523 & 264 \(\pm\) 212 & 86.7 \\ Arc restriction & 3611 & 5 \(\pm\) 3 & 95.4 & 5948 & 12 \(\pm\) 8 & 97.8 & 117,523 & 260 \(\pm\) 209 & 86.7 \\ \hline \hline \end{tabular}
\end{table}
Table 3: Impact of graph pre-processing.  
the network. Finally, the results demonstrate that when including \(\mathcal{M}_{i}\), journey similarity is impacted, however, not always positively. For the Belgium network, the returned solutions are very diverse, whereas the journeys returned for the London and New York City networks were more similar. Note that an exact comparison between the two multi-objective settings is complicated as the number of solutions also impacts journey similarity.