From Transit to Urban Mobility, Part 2: Evolution

30 May 2016 by Dzianis Dudnik

In Part 1 we briefly described what our starting position was before we transitioned from Transit to Urban Mobility. This time you'll see what changes were made to our platform (and to Meta-Router specifically) to accommodate all the new use cases we now need to support. This is an ongoing process, so it's possible something will change in the future.

Let's start with the high-level requirements. What are the main use cases we want to cover? After many discussions, we came up with these two generic cases.

  1. Multi-modal routing. We still provide Transit routes but we also want to give all other alternative ways to cover the same route from A to B so our customers can easily compare journey time, cost and other factors. Do I still take the metro or the bus, or should I consider car-sharing if there is a free car nearby? Or maybe I should just take a cab which is more expensive but much faster. Having all the options outlined for you makes it easier to decide.
  2. Inter-modal routing. This is somewhat more challenging. Here we want to combine different means of transport to provide the best option for your route. This is best explained by examples. Say, you live outside the city and you need to get to work and back every day. Which options could be the best for you?

You could take public transport all the way. But what if the bus that takes you to local train station is too slow or too busy? Then you might consider taking your own car and parking it at the bigger station which is a bit further from your home, than take a train to the city and cover the last mile by taxi.

Scale it up a bit to intercity transit and it adds a whole bunch of new options to the mix, such as long-distance trains and flights. You can see the challenge: a vast number of combinations and options and not all of them of real value to the customer.

These are the tasks that faced us.

Multi-modal routing

As you might have guessed, this particular use case can be essentially reduced to aggregation. Fortunately, Meta-Router already has what we need to make use of them:

  • external routing planners Car/bike sharing or taxi providers have an API which they use to power their own applications and services and to integrate with others. As I mentioned in part 1, in certain regions we have to consult these external APIs to get the best result for Transit. We can re-use the same approach here.
  • a plug-in-based design that is very adaptable When an incoming request is being sent to the actual routing engine cluster, we can also set which particular Meta-Router plug-in should be used to handle this request in the end. This is actually used to integrate various external routing planners: each of them is handled by the specific plug-in which is capable of communicating with a specific API provided by this planner.

However, we still have to change the way the Meta-Router processes the incoming request. If you remember, the original Grid component used to give us a list of regions sorted by routing quality, which is queried sequentially. It wouldn’t work with additional external providers as only one of them will be providing the end result. If we decided to call all of them it would take too much time.

So we decided that some data-packages or external routing planners would be ear-marked to provide multi-modal alternatives. This means that incoming requests can be served both by conventional Transit and those multi-modal alternatives. We do this by executing several concurrent tasks:

  • sequentially calling sorted list of regions providing Transit routes as before
  • calling every plug-in for every external API provider that is capable of providing alternative results

All results are then merged into a single response and returned to the customer.

Since all of the concurrent tasks are going to make remote calls that are I/O bound, we use the Gevent library with its light-weight pseudo-concurrent micro-threads,  called ‘greenlets'. This gives us the possibility to run a huge number of calls concurrently as long as we keep those I/O bound. So potentially we could scale up to provide as many alternatives from external providers as we want. Consider this one solved!

Inter-modal routing

As I said before this is the more challenging one. Not only do we need to aggregate many different sources, but we also have to query and combine their results in a meaningful way. We decided to start with a slightly simplified use case: long-distance routing. Whenever you plan to travel, say, more than 150 to 200km, you are probably going to take a long-distance service such as a train, bus or flight to cover most of your journey. You will also need to get from your origin to the train station or airport and to your final destination using local transport. Sounds like something we can solve.

We created a new component which is a part of Meta-Router (which we internally call InterPoolRouter). This is a reactive asynchronous component which is triggered by a message containing the long-distance part of the journey (for example, between two big train stations or airports). When it receives this message, the InterPoolRouter resolves all missing bits and connects everything into a single route or several routes, depending on the number of long-distance parts received in a message. Then the main Meta-Router tasks triggered by the original incoming request can query this component for any results that are ready. In the end we were able to come up with a rather clean solution for the internals of InterPool Router and reuse as much existing code as we can.

And where do the long-distance parts of the journey come from? Well, they come from those concurrent flows executed by Meta-Router when aggregating all the alternatives. Since we know which plug-ins correspond to which service providers and which providers are capable of calculating long-distance routes, we can inject posting messages to the InterPoolRouter component and query InterPoolRouter for results later. In the end we will receive results like this: take a car share to the airport, take a flight, take a cab to your destination.

Of course, this approach does not solve the inter-modal case completely, but it's a good start. So in the near future we will continue working on it to improve the results and routing quality, as well as aggregate even more external alternative routing providers. Stay tuned for our updates!