Route travel time prediction in Yandex Traffic

Ilya Khokhlov4 Jun 2022

Problem

Users of a navigation service choose a route by its promised travel time, and a ride-hailing service uses the same forecast to price a trip and pick a driver. The forecast must hold for any start time, while the router that calls the model has strict response time limits. Quality is hard to measure because people leave the route early, in the middle or near the end. Without an online metric, the team once saw good offline numbers while a production bug surfaced only through user complaints.

Example from the article: the same route is fast at 7 AM with almost no traffic, but at 9 AM traffic builds up and the travel time roughly doubles.

Solution in brief

A gradient boosting model predicts the time of a fixed route from route-level features: graph properties, current and direction-specific traffic, and historical speeds. Quality is tracked as mean absolute percentage error (MAPE) offline and online, with route exits as a proxy metric. Most gains come from input preparation, not from the algorithm.

Questions this case answers
  • How to predict the duration of a trip along a chosen path from live and historical conditions under a hard per-request latency limit
  • How to evaluate a prediction when most users abandon the evaluated object before its end, using behavioral proxy metrics that agree between offline and online
  • How to predict how long a route will take, for any start time, within a router's response-time limit?
  • How to measure the quality of a travel time forecast when people rarely drive a route from start to finish?

Tools and methods

  • CatBoost — gradient boosting over trees; fast enough for the router's limits.
  • Historical speeds — per-edge averages by interval and day type, for rush hours and sparse regions.
  • Maneuver-specific traffic — traffic from vehicles going the same direction only.
  • MAPE — predicted versus actual time, offline and online.
  • Route exits — proxy metric for forecast quality.
Continue reading — it's free

Google or a one-time email code. No password.