Yaron Halle, Ariel Felner, Sven Koenig, Oren Salzman

A Preprocessing Framework for Efficient Approximate Bi-Objective Shortest-Path Computation in the Presence of Correlated Objectives

Introduction

A preprocessing framework for efficient approximate bi-objective shortest-path computation in the presence of correlated objectives. Efficiently compute approximate bi-objective shortest paths in correlated objective scenarios like road networks. This preprocessing framework speeds up A*pex by 5x on DIMACS, leveraging correlations for faster, guaranteed solutions.

Abstract

The bi-objective shortest-path (BOSP) problem seeks to find paths between start and target vertices of a graph while optimizing two conflicting objective functions. We consider the BOSP problem in the presence of correlated objectives. Such correlations often occur in real-world settings such as road networks, where optimizing two positively correlated objectives, such as travel time and fuel consumption, is common. BOSP is generally computationally challenging as the size of the search space is exponential in the number of objective functions and the graph size. Bounded sub-optimal BOSP solvers such as A*pex alleviate this complexity by approximating the Pareto-optimal solution set rather than computing it exactly (given a user-provided approximation factor). As the correlation between objective functions increases, smaller approximation factors are sufficient for collapsing the entire Pareto-optimal set into a single solution. We leverage this insight to propose an efficient algorithm that reduces the search effort in the presence of correlated objectives. Our approach for computing approximations of the entire Pareto-optimal set is inspired by graph-clustering algorithms. It uses a preprocessing phase to identify correlated clusters within a graph and to generate a new graph representation. This allows a natural generalization of A*pex to run up to five times faster on DIMACS dataset instances, a standard benchmark in the field. To the best of our knowledge, this is the first algorithm proposed that efficiently and effectively exploits correlations in the context of bi-objective search while providing theoretical guarantees on solution quality.

Review

The paper presents a valuable contribution to the field of multi-objective optimization by addressing the bi-objective shortest-path (BOSP) problem, specifically in contexts where the objective functions are correlated. This focus on correlated objectives, such as travel time and fuel consumption in road networks, is highly relevant to real-world applications where traditional BOSP solutions are computationally prohibitive due to their exponential search space. The authors build their work on the insightful observation that increasing correlation between objectives can simplify the Pareto-optimal set, potentially allowing for smaller approximation factors to achieve a desired solution quality. To leverage this insight, the proposed methodology introduces an innovative preprocessing framework. This framework, inspired by graph-clustering algorithms, first identifies "correlated clusters" within the graph during a preprocessing phase. Subsequently, it generates a new graph representation that intrinsically captures these correlations. This restructured representation is designed to facilitate more efficient computations for approximate BOSP solvers. The authors demonstrate how this preprocessing allows for a natural generalization of existing bounded sub-optimal solvers, exemplified by A*pex, to operate with significantly reduced computational overhead by effectively narrowing the search space. The efficacy of the framework is validated through experimental results on standard DIMACS dataset instances, where the approach achieves up to a five-fold speed improvement. A particularly strong aspect of this work is the claim of providing theoretical guarantees on solution quality, which is paramount for approximate algorithms. The paper positions itself as a novel and pioneering effort, asserting it to be the first algorithm that efficiently and effectively exploits objective correlations in bi-objective search while simultaneously offering such robust theoretical assurances. This robust combination of practical performance gains and theoretical soundness marks a significant advancement for tackling complex BOSP problems in correlated real-world scenarios.

Full Text

Comments

You need to be logged in to post a comment.