How we created HOV-specific ETAs in Google Maps

The shift to sustainable travel modes like electric vehicles (EVs), carpooling, and public transit, has made travel times more varied. This is largely due to the availability of dedicated lanes, such as carpool lanes, also called high-occupancy vehicle (HOV) lanes, which are reserved for vehicles with multiple passengers and are designed to move traffic more efficiently during peak hours. As a result, HOV lanes are typically faster than general lanes during rush hour. For example, in Utah’s Salt Lake Valley, the average speed in HOV lanes was recorded at 68.18 mph compared to 58.60 mph in general lanes, a difference of about 16%.

Accurate estimated time of arrival (ETA) predictions and optimized routing are key to improving the commuting experience. With precise ETAs, travelers can make better decisions, save time, and even contribute to reducing congestion and emissions. With this in mind, Google Maps recently introduced a feature that lets drivers select routes that include HOV lanes and see that route’s ETA. In this blog post, we explain how we developed this feature and developed a classification system to determine HOV trips from non-HOV trips, which led to the launch of HOV specific ETAs in Google Maps.

Developing HOV-specific ETAs

To estimate HOV travel times, we first infer past HOV travel times by analyzing aggregated and anonymized traffic trends. We then use these inferred times to train our ETA prediction models specifically for HOV lanes.

However, identifying HOV trips isn't straightforward. Simple data, like speed, can be similar for both HOV and non-HOV users, especially when traffic is light. Yet HOV travel patterns also have several distinct and useful constraints, including limitations on availability based on location, time of day, and exceptional events.

To address these issues, we develop an unsupervised learning approach, performing a classification without initial labels (HOV vs. non-HOV). We perform a classification task of the trip parts lying on individual road segments that have HOV availability. The overall trip classification is then determined by combining these segment-level classifications.

Segment-level classification

For each individual segment, we process a collection of trip parts from different trips that lie on this segment in a short window of time, e.g., 15 minutes. Our goal is to classify these trip parts using the information from both the trip itself and also the other trips that happened in the same window of time. Each trip is composed of several observations, or “trip points”, recorded during the travel time. These points include information such as speed, lateral distance from center of the road, and the time of the observation.

The most prominent feature in this classification is the speed information. In fact, our classification task is more valuable when travel times on HOV lanes differ from general lanes. In such scenarios, we often observe a bimodal speed distribution, two distinct traffic patterns emerging at the same time. For example, in the figure below, anonymized aggregated speed data collected between 4:00 to 4:30 pm on Seattle’s I5 shows this clearly, with faster speeds likely corresponding to vehicles using HOV lanes. We call this Scenario A.

By analyzing speed data, we can differentiate between HOV and non-HOV travelers when their travel times show a significant difference. However it is possible that there is a noticeable difference between travel times but it is not necessarily significant. For example, the following plot shows the speed distribution for the same segment during peak hours but when the HOV is traveling just a bit faster. We call this Scenario B.

Beyond speed: Incorporating estimated lateral distance

While speed is a strong signal, we also explored other factors to improve classification. Estimated lateral distance to the center of the road, though inherently noisy due to the inherent imprecision of GPS, turned out to be useful when combined with speed. In fact, even with some imprecision, distance information helps highlight lane-specific behaviors, especially when distinguishing from adjacent general lanes.

The two figures below illustrate the two speed distributions discussed previously. They depict anonymized rush-hour traffic data in the Seattle metro area on a highway segment with five lanes, where the two HOV lanes are located on the left. Speed and estimated relative distance to the center of the road from this segment are shown, with data points color-coded green and blue to indicate whether they fall within an HOV lane. The first figure highlights data in Scenario A where HOV lanes experience significantly higher speeds compared to general lanes, with average speeds of 65 mph versus 25 mph.

The second figure highlights the same data collected during the time that the the difference in speed is less (Scenario B) with average speeds of 67 mph versus 55 mph.

Temporal clustering and soft assignments

As the figure above suggests, clustering can be an effective method for generating initial labels for these observations. However our approach goes beyond basic clustering by incorporating an additional dimension: time. When classifying a trip observation, the timing of other observations plays a significant role. While it is important to have enough data within each time interval for statistical reliability, we also prioritize more recent data points during processing. Therefore, we use weighted median approaches that account for the timing of events.

Another factor that helps our classification is a shift toward soft clustering techniques. Rather than assigning each data point definitively to a single cluster (HOV or non-HOV), we calculate the probability of each point belonging to each cluster. This is especially helpful for borderline data points. Soft clustering also gives us more flexibility when aggregating these classifications to make a final determination for the entire trip.

Final aggregation and classification

A trip spans multiple road segments, and we classify each trip by aggregating classification outcomes from each segment. Special attention is given to segments that fall within HOV-eligible stretches of the road. We compute the proportion of the trip that was likely spent in HOV lanes and use this as a key factor in the final classification.

To further refine our results, we implement a mixture of experts (MoE) approach. This framework uses multiple classifiers, each with different parameter settings for segment-level classification models. The final trip classification is then determined through a majority voting mechanism across these classifiers, resulting in more reliable outcomes.

Evaluation

To evaluate our ETA accuracy, we conducted a series of experiments comparing the ETA calculated using our new HOV-based estimates with that of our legacy system. We partitioned trips across road stretches of varying lengths and analyzed the distribution of travel times for each stretch.

For each stretch, we modeled the bimodal distribution of trips’ travel times using two normal distributions — one representing general lane travel and the other representing HOV-lane travel. Based on this, we computed the z-score for each trip to assess how closely it aligned with either distribution. This allowed us to confidently label trips as either HOV or not when their z-scores fell within high-certainty thresholds. We then evaluated our algorithm’s performance against these high-confidence labels.

Results

We now present HOV-specific ETAs. With the launch of this feature, we've improved overall ETA accuracy for drivers using this feature by 75%, making our accuracy metrics for HOV users comparable to those of drivers taking routes without HOV lanes. Our final classification method yielded an 18% improvement in ETA accuracy over the initial method, which only compares travel speeds.

Conclusion

By analyzing lane placement with speed analysis and applying a mixture-of-experts approach to trip classification, we developed a powerful method to address the scarcity of labeled HOV data. This framework offers a novel way to interpret dynamic traffic conditions and address key challenges in traffic modeling. Beyond HOV travel, similar principles can be extended to other transportation modes exhibiting similar usage patterns. For instance, in regions with significant two-wheeled traffic, these concepts could also be applicable to two-wheeled travelers.

We believe this approach holds strong potential for advancing the field of traffic data analysis and has practical implications for enhancing real-world applications such as Google Maps. By improving the accuracy and efficiency of HOV lane utilization, our model could help users plan more efficient routes, reduce travel times, and contribute to smarter, greener commuting.

Acknowledgements

These technological advances were enabled by the tireless work of our collaborators in Google Maps: Daniel Delling, Amruta Gulanikar, Cameron Jones, Oliver Lange, Ramesh Namburi, Pooja Patel, Lorenzo Prelli, Stella Stylianidou, and Qian Zheng. Special thanks to Corinna Cortes, Sreenivas Gollapudi, Ravi Kumar, and Andrew Tomkins for their support during this project. We thank Cameron Jones, Sreenivas Gollapudi, and Ravi Kumar for their valuable contribution to this blog post.