Architecture Design

Data Preparation

Model Serving

Model Training

Requirement Gathering

Pay Range on Glassdoor

Predict Trip ETA on Uber

ML System Design

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).



<figure class="wp-block-image"><img decoding="async" src="https://files.cdn.thinkific.com/file_uploads/481328/images/f0f/3f0/e10/Screen_Shot_2023-07-01_at_4.35.32_PM.png" alt=""/></figure>



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.



<figure class="wp-block-image"><img decoding="async" src="https://files.cdn.thinkific.com/file_uploads/481328/images/cb1/533/2e5/Screen_Shot_2023-07-01_at_4.35.53_PM.png" alt=""/></figure>



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:



<ul class="wp-block-list">
<li>XGBoost</li>



<li>Neural Network</li>
</ul>



Model Evaluation



<ul class="wp-block-list">
<li>Offline Metrics
<ul class="wp-block-list">
<li>Mean Squared Error</li>



<li>Mean Absolute Error</li>



<li>Mean Absolute Percentage Error</li>
</ul>
</li>



<li>Online Metrics
<ul class="wp-block-list">
<li>Rides per User</li>



<li>DAU</li>



<li>Customer Reviews</li>
</ul>
</li>
</ul>

Model Training

Join now to continue learning