# An Algorithm for Generating a Diverse Set of Multi-Modal Journeys
### Multi-Modal Journey Planning  
There have been a number of important contributions with respect to route and journey planning over the last twenty years. In road networks, shortest paths can be found in graphs consisting of millions of vertices and arcs in only a few milliseconds thanks to sophisticated algorithms that combine extensive pre-processing with intelligent search [2; 3]. Journey planning problems that involve public transport are typically modeled using either time-expanded or time-dependent models. In a time-expanded model, there is a vertex for each event in the timetable. There are arcs between vertices representing events associated with the same trip as well as between vertices belonging to the same stop. Time-dependent models are generally smaller and consist of one vertex for each stop. Arcs between vertices (stops) are characterized by travel time functions that map departure times to arrival times. Several extensions and variations of these two basic models have been proposed, for example to handle fast updates of timetable-related data in case of delays [4]. Finding journeys in public transport networks is complicated by the fact that transfers, typically performed in a secondary network, also need to be included in solutions. Early methods for journey planning in public transport networks were restricted to transfers on foot between public transport stops [5]. Noteworthy early approaches to journey planning include round-based public transit optimized routing, the connection scan algorithm and trip-based public transit routing [6; 7; 8]. Common to these methods is the assumption that the graph used to model the transfer network is transitively closed: if transfers from location \(a\) to \(b\) and from location \(b\) to \(c\) are possible, then a transfer from location \(a\) to \(c\) should also be possible. For real-world public transport networks, this assumption can lead to very large transfer networks. Therefore, these three algorithms include additional restrictions that forbid lengthy transfers, based on the assumption that long transfers are rarely part of optimized journeys and are usually not preferred by users. These additional restrictions considerably reduce the number of edges in the transfer network. More recently, research efforts have shifted toward solving what is the true multi-modal journey planning problem: combining public transport with a general unrestricted mode of transport. This unrestricted transfer network generalizes transitively-closed transfer networks to allow fully fledged routing in very large road or pedestrian networks. [PERSON] et al. [9] achieved this by using a pre-processing technique that computes a small number of so-called transfer shortcuts that enable the discovery of optimal solutions. [PERSON] et al. [10] employed a different pre-processing step in which the multi-modal network is partitioned. By using pre-computed shortest paths between the partitions in a bi-directional Dijkstra algorithm, solutions are found in short computation times. [PERSON] and [PERSON] [11] solved a journey planning problem with transfers permitted between all modes of transport while optimizing for three objectives: arrival time, number of public transport trips used and time spent on transfers. They proposed an algorithm based on trip-based public transit routing [8] that eliminates the need to explicitly represent the Pareto set of non-dominated solutions. Car travel in multi-modal journeys is often heavily restricted in existing approaches in order to limit the number of possible solutions and reduce computation time. For example, [PERSON] et al. [12] only allowed car travel at either the beginning or end of a journey. As a result, journeys that employ car travel as an intermediary link between two modes of transport are not considered. [PERSON] et al. [13] defined specific combinations of modes of transport to be feasible: (i) only car travel, (ii) public transport and walking but no car travel and (iii) mostly public transport, little walking and little car travel.