Simulating cities for a better ride-hailing experience at Bolt
Bolt helps 25 million people in 30 countries move around their cities. The responsibility is huge — every change can influence millions of customers. In this post, I’ll share our experience of using simulation to test the otherwise impossible and to help our teams make the right decisions without affecting the real users.
Motivation
You have been working hard on a new feature that is going to change the game. With big change comes big responsibility. The theory is sound, but there are many different moving pieces that are affected by your new implementation. You have looked at historic data, applied your novel method to the data, and seen obvious benefits. The problem is, by applying your method, the state of the world is going to change. It will become something you have never seen before. What if the gains happen as you have predicted but unpredictably cause the whole system to enter into a state where some processes start to fail? Sure, there’s an option of running an A/B test (although, in some cases, that might not be possible) — it will only require the actual implementation of the feature into the application, take possibly weeks to run, and in the worst case scenario affect real people negatively. It would come in handy to have a sandbox where one could test out their ideas in a fast and safe way. Enter the Simulator.
Overview
In Bolt’s case, the Simulator replicates a ride-hailing city. It uses a realistic environment — a city map with its road network — and agents such as generated drivers and riders. The Simulator emulates the city by taking advantage of the historic data, the maps of the cities, models giving accurate estimates of driving times based on the time of day, and models reflecting human behaviour under different circumstances. All of that is supported by matchmaking, dispatching, and pricing algorithms that can be custom-built. In addition to playing through “normal” situations in the city that are based on historical data, the existence of the Simulator allows users to play through modified situations, for example having a different level of supply in a certain area throughout the day. The Simulator outputs logs from which one can calculate different metrics, such as ETAs or the number of finished orders, to see how well the city has “performed”.
A simulation framework allows users to gain insight into how the different parts of the city affect one another. How much are the arrival times affected if demand is increased X times? What about if we change the dispatching algorithm? Many such situations can’t be tested in the real world since the 10x demand hasn’t happened, yet. There are no data points for the case where half of the supply drops during the evening rush hour traffic. What will happen to the city then? Are there any algorithms that perform better under such extreme circumstances? These types of questions are the ones that the Simulator is set up to answer.
How to make it realistic
As mentioned above, there are many different small (and some not so small) pieces that make the Simulator a usable tool. The driving force behind the simulation is the heartbeat of it — a tick that moves time forward. As one beat gets processed, everything is bound to change. Orders appear, disappear, or get assigned to drivers. Drivers come online, go offline, move around, or stay put. The number of orders and drivers in a specific region is estimated beforehand based on our own data and sampled from the Poisson distribution. If the city goes off balance, meaning that the drivers manage to end up in unlikely locations, the idle drivers start driving back to the city hotspots.
The driver movement does not take place in a uniform world though. OSRM maps with accurate roads allow users to route the drivers through the city as they would in real life. On top of the given routes, a trained ETA model adjusts the time it takes to get from point A to point B, using our knowledge of similar trips from the past.
Having orders and drivers geospatially in place is all nice and dandy, but orders would go unfulfilled and the drivers would just sit around being perfectly located if there wasn’t a mechanism that would try to pair up the orders with drivers. Therefore, during the beat there’s also matchmaking taking place, which tries to find the best available car for each order according to the logic provided. The probability of a given match between a driver and a rider happening is defined by a trained model that takes into consideration the state of the current world and that specific match.
In addition, matchmaking itself can have different flavours. Do we allow multiple passengers in one car? Should we match one order at a time or should we try to match multiple orders at a time by performing Hungarian Maximum Matching? Different matching algorithms require different implementations and will also have different consequences to the city. Another aspect of the matching is the definition of “an available car”. Which cars are eligible for dispatching and which aren’t? The design of the Simulator allows the user to define their own answers to these questions. In order to make sense of the output and to have a point of comparison — a baseline — the currently-in-production algorithms are also implemented into the Simulator. To see how well the Simulator baseline performs against the reality, one can, for example, look at the distribution of ETAs (Vis3) or compare the number of finished orders between the Simulator and reality.
Perfect accuracy is not attainable for any system. Even the most robust machine learning algorithms trained to do one specific task can’t produce 100% accurate results. However, our system built on top of generated orders, drivers, and models approximates reality well enough for business use.
Examples/results
Imagine you have a data set of a full day of orders with a time-generated timestamp, pickup timestamp (if it got a ride), drop-off timestamp (if it got a ride), start coordinates, and end coordinates. Additionally, each order has the location of where the matched driver was at the time of accepting the ride. You want to know how many of those orders would be affected if we allowed multiple orders in one car and everyone was willing to share a ride. You have also constrained the problem such that the overall ride, from the match to the drop-off, can’t take 1.1 times longer than it was initially supposed to. If the trip took 10min with only one passenger, then under the new rules, the new ride, with potentially another person in it, can’t take longer than 11min for that passenger.
One can look at each order and find orders with similar pickup locations and drop-off locations in a certain time window. In addition, it’s possible to produce routes for each order and then find routes that have some kind of a similarity score above a threshold. This already introduces complexity as we have to take into consideration driving speed for different routes — even though the routes are similar, the driver might not have enough time to pick up one order and get to the next one. There might also be orders that have different routes in isolation but when looked at together have an alternative route that adds no time penalty. So you would need a routing system and also a fairly accurate estimate of the time it takes to complete each route. Now you would also want to know if there are any orders that in reality didn’t have a car available but, thanks to the additional spot in the car, can get a ride. Can you fulfill more orders given the same amount of supply? Solving it just by looking at the data and making some assumptions is impossible. Every decision changes the state of the world — different orders get matched and drivers end up in changed locations. Soon enough, you realize you need a simulator that emulates the whole process of drivers driving around and picking up customers. Below, calculated thanks to the Simulator, there’s an example of the percentage of the rides affected by the additional spot in the car and the given constraints in three different cities (Vis4).
The Simulator can also show the power of different algorithms in action. Say we have figured out a smarter way of dispatching cars. Since the supply and demand balance is in constant fluctuation through time, one shouldn’t use a constant rule-set for dispatching. The amount of demand is a good proxy for how busy the city is. If there is little demand the traffic should also be fairly quiet. Therefore, we would like to allow dispatching further away, since the car could get to different places around the city quickly. During heavy traffic or high demand, we don’t want to dispatch cars very far away due to long ETAs. In theory, applying that logic should lower the amount of cases where we don’t have cars available for orders and also increase the number of finished rides. These situations might happen in different cities at different times so it would be smart to figure out a city and time-of-day independent estimate for them. Once that is figured out, it’s easy to plug the new logic into the Simulator, run some simulations under conditions that amplify the efficiency of the new algorithm, and verify your results.
As an example, for that simulation, we artificially lowered the supply by 4 times during the hours of 7AM — 7PM. It is clear that, thanks to the new algorithm, there are fewer orders without a car available (Vis5). One might assume we get an equivalent boost to the finished orders count. That is not the case, as the Simulator illustrates (Vis6), and this is due to the fact that the conditions for a successful match might not have been met for all those newly acquired orders — according to our built-in model. There is still an increase though so nothing is broken.
It would be foolish to use the numbers from the Simulator logs directly to make big decisions. The real value of the Simulator lies in the fact that it shows the trends and potential pitfalls, and allows users to verify their ideas in a safe manner.
Final words
The Simulator has been built step by step — small improvements along the way. It has already proven to be a powerful tool as such a system can be used to help solve many problems in the transportation data science world. With no single target and a bigger picture in mind, the process is still ongoing to make the simulations faster, better, and more accessible.
If this blog post got you excited about what we’re doing, remember that we’re hiring — check out our careers page.
