Expert in Intelligent (Transport) Systems

Towards Fully Multimodal Journey Planning

Added on by Michal Jakob.

The recent update to Google Maps has finally brought the possibility of showing journey plans employing private and public transport modes side by side, facilitating the comparison of different travel options available to the traveller. This is certainly a move in the right direction much, however, remains to be done to fully leverage the potential of ever richer transport options offered to the traveller in modern cities.

Transport modes available in modern cities can be broadly divided into three categories. individual transport (also termed private transport), such as car, walk and bike; scheduled public transport services, such as underground, bus, rail or ferry; and flexible, on-demand services, such as taxi or bus on-demand. Together, these diverse transport modes, especially when treated in combination, offer a very wide range of travel options that can satisfy diverse traveller needs.

Unfortunately, none of existing journey planners support journey planning with the full set of transport modes. This means that a traveller who wants to combine car and public transport or to use walking bike and a metro to reach his destination still needs to plan his trips more or less manually. In many cases, travellers may not realize that a certain combination of modes would bring them to their destination fast/cheap/safe and resort to using modes that seem more straightforwrad to use, such as walk, bike or, unfortunately in most cases, car.

Fully Multimodal Journey Planner

This is why together with a PhD student of mine, Jan Hrnčíř, we started the development of a fully multimodal journey planner capable of finding plans involving any combinations of transport modes, as long as they bring the user to the destination quickly. In late June 2013, after more than a year of intensive research and development, our fully multimodal planner successfully passed pre-tests organized by the SUPERHUB project in three European cities and it will be deployed in full SUPERHUB trials involving hundreds of users at the end of the summer.

In order to be able to discover all useful combinations of transport modes, our planner utilizes two important technical inventions – generalized time dependent graph representation and journey plan templates.

Generalised Time-Dependent Graphs

Fully multimodal journey planning graph for Milano, Italy. Colours correspond to transport modes.

Journey planning is typically cast as a problem of finding a shortest (or, more precisely, a least cost) path through a graph. In the case of routing, i.e., planning for car, bike or walk trips, the journey planning graph more or less directly corresponds to the road network graph.

Planning with public transport services is more complicated, though. In this case, we need to encode routes and timetables of public transport services in a graph in such a way that the shortest path through the graph corresponds to a sequence of one or more public transport services that can be used to reach the destination location at the earliest possible time.

Two approaches to do this encoding have been studied and used in public transport journey planners. In the time-expanded approach (Muller-Hannemann, 2001), each event at a stop, e.g., the departure of a train, is modelled as a node in the planning graph; in the time-dependent approach (Brodal, 2002), the planning graph only contains one node for each stop. The graphs in the time-dependent approach thus contains fewer nodes but each node contains more information. Recent empirical studies (Pyrga, 2008) comparing the two approaches indicated that the use of the time-dependent approach often leads to faster planning times and we therefore also use it as the basis of our planner.

Both of the approaches have been known for quite some time but they’ve been only used for public transport journey planning. The key contribution of Jan and myself is that we've found a way to encode the information about PT transport services together with all other transport modes in a single planning graph. We call the resulting novel representation generalised time-dependent graphs. You can find more details about the representation in our recent paper (Hrncir, 2013).

Journey Plan Templates

Although fundamental to the operation of the planner, generalized time-dependent graphs are not the only innovation behind the fully journey planner we have developed. The second important ingredient are journey plan templates, which are regular expression describing the permissible sequences of transport nodes in returned journey plans. Although a conceptually simple tool, journey plan templates prove to be a surprisingly powerful tool supporting several objectives of journey planning at once.

The first and most important purpose of journey plan templates is to give the users of the journey planner a flexible tool to express their preferences on journey plans that should be returned. Using the templates, the user can e.g. specify that she does not want to travel using a bus or that he only wants to use a bike in combination with an underground but not a tram. In real-world deployment the templates might be preconfigured by an administrator of the planner and only exposed to the user through a simplified set of options.

Second, journey plan templates are used for (non-optimum) multi-criteria journey planning in case there are more than one criteria by which journey plans are assessed, such as duration, cost, emissions or physical effort. It is, e.g., possible to design an inexpensive journey template (employing walk or bike templates), an environmentally friendly template (employing walk, bike or public transport) or a fast template (employing car or taxi).

Finally, the journey plan patterns are used to constrain the search space and consequently to speed up journey planning.

You can find the description of the templates in our recent paper (Hrncir, 2013).

Summary and Outlook

Web frontend of the core planner

Our fully multimodal journey planner is at the core of the innovative SUPERHUB platform that will be open for experimentation in Helsinki, Barcelona and Milano at the end of the summer (see the SUPERHUB project website for more information). The core version of the planner is also directly accessible through a web frontend. At the same time, we’ve already started working on a second version of the planner which will provide more innovative features, including the handling of dynamic information or an improved support for multiple planning criteria. Over time, the journey planner will also be released as an open source software. Stay tuned!