In this series of posts we will be looking to design a cab hailing service similar to Uber or Ola (in India). We will be mainly concerned about the technical design and challenges and not get into the logistics such as signup and recruitment of drivers, training drivers for customer satisfaction, number of cabs on street and so on. Even for the technical design, we will omit some of the technical details regarding payment gateway integration, GPS navigation, frontend UI and UX etc.

Note : All the design process and thinking are of my own and may not be implemented by any of the cab hailing services.

The most important features of a ride hailing app like Uber or Ola are as follows :

- Matching a driver to a passenger for a single booking.
- Matching a driver, plus other passengers in cab pooling.
- Deciding optimized route for pooled cabs.
- Fare estimate for a trip (with dynamic or surge pricing).
- Targeting customers with SMS, Push notifications and Email.

Few other features are also important from the business perspective but will not cover them here.

- First time signup free rides for customers.
- Discounts and Referral promo codes.
- Bonuses for drivers on completing additional trips.
- In-App chat between driver and a customer.
- Cancellation and Fees.
- Passenger and Driver profiles.
- Notifications of arrival and cancellation of cabs.
- Showing the most likely locations to a customer on the home screen.
- Scheduling rides for a future time.
- Writing reviews for your ride.

In this post, we will be designing a strategy for matching passengers with drivers.

While I was visiting Ho Chi Minh city, Vietnam with my friends, the same cab was booked by the Uber app for three successive times in a span of two days. Probability of this being a mere co-incidence is very less.

We need to separate the case of single booking trips from shared or pooled cabs because they have different design challenges and constraints.

Trivial cases for matching would be :

- A single cab is enrolled and a single customer has signed up.
- Few other cabs have enrolled, but still a single customer. If 5 cabs are available within 1.5 km radius from the passenger, then the obvious choice is to allocate the cab closest to the passenger.
- By closest one can define the geographical distance between the cab and the passenger or the minimum distance travelled using the best route.
- What other options are there for cab allocation ?
- Driver and Passenger Rating : Passengers can rate drivers and drivers can rate passengers as well. Matching the highest rated (average) cab driver can lead to rich gets richer phenomena.

Non-trivial and more challenging scenario :

More than 10K cabs have enrolled and more than 10 million users have signed up.

Some challenges are :

- The number of cabs on road will be constant relative to the number of users trying to book a cab at a given moment in time.
- During peak hours, for every cab there could be more than 3-4 passengers trying to book it.
- Fixing a constant search range, will result in scenarios where there are more than one cab available for one passenger and no cabs available for another passenger.
- Not all un-available cabs might be in between a trip. Some of them might be ending a trip shortly and will be available.

Keeping in mind the above challenges, the goal of the cab assignment is to :

- Maximise the number of passengers getting a cab.
- Minimize the total waiting times of all passengers.
- Better than shortest route, because sometimes shortest route may have more delays due to traffic.

- Minimize the total distance travelled by all cabs.
- Since the shortest distance between pickup and drop of passenger is constant, minimize the distance from current location of cab to the pickup location.

- Create matches such that driver and passenger have similar ratings.

It is not possible to simultaneously minimize both the distance and waiting time from cab location to pickup location unless they are the same. So the best option is to minimize either one of them while keeping an upper bound on the other or both. This makes more sense since anyways we want to limit the waiting time as well as the distance.

For the rest of the post will assume that we are minimizing the total waiting time by constraining the maximum search radius to 1.5 km from the passenger.

Thus we need to track the following metrics :

- List of passenger ids who is trying to book a cab (but not allocated a cab).
- Pickup and Drop locations (GPS co-ordinates) of the above passenger ids.
- Average ratings given to the above passenger ids.
- List of cab ids that are currently available to be booked.
- Average ratings of drivers owning the above cab ids.
- Distance along the shortest route from cab location to passenger location.
- Maximum distance for matching = 1.5 km.

- Shortest time required to travel from cab location to passenger location.
- List of cab ids that will complete trip in the next 5 minutes.

Assuming some passenger P1 is trying to book a cab, retrieve the pickup location for the passenger and then within a search radius of 1.5 km, check if any cab is available. If a cab is available, then one option is to quickly allocate the cab C1 with the shortest time to pickup.

But this may not be the most optimal. There could be another passenger P2, whose booking came in just a second later, and has been assigned a cab C2. But C1 could be a better option for P2 while C2 a better option for P1 in terms of waiting time as well as distance travelled.

Note : The goal is not to minimize the individual waiting times but the overall waiting time.

One way to handle this is to not book a cab immediately but allow a time-frame of 3 seconds to find the best possible matching of cabs. If within the time-frame of 3 seconds multiple other booking requests identify the same cab C1 as the best choice, then with all the passengers who were matched with C1 and with all cabs other than C1, which are located within a distance of 1.5 km from the afore-mentioned passengers, create a matrix of cabs against passengers with waiting times as cost and then find the best matches subject to minimizing the total cost.

If P1 is matched to C3, P2 to C2 and P3 to C1, then total waiting time (cost) = 3 + 7 + 5 = 15 mins.

Will using a greedy strategy of assigning cabs to passengers work ?

Let's look at the following scenario.

Cab C2 is closer to P1, so C2 is assigned to P1, then P2 will be assigned cab C1.

The total distance traveled by cabs = 0.2 + 1.2 = 1.4 km

While if C1 was assigned to P1 and C2 to P2, then total distance travelled = 0.6 + 0.4 = 1.0 km.

Same reasoning would hold with waiting times also. Thus greedy approach is NOT the most optimal approach in this case.

This is an example of assignment problem in a bipartite graph. Given two sets of nodes (equal numbers) in a bipartite graph, create an one-to-one mapping so as to minimize the total edge costs. In our problem, one set of nodes represents the cabs and the other set represents the passengers and the cost is the waiting time.

There is an algorithm called the Hungarian Method, that computes the most optimal matching in O(N^{3}) time complexity, where N = max(#cabs, #passengers).

Till now we have used only the waiting time as a cost function, but remember we had another parameter, i.e. the ratings. One way to include ratings in the cost function is to add the absolute difference of the driver and passenger average rating with some weights :

Cost Function = 0.7 * passenger_wait_time + 0.3 * |driver_rating - passenger_rating|

Given that now we have the algorithm in place, let's look at some of the implementation details :

- We need to have MySQL tables for cabs, drivers and passengers.
- Table for drivers needs to store driver personal information (name, address, contact etc.), along with the average ratings given to them.
- Table for cabs needs to store the cab details (make, model etc.), the driver id of the driver.
- Tables for passengers, needs to store passenger personal details (name, contact, home location, office location etc.), average ratings given to them by drivers.

- Store each trip details in a document database such as MongoDB. The trip details will include some of the following :
- Cab id, Passenger id, Driver id
- Pickup and drop location (GPS co-ordinates).
- Start date-time and End date-time of trip.
- Ratings given by passenger to driver and driver to passenger.
- Waiting time of passenger.
- Distance travelled by cab to pickup location.

- Average ratings can be computed from trip data and updated into the MySQL tables.
- Use in-memory database like Redis to store the following :
- Current location of all the cabs. Refresh and update location after every second.
- Flag to indicate whether cab available or not available.
- Last trip start and end time. If cab is on-trip then start time of current trip and estimated end time.

Without proper indexing of the data, searching available cabs within a radius of 1.5 km, would require linear search over all cabs. Thus if there are 10K cabs, then for each booking request, we need to scan 10K entries in the Redis database.

Index the data. In most relational database, there is provision for spatial indexing, i.e. indexing of data corresponding to geographical coordinates. R-Trees and KD-Trees can be used to index geo-spatial data which gives very good lookup and range query performances.

Redis uses sorted sets to index the geo-spatial data.

The idea is to find the smallest bounding box such that all points that are at a distance of at-most 1.5 km can be found inside the box plus some other points which maybe at a distance greater than 1.5 km.

Lookup requires scanning all the cabs inside the bounding box to filter the ones that are at a distance of less than equal to 1.5 km and are also available. Time complexity is O(M + logN) where M is the number of cabs inside the smallest bounding box and N is the total number of cabs.

For each passenger request P_{i} above, search for available cabs within 1.5 km radius. These requests are added to a message queue.

In Redis create one mapping C_{P} from each cab id to the list of all passenger ids matched to it (within 1.5 km radius) and a reverse mapping P_{C} from passenger id to the list of cab ids. When a request comes in, update the mentioned maps.

From the time a request comes, after 3 seconds, remove the head of the message queue, retrieve the passenger id, then retrieve the cab ids for this passenger id from the map C_{P}. Then for each of these cab id, retrieve the list of other passenger ids from the map P_{C}.

Once we get tuples of (cab id, passenger id), create a matrix and then using the Hungarian method compute the optimal option for the current passenger id P_{i} retrieved from the head of the queue and allocate a cab and then update the maps C_{P} and P_{C }to remove the passenger id and the cab id already matched.

During peak hours, one cab can be matched with 4-5 other passengers and each passenger is matched to maximum of 8 cabs. So the size of the matrix for each passenger request may not exceed 10x10.

Even with O(N^{3}) run time for Hungarian method, dealing with 10x10 matrices would not take more than a few milliseconds to process.

To reduce delays with many concurrent booking requests, use multiple message queues in parallel and insert the requests in a round-robin fashion. Use asynchronous threads to compute optimal matching for a request, so that one passenger do not remain blocked due to optimal matching computations for the previous request in the queue.

Categories: DESIGN, MACHINE LEARNING, PROBLEM SOLVING

Tags: Cab hailing service, Cab-Passenger Matrix, Design, Google Maps, Hungarian Method, Uber