# An Algorithm for Generating a Diverse Set of Multi-Modal Journeys
## 2 Problem Model  
This paper employs a graph-based model of the multi-modal journey planning problem. Let \(G=(V,A)\) be a graph where \(V=\{1,...,|V|\}\) is the set of vertices and \(A=\{1,...,|A|\}\) is the set of arcs. Each vertex represents a physical location associated with a mode of transport, for example a platform in a train station or a parking location used for park-and-ride. Arcs between vertices represent the ability to travel between two locations. An arc \(a\in A\) is characterized by its tail and head vertices \(t(a)\) and \(h(a)\), respectively. Note that the tail and head vertices must be different for an arc \(\{t(a)\
eq h(a)\}\). It is possible for multiple arcs to connect the same pair of vertices when a user can travel between these two locations using different modes of transport. We consider always-accessible modes of transport such as walking, cycling or driving as well as timetabled services such as train, metro or bus. The set of arcs \(A^{1}\subseteq A\) is associated with modes that are always accessible. An always-accessible arc \(a\in A^{1}\) is characterized only by the duration required to travel from \(t(a)\) to \(h(a)\), which is denoted by \(d(a)\). The arcs in set \(A^{2}\subseteq A\) are associated with timetabled services. A timetabled arc \(a\in A^{2}\) represents a timetabled mode of transport characterized by a set of departure and arrival times from \(t(a)\) to \(h(a)\). Because of the timetable, a user may need to wait for the next departure time at vertex \(t(a)\). The waiting time when arriving at time \(t\) at vertex \(t(a)\) is computed by the function \(w(t,a)\). If two or more instantiations of the same timetabled mode of transport travel from vertex \(t(a)\) to vertex \(h(a)\), their timetables are merged. This may occur when, for example, there are two bus lines that serve the same two consecutive stops. The resulting aggregated timetable is then used to compute the waiting time. Note that timetables are only merged for instantiations of the same mode of transport. What this means is that in our example involving bus lines, the timetable of a train traveling between the same two stops will not be included in the aggregated timetable as it corresponds to a different mode of transport. The considered modes of transport are defined by the set \(M\). The elements in this set refer to general modes of transport--such as car, train or bus--and not to specific instantiations of these modes such as specific trains or buses. Each arc \(a\in A\) is associated with one mode \(m(a)\in M\). As car travel is a special mode of transport that we wish to emphasize, Figure 1 illustrates the different forms car travel may assume. Figure 1(i) corresponds to traveling the entire journey by car, while Figures 1(ii)-(iv) illustrate different combinations of car travel and other modes of transport. A car can be used to cover the journey's first/last mile or to travel to a park-and-ride location that is close to the destination. For first-mile car travel (Figure 1(ii)), always-accessible arcs are added between the origin vertex and hubs located close to the origin. Hubs are vertices of the graph that represent highly interconnected locations. Similarly, for last-mile car travel (Figure 1(iii)), arcs are added between hubs close to the destination vertex and the destination vertex itself. To model driving to park-and-ride locations (Figure 1(iv)), always-accessible arcs are added between the origin vertex and vertices close the destination that represent park-and-ride locations. Each of these forms of car travel is considered a unique mode of transport, and will therefore be included separately in \(M\). By doing so, a distinction is made between the different forms of car travel, allowing for greater solution diversity. Note that arcs representing these modes are added to \(G\) when a query is made as they connect query-dependent origin and destination vertices to existing vertices in \(G\).