Xerox’s European research labs trip planner engine at the core of ‘Mobility Companion’.
Blog author: Luis R. Ulloa
If you live in a city you’re probably spoilt for choice on how to get around – public transport, bike, car sharing, ride sharing or taxi. Yet, despite being faced with all these options, most people still jump in their car to get to their destination. They do so because it’s simple. The effort it takes to figure out the best way to travel with different operators and modes is so big that most people shy away from the complexity and prefer to use what they’re most familiar with. And they do so even though they know it’s not the most economical, eco-friendly, fastest or even enjoyable choice they’ve made.
To tackle this complexity and encourage more sustainable choices, a number of city trip planning apps have appeared to help people organize their travel in the same way GPS navigation systems help drivers on the road. However, building a reliable, easy-to-use trip planning app is a challenge to meet some basic requirements that will make people give the car the definitive boot.
Dynamic, personal and transparent
For a travel app to become the first step in any trip it must be able to do three things - provide the full array of travel options available, incorporate reliable real time information on the fly and learn individual travel preferences to make planning fast and smooth. Making these three capabilities a reality has been the focus of Xerox’s European research labs in creating the trip planner engine at the core of ‘Mobility Companion’.
To illustrate what’s behind multimodal multi-provider planning, let’s go back to the example of the GPS. To model the different routes a vehicle can take the GPS uses graphs. This works perfectly well if you stay in a single vehicle but the graph gets too big to handle if you start switching modes. If for example you decide to leave your car next to a bus stop and continue your travel via public transit, generating a graph with all the possible bus stops and all the possible options of travel from there is extremely challenging. Moreover, most travel options, and in particular scheduled services such as public transport, require not only an origin and destination but also a time when the service is available.
Altogether these options create a combinatorial complexity that would very quickly explode the size of a graph representation of the network.
To address this complexity, a common approach is to simplify the problem by simply ignoring some options. Another way is to allow travellers to switch between modes at predetermined, specific 'hubs' and not any just anywhere. This aggregates results at only a few connection points but it has the same problem as the previous solution whereby it excludes a number of options. A third approach is to quite simply ignore the time dimension. None of these solutions are ideal and, in some cases, they may even generate itineraries which don’t make any sense encouraging the traveller to once again head for the car key.
One way to get around the problem of calculating all possible options is to ‘pre-compute’ travel paths. The speed this gives does however have two drawbacks: it requires expensive storage and computing infrastructures and secondly, it cannot integrate any network information changes as the preprocessing may require hours or days of computation.
Our approach is based on a completely different way of modelling the network and an algorithm that allows us to calculate all possible combinations of transport modes without relying on any preprocessing for the parts of the trips that are subject to constant change and in particular, public transport schedules.
Only a sfew transport services are able to provide ‘real time’ information to passengers within a timeframe that is acceptable to the user.
Even when this information is available, most apps are victim to the preprocessing described earlier, and can’t integrate the information at the time of a trip planning request. Very often the trip planner user interface will just mention delays or changes associated to a leg of the itinerary without actually integrating it. The traveller needs to do the calculation themselves.
As more and more real time information becomes available from mobility services systems we believe our system will be alone in proposing its users, valid alternative travel solutions when unforeseen delays and incidents occur on the move.
Multimodal trip planning represents a whole new challenge in visually presenting results to users. When you plan a trip with your car you basically choose between fastest or cheapest in the satnav. In a multimodal trip, the number of options and user preferences is much bigger and more complex to communicate.
You may prefer one type of service or mode of transport over another (e.g. tram vs bus) and want to completely avoid others. You’ll also typically want to consider criteria other than the price and arrival time such as the number of transfers, the frequency of the service, the walking distance or the waiting time between connections. The fact that you’re going to prefer one option from a set of alternatives relies on a complex, context-dependent, combination of criteria that may be totally unpredictable such as the weather, the other constraints you have that day, why you’re travelling in the first place or the mood that you happen to be in.
In proposing options, the usual method is to submit several queries to the trip planning engine with some predefined possible combinations of transportation modes and services. This is designed to return the best result for each combination and allows the user to sort the results criterion per criterion e.g. cheapest, fastest...
The Mobility Companion engine uses a generic model that considers all possible combinations of modes in a single query. This makes it easy to configure the specific user criteria and easily integrate new services or city information as they become available. Yet another mechanism provides alternative paths using the same combination of transport modes to propose different travel experiences.