2020/06/18 by Oren Salzman, Salzman, Oren · 4 citations
Computer Science · Engineering · #Bayesian Modeling and Causal Inference #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2006.10302
openalex publication_date 2020/06/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the bi-criteria shortest-path problem where we want to compute\nshortest paths on a graph that simultaneously balance two cost functions. While\nthis problem has numerous applications, there is usually no path minimizing\nboth cost functions simultaneously. Thus, we typically consider the set of\npaths where no path is strictly better then the others in both cost functions,\na set called the Pareto-optimal frontier. Unfortunately, the size of this set\nmay be exponential in the number of graph vertices and the general problem is\nNP-hard. While existing schemes to approximate this set exist, they may be\nslower than exact approaches when applied to relatively small instances and\nrunning them on graphs with even a moderate number of nodes is often\nimpractical. The crux of the problem lies in how to efficiently approximate the\nPareto-optimal frontier. Our key insight is that the Pareto-optimal frontier\ncan be approximated using pairs of paths. This simple observation allows us to\nrun a best-first-search while efficiently and effectively pruning away\nintermediate solutions in order to obtain an approximation of the Pareto\nfrontier for any given approximation factor. We compared our approach with an\nadaptation of BOA*, the state-of-the-art algorithm for computing exact\nsolutions to the bi-criteria shortest-path problem. Our experiments show that\nas the problem becomes harder, the speedup obtained becomes more pronounced.\nSpecifically, on large roadmaps, we obtain an average speedup of more than\n\× 8.5 and a maximal speedup of over \× 148.\n