Ola trip match making Algorithm
Today, booking cabs by mobile is a common practice. Companies like OLA and Uber have been very successful in this regard. It is much easier to book cars on phones than to go out and look for one. Other important features are security and payments. Customers can pay with UPI or cards immediately, they do not need cash to make a payment. Driver details, and ratings are displayed, this ensures safety for customers.
From a customer perspective, it is much easier to book a cab. The customer is then handed over to the driver. Customers receive a notification when the driver arrives at the venue, the payment method is set. All in all, the experience flows free and easy. It is much easier than going out and looking for the car alone.
The question is, how does this work? There should be some algorithms running in the background to match the client and the driver. This algorithm should not only be fast but also accurate. Customers are king and should not be left disappointed.
Here are some details about the algorithms used by cab companies to match customers and drivers.
Buyer Pick Model
As the name suggests that buyers or customers are in a state of luxury to choose according to their preferences. The customer here selects the type of cable they need. Typically, in the buyer selection model, after the preferred selection, the customer is given a list of options to choose from. In the case of OLA or Uber, this section is automatic. The driver is selected automatically. The customer is then shown the cost of the trip, if the buyer is happy with the cost, the cable can be booked.
OLA and Uber have an extensive database of drivers, and once a customer has requested a cab, the driver closest to them at the time will be offered a ride. Multiple data such as traffic data, location data, and time are often used to predict demand and supply on time to determine prices.
These same algorithms usually have a double commitment. In this sense, the journey should be committed to both ends, that is, from the passenger and the driver. If the customer accepts the taxi at a given price, the driver may choose to accept or reject the request.
These algorithms include the concept of solid and soft filters.
Sturdy filters ensure a comfortable ride for both drivers and passengers. These filters can be set by both according to their preferences. These filters are conditions that must be met before a ride. Some of the solid filters can be location, pricing conditions, etc. In countries like the US, where women often work as sailors. The algorithm also allows the passenger to select the driver’s gender. These filters are known as solid filters because these are the conditions to be met.
Soft filters help filter out results. These can be filtered related to cab type, driver ratings, etc. Soft filters can help balance the load and ensure drivers are not overloaded with travel. These algorithms can also help provide the driver with a complete route to his destination. These filters are naturally intelligent, they may not be easily visible but are used continuously in the background.
Real-time Match-Making
Map-matching is a process that maps raw GPS locations to road segments on a road network in order to create an estimate of the route taken by a vehicle.
Why We need:
At the end of a ride, compute the distance traveled by a driver to calculate the fare.
In real-time, to provide accurate locations to the ETA team and make dispatch decisions as well as to display the drivers’ cars on the rider app.
Challenge:
A bad map-matched location leads to inaccurate ETAs, then too bad dispatch decisions and upset drivers and riders. Map-matching thus directly impacts Lyft’s marketplace and has important consequences on our users’ experience.
Assigning Pick-Ups to Driver
We can use linear programming to assign the Driver to the customer based on the minimum weights.
- Maximum Flow Minimum Cut Problem
the maximum flow through any network from a given source to a given sink is exactly equal to the minimum sum of a cut.
2. Assignment Problem
the task of assigning n jobs to m machines/workers.
- We can formulate the assignment of Uber drivers (=workers) to nearby pick-ups (=tasks) as minimization of waiting time (=objective function) derived from how far, in minutes, the drivers are to pick-ups (=cost).
- assigning the fastest pick-ups of Uber = minimizing waiting times of all nearby available drivers and riders.