Finding the Optimal Route

Finding the optimal route is finding the shortest path given that the node is an intersection and an edge is the road segment. The shortest path algorithm can be solved using Dijkstra’s algorithm which has a runtime complexity of O(nlogn).

But you could imagine that a city with thousands of intersections and roads, O(nlogn) is computationally expensive. This can be simplified by partitioning a route using graph partitioning then find the shortest path per segment. Then, the shortest path is just the series of shortest path from the starting and end point of each segment. Though the solution may be suboptimal compared to the global-level calculation, the difference is most likely minuscule and improves computational efficiency.

Training ETA Prediction

With the routing engine providing the shortest route, you can now build an ETA model. Essentially, you have two models: (1) intersection model and (2) road segment model. The intersection model uses metadata about the intersection to predict waiting time while the road segment model predicts the travel time between the intersections. The sum of the waiting time from intersection and travel time from the road segment model gives you the total ETA time of a trip. You will train the two models independently.

Model Selection

You could consider the following model algorithms, and apply hyper-parameter tuning to find the optimal variance and bias trade-off in relation to the offline metric used to train the model. In industry setting, it’s common to see the following models in production:

XGBoost
Neural Network

Model Evaluation

Offline Metrics
- Mean Squared Error
- Mean Absolute Error
- Mean Absolute Percentage Error
Online Metrics
- Rides per User
- DAU
- Customer Reviews

Model Training

Unlock now by joining.