Design an ETA Prediction System
Design a system to predict estimated time of arrival for a maps/navigation application.
Requirements
Functional:
- Predict travel time between two points
- Support driving, walking, transit
- Update ETA during trip
- Handle different traffic conditions
Non-functional:
- Prediction latency < 100ms
- Handle millions of requests/minute
- Accuracy within 10% of actual time
Metrics
| Metric | Description |
|---|---|
| MAPE | Mean Absolute Percentage Error |
| MAE | Mean Absolute Error (minutes) |
| % within X% | Predictions within X% of actual |
Architecture
Loading diagram...
Features
| Category | Features |
|---|---|
| Route | Distance, number of turns, road types, traffic signals, intersections |
| Traffic | Current speed on segments, historical speed by time, real-time incidents, events, weather |
| Context | Time of day, day of week, holidays, special events |
Model
Segment-Level Prediction
Loading diagram...
| Component | Input | Output |
|---|---|---|
| Base Time | Segment distance, speed limit | Time in ideal conditions |
| Traffic Factor | Segment ID, current speed, time of day | Multiplier (0.5 to 3.0) |
| Final Prediction | Base time, traffic factor | Adjusted segment ETA |
Graph Neural Network Approach
Model road network as graph, propagate traffic information:
Loading diagram...
| Layer | Purpose | Output |
|---|---|---|
| Input | Segment features | Road characteristics |
| GCN Conv 1 | Aggregate neighbor info | 64-dim embeddings |
| GCN Conv 2 | Higher-order patterns | 32-dim embeddings |
| Predictor | Speed prediction | Predicted speed per segment |
Real-Time Updates
During trip, the system continuously refines predictions:
Loading diagram...
| Step | Calculation | Purpose |
|---|---|---|
| 1. Track progress | Compare actual position to route | Know completed segments |
| 2. Calculate correction | Actual time / Predicted time | Learn from real performance |
| 3. Apply to remaining | Remaining ETA x Correction factor | Adjust future predictions |
| 4. Incorporate new data | Fresh traffic data for remaining route | Account for changing conditions |
Reference
| Topic | Description |
|---|---|
| Sparse data | Most roads have no traffic sensors. Infer from GPS traces of drivers on those routes. |
| Incidents | Accidents change predictions significantly. Detect and incorporate quickly through real-time data. |
| Events | Stadium emptying creates surge traffic. Model known events separately. |
| Route changes | User deviates from suggested route. Recalculate remaining ETA based on new path. |