## 2 Literature Review
### Multi-Modal Route Planning  
In general terms, route-planning problems come in two main varieties: vehicle-routing problems (see [28] for a recent survey and classification scheme) and journey-planning problems. This work is concerned with the latter. Journey-planning problems themselves come in many varieties, including itinerary planning, where journeys must visit a specifiedsequence of intermediate locations/transfer points [29], and shortest-path problems, which are the focus in this work. Over the years, shortest-path-planning problems have been extended in a number of ways, including multiple objectives [30; 31; 32; 33; 34; 35], transport modes [36; 37; 38; 39] and network characteristics [40; 41]. For example, [PERSON]. [32] introduced a new exact-label-setting algorithm that returns the subset of Pareto optimal paths that satisfy a set of lexicographic goals, or a subset that minimises deviation from goals if these cannot be fully satisfied. [PERSON]. [39] presented an algorithm that considers the price optimisation (including driving and parking costs) as a Pareto criterion in addition to travel time and the number of transfers for multi-modal two-way round trip journeys. The term _multi-modal_ route planning refers to path-planning problems where transfers between different vehicles and types of vehicles are allowed en-route. This term has often been used in cases where the available modes are all fixed-schedule transport modes [29; 42; 43]. More recently, _multi-modal_ is most often used to refer to cases where the available modes also include what might be referred to as open-network modes, such as cars and bicycles, in addition to fixed-schedule modes, such as public transport services. Research into multi-modal journey planning has been becoming more and more general regarding the available transport modes, the objectives considered and the rules imposed on when different modes can be used and in what order. Ref. [8] proposed a fast algorithm for a special case of a multi-modal shortest-path problem in which the starts and ends of journeys use the road network, while the main part of the journey utilises public transport. Distances to and from public transport access-nodes are pre-computed and stored, meaning that, at query time, only the smaller public transport network is subject to a path search. In this work, pre-processing tasks are also employed to reduce query times; see Section 4.2. This work focuses on the development of a general multi-modal and multi-objective journey-planning algorithm, without imposing rules regarding allowable mode sequences. Previous works have focused on other special case problems. Ref. [44] developed a trip-planning algorithm that extends a time-minimised vehicle trip-planning system by integrating it with multi-criteria walking considerations. They argue that people are sensitive to walking for a great many reasons, including, exercise, physical capabilities, path gradients and environmental conditions at travel time. Ref. [9] introduced the RAPTOR algorithm for generating public transport and walking journeys that minimise travel time and number of transfers; it is often the case that journeys can be completed faster if commuters are willing to perform more transfers and walk more, since public transport timetables are not always conveniently synchronised with each other. More recently, ref. [10] proposed a _time-dependent inter-modal_\(A^{*}\) (TDIMA*) algorithm, which combines scheduled transport services, walking and vehicular transport networks. The objective was to minimise a weighted sum of travel time, waiting time and penalties for transfers between modes. The general trend towards rolling out the efficiencies brought about by digitisation, internet and instant telecommunications is making route-planning algorithm functionality available to an ever expanding portion of the population, often via MaaS apps.