Contents
Finding the best way to get from point A to point B has been completely handed over to algorithms since the dawn of the 21st century. We no longer browse through paper maps but instead, use technology to get calculated feedback.
Real-life options, however, may still differ from what an algorithm can present us — and routing is still an evolving solution to an ever-complicated problem. What’s more, routing is only really helpful when it is built from a human perspective and takes into account the reality of how we actually navigate the world around us.
In this post, we’ll explore some of the complexities around multimodal routing and how the TravelTime API can help to solve many of these challenges.
What is multimodal routing?
With many different transit options and both time and physical limitations in mind, we may not want to drive to a congested urban location, spend time in traffic and get frustrated looking for a suitable parking spot. Instead, we may prefer to park our vehicle at a train station and reach our destination by train.
In contrast, in the Low Countries, it is only natural to take your bicycle on a ferry or a designated train cart and commute part of your journey by train, while cycling the rest of the way.
All these cases and many more require a more complex solution than mere single-mode routing. Multimodal transit routing is a natural extension of the classic problem to a more life-like navigation of our physical world.
Why is multimodal routing complicated?
Classic search algorithms such as A* and Dijkstra’s shortest path search are capable of delivering a quick solution to routing in the form of a graph. However, a graph is a mathematical abstraction — which works perfectly well for representing traversable roads, connected rail networks, waterways etc.
But such simple solutions are insufficient for solving the challenge of multimodal transit routing. A simple public transport journey could be considered multimodal since we have to consider possible transfers not just in the same stop, but also short journeys by foot between rail platforms or adjacent bus stops.
And to be ‘human-led’,alltransport journeys need to at least include walking, even if, in the case of driving, it is just from the departure location to the road.
As an example, let’s consider a journey that consists of both a) driving to a railway station and b) taking the train for the rest of the journey into a more congested part of the city.
We can start our journey in South East England, at one of a few potential departure points somewhere between the towns of Guildford and Woking.
Our intended destination is located just north of Vauxhall station.
You can find the location definitions we will be using in this post below:
The search of a journey from our chosen departure location to the destination will proceed in two stages. We can find all suitable railway stations in the first stage of the search.
The following images are example searches of only 15 minutesdrivingfrom given departure points. Stations captured in the shapes (isochrones) are potential candidates for a follow-up train journey.
Such a search corresponds to the one-to-many search implemented by the TravelTime API’s distance matrix / time-filter. It yields the best (under earliest arrival time optimality measure) journeys from a given point to multiple destinations.
The second part of the search involves taking that search state and exploring rail journeys departing from the reachable stations.
In effect this means that a 2-mode search (driving and then train in our case) involves a 2-stage search:
- Stage 1: find the nearest railway stations by car;
- Stage 2: search for departures from each station at the time of possible arrival.
The image below shows an optimal journey found fromdeparture point 1with its driving search state highlighted.
Depending on the location of the departure a different optimal journey may be found — the following 3 departure points are each within a closer driving time of different railway stations.
Here is the complete TravelTime API request for the computed journeys:
Naturally, with more factors to take into consideration, the process quickly becomes more complicated. For example, here we don’t consider the walking needed after the train-leg of the journey to reach the intended destination, possible delays due to parking the vehicle at the station etc.
Additionally, we haven’t considered the possibility of edge cases such as:
- What if simply driving the whole way to the destination would be faster than switching modes mid-journey?
- If we start our journey right next to a train station, do we still consider driving?
- What if no railway stations can be reached in the initial search stage?
How multimodal routing works with the TravelTime API
TravelTime currently provides a couple of implementations of multimodal routing.
For example, in the UK, in addition to the standard modes of transportation, such as walking, public transport, driving and cycling, a specialiseddriving+trainmode is offered. This is essentially an implementation of the previously discussed case — a journey consisting of 2 stages: driving (with parking included) and then continuing by train.
However, to compensate for the potential edge cases, our implementation ofdriving+trainsearch effectively involves 3 different searches. The following scheme covers both stages of the search, but stage 1 is in fact a union of search spaces explored viadrivingandwalking.
This allows us to construct several combinations of potential journeys:walking+train,only drivingetc., each covering a potential edge case.
Technical notes about the TravelTime API
Due to the computational complexity of such searches, they are better suited for analytics-oriented operations. With generous search parameters, a response should be expected in more than just a couple of seconds.
Additionally, since the computed journeys involve a fixed-schedule transit, the optimal journey may differ depending on the search time chosen.
Lastly, note that the provided examples are valid as of the time of writing this post — as our maps get updated, they may not contain outdated public transport information. And for use in the future, these examples would need their arrival/departure times updated accordingly.
What do the TravelTime API results mean and what do they look like?
As previously discussed, multimodal routing comes with added complexity and edge cases. To shed a little light on how multimodal search works in the TravelTime platform, let’s explore how those cases are handled by our API.
In the case ofdriving+train, 2 kinds of search happen before rail transit is considered: search space is explored in both walking and driving modes. From these, two sets of results are assembled — search space to continue exploration via rail and, if possible, full journey to designated destination via already used modes. Thus, under certain conditions, it is possible to find a route via only walking or only driving even before transit via rail is considered. The explored search space is then passed on to routing via train.
The combined result can yield journeys of 4 forms:
- Walk from departure location to destination– departure and arrival locations are very close to each other — very likely no train journey will be involved and the optimal journey will either be just walking or just driving;
- Drive from departure location to destination– departure and arrival locations are within the set driving limit and the driving journey is faster than the one involving a train journey;
- Walk from departure location to a train station, take a train towards the destination and if needed, walk the final leg of the journey from platform to the exact location– departure location is so close to the optimal train station that it is faster to walk there and the driving leg of the journey need not be involved. Penalising parking timenudges the algorithm towards such a result.
- Drive from departure location to a train station, take a train towards the destination, if needed walk the final leg of the journey from platform to the exact location– classic case as defined bydriving+trainmode.
As you can see, even a naive combination of modes of travel may result in various edge cases and the TravelTime API attempts to cover the most possible outcomes.
To give even more flexibility, detailed search parameters, such as driving_time_to_stationand parking_timecan be configured to have an effect on the search outcome. For example, the following departures in Woking differ little but the route from departure point 4 suggests driving to the station whereas the route from departure point 5 suggests walking instead.
Penalising parking_timemore would certainly nudge the algorithm towards offering walking in both cases. However, reducing the walking timeparameter could leave the station out of reach and the algorithm would opt for driving again.
Conclusion
As demonstrated, the complexity of multimodal search arises not only from an apparent multitude of combinations of transport a traveller can use, but also from various edge cases.
In actual applications this means both computationally expensive operations and protective logic to handle possible edge cases.
At the time of writing, the TravelTime API offers a couple of country-specific multimodal search implementations:driving+trainin the UK andcycling+public transportin the Netherlands. In both cases, we try to provide the best journey from the combined search space of all involved modes.
For example, adriving+trainroute search offered in the UK in fact can be understood as a combination of 3 many-to-one searches: exploration viawalking,drivingandpublic transport.
We hope this article has helped to demonstrate some use cases and clarified the behaviour of some of our more complex solutions provided by the TravelTime API. We constantly strive to improve existing service and push for further development of our platform and are always eager to hear of the needs of our users.
To try the TravelTime API for yourself, you can sign up for a free API key.