Comparing Alternative Route Planning Techniques: A Web-based Demonstration and User Study

Lingxiao Li, Muhammad Aamir Cheema, Hua Lu, Mohammed Eunus Ali, Adel Nadjaran ToosiarXiv 2020 · arXiv

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:

  1. 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.
  2. 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.
  3. 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.
The Plateaus algorithm identifies common branches in shortest-path trees to construct alternative routes.

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.

The user study interface presenting four different routing approaches (A, B, C, and D) for evaluation in Melbourne.

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

Abstract

Many modern navigation systems and map-based services do not only provide the fastest route from a source location s to a target location t but also provide a few alternative routes to the users as more options to choose from. Consequently, computing alternative paths has received significant research attention. However, it is unclear which of the existing approaches generates alternative routes of better quality because the quality of these alternatives is mostly subjective. Motivated by this, in this paper, we present a user study conducted on the road networks of Melbourne, Dhaka and Copenhagen that compares the quality (as perceived by the users) of the alternative routes generated by four of the most popular existing approaches including the routes provided by Google Maps. We also present a web-based demo system that can be accessed using any internet-enabled device and allows users to see the alternative routes generated by the four approaches for any pair of selected source and target. We report the average ratings received by the four approaches and our statistical analysis shows that there is no credible evidence that the four approaches receive different ratings on average. We also discuss the limitations of this user study and recommend the readers to interpret these results with caution because certain factors may have affected the participants' ratings.
BibTeX
@misc{li2020comparing,
  author = {Lingxiao Li and Muhammad Aamir Cheema and Hua Lu and Mohammed Eunus Ali and Adel Nadjaran Toosi},
  title = {{Comparing Alternative Route Planning Techniques: A Web-based Demonstration and User Study}},
  year = {2020},
  eprint = {2006.08475},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2006.08475},
}
Figure