Introduction
Modern navigation systems rarely provide a single path; instead, they offer a set of "alternatives." While finding the shortest path is a well-solved mathematical problem, defining what constitutes a "good" alternative is inherently subjective. A high-quality alternative must be meaningful, avoid excessive detours, and be sufficiently distinct from the primary route. Over the last decade, several algorithms—Penalty, Plateaus, and Dissimilarity—have been proposed to solve this problem. However, evaluations have historically relied on objective metrics like length or overlap rather than human preference. This study presents the first systematic user evaluation comparing these research algorithms against the industry standard, Google Maps.
Methodology
The researchers developed a web-based demonstration system using road network data from OpenStreetMap (OSM). The study implemented three prominent research algorithms:
- Penalty: This method iteratively finds the shortest path and then "penalizes" the used edges by increasing their cost, forcing the next iteration to find a different route.
- Plateaus: This technique generates shortest-path trees from both the source and destination. It identifies "plateaus"—common branches shared by both trees—to construct alternative routes.
- Dissimilarity (SSVP-D+): This approach uses "via-nodes" to create paths, adding them to the result set only if they meet a specific threshold of difference from existing paths.
These algorithms were benchmarked against Google Maps. To ensure a fair comparison, Google routes were retrieved at 2:00 AM to minimize the impact of real-time traffic data, which is unavailable to the OSM-based algorithms. The study was conducted across three diverse urban environments: Melbourne (planned grid), Dhaka (high-density/complex), and Copenhagen (cycling-centric). A total of 520 participants provided ratings on a 1–5 scale.
Key Insights and Results
Statistical Parity with Industry Standards
One of the most significant findings was that the differences in mean ratings between Google Maps and the three research algorithms were not statistically significant ($p > 0.05$). On a 5-point scale, all four approaches achieved mean ratings between 3.4 and 3.5. This suggests that open-source algorithms can produce route quality comparable to proprietary, data-rich commercial systems.
The Subjectivity of Navigation
User perception varied based on local knowledge and route length. Google Maps consistently received higher ratings from residents than non-residents, likely because its routes align with local traffic patterns that residents find familiar. Interestingly, the Penalty method often outperformed others for short routes (under 10 minutes), while the Plateaus method was favored for longer routes (over 25 minutes).
Diversity vs. Quality
The Dissimilarity algorithm was the most successful at providing truly distinct routes, with an average overlap of only 24%. However, the study revealed a trade-off: highly diverse routes are sometimes perceived as unnecessary detours by users, even if they are mathematically valid alternatives.
Conclusion and Future Work
The study demonstrates that for developers building navigation tools, publicly available research algorithms are a highly viable alternative to expensive commercial APIs. However, users noted a preference for heuristics not yet fully captured by these algorithms, such as prioritizing wider roads or minimizing the number of turns. Future research will focus on integrating real-time traffic data and these human-centric heuristics into the Penalty, Plateaus, and Dissimilarity frameworks to further bridge the gap between research and commercial application.
Summary updated