The global shift towards sustainable transportation, including electric vehicles, carpooling, and public transit, has introduced greater variability in travel times. This variation is primarily driven by the availability of dedicated lanes, such as High-Occupancy Vehicle (HOV) lanes. These lanes, designed for vehicles with multiple passengers, expedite traffic flow during peak hours and are consistently faster than general traffic. For instance, Utah’s Salt Lake Valley recorded average HOV lane speeds of 68.18 mph compared to 58.60 mph in general lanes, a 16% difference.
Accurate Estimated Time of Arrival (ETA) predictions and optimized routing are paramount for improving the commuter experience. Precise ETAs empower travelers to make informed decisions, save valuable time, and actively contribute to reducing traffic congestion and emissions. Recognizing this need, Google Maps recently launched a feature enabling drivers to select routes incorporating HOV lanes and view their corresponding ETAs. This article details our development process for this feature, including the creation of a classification system to distinguish HOV from non-HOV trips, which powered the introduction of HOV-specific ETAs in Google Maps.
HOV-aware route options in Google Maps.
Develop HOV-Specific ETAs
To accurately predict HOV travel times, we first infer historical HOV travel durations by analyzing aggregated, anonymized traffic trends. We then leverage these inferred times to train our ETA prediction models specifically for HOV lanes. Identifying HOV trips presents a challenge; simple metrics like speed may be similar for both HOV and non-HOV users in light traffic. However, HOV travel patterns exhibit distinct constraints, including availability based on location, time of day, and special events.
To overcome these obstacles, we developed an unsupervised learning approach, classifying trips without pre-existing labels (HOV vs. non-HOV). We classify trip segments that traverse roads with HOV availability. The overall trip classification emerges from combining these segment-level classifications.
Classify Road Segments Effectively
For each road segment, we process a collection of trip segments from various trips that utilize it within a short timeframe, such as 15 minutes. Our objective is to classify these trip segments using data from both the trip itself and other concurrent trips. Each trip comprises multiple observations, or “trip points,” recorded during travel, including speed, lateral distance from the road center, and observation timestamps.
Speed information stands out as the most critical feature for this classification. Our classification task becomes significantly valuable when HOV lane travel times diverge from general lanes. In such cases, we often observe a bimodal speed distribution, indicating two distinct traffic patterns coexisting. For example, anonymized, aggregated speed data from Seattle’s I5 between 4:00 PM and 4:30 PM clearly illustrates this, with higher speeds likely corresponding to HOV lane usage. We designate this as Scenario A.
Scenario A: Speed distribution on a segment with HOV availability during peak hours, showing significantly faster HOV speeds than general lanes.
By analyzing speed data, we effectively differentiate between HOV and non-HOV travelers when their travel times exhibit a substantial difference. However, notable differences in travel times are not always significant. For example, the following plot displays the speed distribution for the same segment during peak hours, where HOV travel is only slightly faster. We label this Scenario B.
Scenario B: Speed distribution on a segment with HOV availability during peak hours, showing HOV speeds faster than general lanes, but not significantly so.
Incorporate Lateral Distance for Enhanced Classification
While speed proves a robust indicator, we explored additional factors to refine our classification accuracy. Estimated lateral distance to the road center, despite inherent GPS noise, proved valuable when analyzed alongside speed data. This distance information effectively highlights lane-specific behaviors, particularly when distinguishing from adjacent general lanes.
The subsequent figures illustrate the two speed distributions previously discussed. They present anonymized rush-hour traffic data from a five-lane highway segment in the Seattle metro area, where the two HOV lanes occupy the left positions. The figures display speed and estimated relative distance to the road center, with data points color-coded green and blue to denote HOV lane usage. The first figure exemplifies Scenario A, where HOV lanes exhibit significantly higher speeds (average 65 mph) compared to general lanes (average 25 mph).
Scenario A — Left: Recorded speed versus lateral distance from the road center for anonymized trips on an individual segment. Right: Speed distribution, separated by HOV lane occupancy.
The second figure presents data from Scenario B, where the speed difference is less pronounced, with average speeds of 67 mph in HOV lanes versus 55 mph in general lanes.
Scenario B — Left: Recorded speed versus lateral distance from the road center for anonymized trips on an individual segment. Right: Speed distribution, separated by HOV lane occupancy.
Employ Temporal Clustering and Soft Assignments
As depicted, clustering effectively generates initial labels for observations. However, our methodology extends beyond basic clustering by incorporating time as a crucial dimension. The timing of other observations significantly influences the classification of a trip. While sufficient data within each time interval ensures statistical reliability, we prioritize more recent data points during processing. Consequently, we employ weighted median approaches that account for event timing.
Furthermore, our approach embraces soft clustering techniques. Instead of 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 proves particularly beneficial for ambiguous data points. Soft clustering also enhances flexibility when aggregating classifications for final trip determinations.
Aggregate and Classify Trips Precisely
A trip traverses multiple road segments; we classify each trip by aggregating the classification outcomes from every segment. Segments within HOV-eligible zones receive special consideration. We calculate the proportion of the trip likely spent in HOV lanes, utilizing this as a primary factor for the final classification.
To further refine our results, we implemented a mixture of experts (MoE) framework. This system employs multiple classifiers, each configured with distinct parameter settings for segment-level classification models. The final trip classification is then determined through a majority voting process across these classifiers, ensuring highly reliable outcomes.
Evaluate ETA Accuracy Rigorously
We conducted a series of experiments to evaluate our ETA accuracy, comparing ETAs calculated with our new HOV-based estimates against our legacy system. We partitioned trips across road stretches of varying lengths and analyzed the distribution of travel times for each. For each stretch, we modeled the bimodal distribution of trip travel times using two normal distributions: one for general lane travel and another for HOV lane travel. We then computed the z-score for each trip to assess its alignment with these distributions. This enabled confident labeling of trips as HOV or non-HOV based on high-certainty thresholds for z-scores. Our algorithm’s performance was subsequently evaluated against these high-confidence labels.
Achieve Superior Results
We are proud to deliver HOV-specific ETAs. This feature significantly improves overall ETA accuracy for drivers using it by 75%, matching the accuracy metrics of drivers using routes without HOV lanes. Our refined classification method achieved an 18% improvement in ETA accuracy compared to the initial speed-comparison-only method.
Conclusion
By combining lane placement analysis with speed metrics and employing a mixture-of-experts approach for trip classification, we developed a robust solution to address the scarcity of labeled HOV data. This framework offers an innovative method for interpreting dynamic traffic conditions and tackling key challenges in traffic modeling. Beyond HOV travel, these principles can extend to other transportation modes with similar usage patterns; for instance, in regions with substantial two-wheeled traffic, these concepts are applicable to two-wheeled vehicle travelers.
We are confident this approach significantly advances traffic data analysis and offers practical benefits for real-world applications like Google Maps. By enhancing the accuracy and efficiency of HOV lane utilization, our model empowers users to plan more efficient routes, reduce travel times, and contribute to smarter, greener commutes.
Acknowledgements
These technological advancements stem from the dedicated efforts of our Google Maps collaborators: Daniel Delling, Amruta Gulanikar, Cameron Jones, Oliver Lange, Ramesh Namburi, Pooja Patel, Lorenzo Prelli, Stella Stylianidou, and Qian Zheng. We extend special gratitude to Corinna Cortes, Sreenivas Gollapudi, Ravi Kumar, and Andrew Tomkins for their invaluable support throughout this project. We also thank Cameron Jones, Sreenivas Gollapudi, and Ravi Kumar for their significant contributions to this blog post.