Ola trip match making algorithm
Arunav Goswami
Data Scientist || Machine Learning || NLP || Analytics || Stock Market
Ola is one of the leading online ride booking application in India. It is one of the first applications in the market of India who have introduced this concept of cab booking. Ola has decreased the hustle of booking cabs and negotiating charges with the drivers to just one touch and our ride is here and charges are dependent on the distance we cover.
Machine learning and artificial intelligence transform the world through their applications in various fields. More and more companies are leveraging the power of ML and AI to provide enhanced customer services. Ola is one of the big tech companies that continuously explores methods for better customer service. It keeps optimizing the service by implementing ML-based solutions.
We have observed while using the services of Ola or any other ridesharing company how efficiently their app can match us to our nearest available Ola driver while optimizing the ride fare and the ETA (Expected time of arrival). This is possible due to the match-making algorithm of OLA that matches us to a driver while taking care of different factors. As a customer, we get the best price and lowest possible ETA. The driver also gets to travel less distance to pick up.?
Trip Match making algorithm
Now let us understand how this match-making algorithm works and what data it requires to capture, to work efficiently.
The match-making algorithm of Ola determines which service driver has to be allocated to a new customer request. The first thing that needs to be factored in on how you are going to match the two sides, is how the marketplace is structured.
Ola is an example of a supplier pick model in which, the customer only makes a request and selects some variables associated with the service. Then on the basis of those variables, the algorithm selects the optimum driver for the customer. Then the request is forwarded to the driver who decides whether to accept or reject the request.
Every ML algorithm needs some input data to train the model. In the case of Ola, we as a customer provide the following details:
When the data and filters are confirmed then basic preprocessing of data is done like scaling location coordinates. After that, the algorithm is applied for match-making. There are multiple approaches, some of them are:
领英推荐
Na?ve approach
There can be multiple drivers available near you when you are trying to book a cab using Ola. The most simple approach would be to randomly choose an available driver within a pre-decided range of your location. This algorithm is easy to implement,?and might even work in a few scenarios. But that is not the case most of the time. This algorithm doesn’t care about the optimization of ETA or ride fare. It also doesn’t care about what is the traffic condition in that region. Therefore this algorithm can be used as a base for developing a complex algorithm but implementing this would bring bad experience to the customer and driver, which will not be good for the company.
Dijkstra’s algorithm
The Dijkstra algorithm tries to choose the most convenient of the paths between the origin and destination. Dijkstra’s Algorithm works by determining the weight of a path and constructing a route by choosing the paths with the lowest weights. A weight represents time or distance units determined by the engineering team. By making a decision based on the weight of a path, an engineer is building in constraints.
This approach is a little better than the naive approach but still, it is not good for determining the ETA as it considers no prior knowledge of the map. What if there is a mountain between customer and driver, then in that case driver has to take a longer route again which will not provide the optimal ETA and fare.
Geohashing
Geo-hashing is a method of grouping coordinates of drivers and customers based on their latitude and longitude. Using historical data from past Ola rides, the data team can record the average speed of the rides from one geohash to another and store that in a simple hash-table lookup.?Then, when calculating estimates, we would multiply the haversine distance between those two points with this speed to figure out a time estimate. This approach proved to be much more accurate and helped Ola avoid matching through mountains and to differentiate between highway and street travel. It was also very efficient but still didn’t do a great job of resolving one-way streets or rush-hour traffic as our estimates were the same for all hours of the day.
Fortunately, the geohash model is quick to implement and can work fairly well. We can add another nested hash table for each hour of the week between origin and destination which can reduce the inaccuracies around rush hour, and can continually iterate on this model to improve the estimates. This approach will become more accurate as we collect more data as we could break our model down into smaller geohash sizes.
Further improvements
Improvements in the algorithms are only done with one purpose to improve the quality of user experience.?Optimizing the match making algorithm, however, is not easy as in being able to achieve higher accuracy the computation becomes heavier which is itself a major problem. Improvement can be made from the very basic like how and what data is collected to train such algorithms. As we begin developing algorithms, remember that our first attempt may not address all of our problems and needs. But with time and iteration, we can continue to improve and optimize our solution.