Blog

Charzer aims to find the most optimal location to install its charging stations which will best serve our customers and enable quick and fast charging. As part of this process, we have to determine the most optimal route between the customer and the charging station when they search for the nearest Charzer station on their Charzer app.

In order to recommend the most optimal charging station to our customers, we have tried a number of machine learning techniques. We were able to create an optimal route to traverse the road segment by taking into account the traffic which is influenced by time, weather, and real-life events using a partitioning algorithm based novel approach mentioned in this article published by Ankit Sirmorya in HighScalability, a widely read publication.  

Methodology

To accomplish this, he modeled every intersection as a node and every road segment as a directed edge. For finding the shortest route between source and destination, he used routing algorithms (e.g. Dijkstra’s algorithm). He also highlighted that for ride hailing platforms at the scale at which they operate, Dijkstra’s algorithm won’t work because it takes O(NlgN) to find the shortest path for “N” nodes.  A novel approach Ankit proposed was to divide the graph into partitions, precalculate the best path within each partition, and interact only with the boundaries within each partition. His approach significantly reduced the time complexity from O(NlgN) to O(N’lgN’), where N’ is the square root of N. After the optimal route has been determined, traffic, weather, and real-life events can be taken into account to calculate the estimated time to traverse the road segment and compute the ETA. A few other alternative techniques were also tried to find the optimal route, and some experiments were conducted to assess their performance. By using a partitioning algorithm approach, we discovered that the optimal route we found for our customers took 40% less distance and resulted in a 30% increase in their satisfaction ratings. To improve the experience of our customers, we continuously explore new technologies and experiment with new approaches.