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

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.

To appear in the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA) 2025. Code and data for the experiments can be found here: https://github.com/google-research/google-research/blob/master/explainable_routing