Why is My Route Different Today? An Algorithm for Explaining Route Selection

Aaron Schild, Sreenivas Gollapudi, Anupam Gupta, Kostas Kollias, Ali Kemal Sinop

Introduction

Every driver has experienced the frustration of a navigation app suggesting a counterintuitive detour through residential streets or a convoluted highway bypass. While these routing engines are highly effective at optimizing for travel time, they typically operate as "black boxes." They provide the what (the new route) but rarely the why (the specific traffic conditions necessitating the change).

Simply listing every traffic incident in a metropolitan area is overwhelming for a user, and showing traffic only on the suggested path fails to explain why the original, more familiar route was rejected. This research, a collaboration between Google and NYU, addresses the "identification problem": finding the smallest, most relevant set of traffic conditions that justify a specific route recommendation. The authors introduce a framework for generating Simple Valid Explanations (SVEs) to make these detours human-interpretable.

The Framework: Simple Valid Explanations

To formalize the problem, the researchers modeled the road network as a directed graph where each edge (road segment) possesses two distinct weights: a "free-flow" time (representing the speed limit or ideal conditions) and a "current" time (incorporating real-time traffic data).

An SVE is defined as a subset of road segments that, when their traffic-heavy weights are maintained while all other segments are reset to free-flow, still results in the suggested detour being the shortest path. To ensure these explanations are useful to humans, the algorithm seeks the most "simple" explanation—defined as the smallest possible subset of segments. This approach applies Occam’s Razor to navigation: the best explanation is the one that uses the fewest moving parts to justify the detour.

Algorithmic Innovation

Finding the absolute minimum set of segments for an SVE is computationally expensive and categorized as an NP-hard problem, closely related to "shortest path interdiction." To make this viable for real-time applications, the authors developed a sophisticated multi-step approach:

  1. Linear Programming (LP) Relaxation: They first formulated the problem as an LP relaxation to find an approximate solution efficiently.
  2. Combinatorial Flow-Based Algorithm: To surpass the speed of off-the-shelf LP solvers, the team created a novel combinatorial algorithm. This approach leverages the specific structure of road networks to find valid explanations significantly faster.
  3. Performance at Scale: By utilizing subgraphs and optimized data structures, the algorithm can generate an explanation in approximately 50 milliseconds on standard consumer hardware (e.g., an Apple M1 Pro). This level of efficiency is critical for "continent-scale" routing engines that must serve millions of queries simultaneously.

Experimental Validation

The researchers evaluated the SVE algorithm using extensive real-world data from OpenStreetMap (OSM), focusing on two major regions:

  • Baden-Württemberg, Germany: 6.4 million nodes and 13.5 million arcs.
  • Washington State, USA: 7.4 million nodes and 15.4 million arcs.

They tested the algorithm across short (1–3 miles), medium (5–20 miles), and long-distance (80–120 miles) queries, simulating both total road closures and general traffic congestion.

Key Results

  • Succinctness: In scenarios involving general traffic incidents, the SVEs were remarkably concise. The median size of an SVE was only 10% of the total traffic-impacted segments in the test scenario. This demonstrates that most traffic data is "noise" relative to a specific detour; only a few pivotal segments actually drive the routing decision.
  • Accuracy: In 100% of the test cases involving road closures in the Seattle area, the SVE perfectly identified the specific closed segments as the sole reason for the route change.
  • Robustness: The authors compared SVEs to "Penalty-Based Explanations" (PBEs), which repeatedly penalize the shortest path until it matches the suggested route. They found that PBEs are often "brittle," including irrelevant segments, whereas SVEs consistently identified the most stable and relevant causes.

Conclusion and Future Work

This research provides a robust mathematical and algorithmic foundation for making automated routing decisions transparent. By identifying the minimal set of conditions that force a detour, the SVE framework bridges the gap between complex optimization and human understanding.

While the paper focuses on the identification of these segments, the authors note that the next step is presentation. These identified segments could be integrated into Large Language Models (LLMs) via Retrieval-Augmented Generation (RAG) to provide natural language explanations, such as: "We're taking the side streets because a major accident on I-5 has increased your usual commute by 20 minutes."

Future iterations of this work may expand to include time-dependent graphs—accounting for how traffic changes over the duration of a long trip—and explaining routes optimized for non-temporal factors like fuel efficiency or scenic value.

Summary updated

Abstract

Users of routing services like Apple Maps, Google Maps, and Waze frequently wonder why a given route is proposed. This question particularly arises when dynamic conditions like traffic and road closures cause unusual routes to be proposed. While many dynamic conditions may exist in a road network at any time, only a small fraction of those conditions are typically relevant to a given user's route. In this work, we introduce the concept of a simple valid explanation (SVE), which consists of a small set of traffic-laden road segments that answer the following question: Which traffic conditions cause a particular shortest traffic-aware route to differ from the shortest traffic-free route? We give an efficient algorithm for finding SVEs and show that they theoretically and experimentally lead to small and interpretable answers to the question.
BibTeX
@inproceedings{schild2025why,
  author = {Aaron Schild and Sreenivas Gollapudi and Anupam Gupta and Kostas Kollias and Ali Kemal Sinop},
  title = {{Why is My Route Different Today? An Algorithm for Explaining Route Selection}},
  booktitle = {ACDA},
  year = {2025},
  doi = {10.1137/1.9781611978759.19},
}
Figure