This work addresses a Multi-Objective Shortest Path Problem (MO-SPP) on a
graph where the goal is to find a set of Pareto-optimal solutions from a start
node to a destination in the graph. A family of approaches based on MOA* have
been developed to solve MO-SPP in the literature. Typically, these approaches
maintain a "frontier" set at each node during the search process to keep track
of the non-dominated, partial paths to reach that node. This search process
becomes computationally expensive when the number of objectives increases as
the number of Pareto-optimal solutions becomes large. In this work, we
introduce a new method to efficiently maintain these frontiers for multiple
objectives by incrementally constructing balanced binary search trees within
the MOA* search framework. We first show that our approach correctly finds the
Pareto-optimal front, and then provide extensive simulation results for
problems with three, four and five objectives to show that our method runs
faster than existing techniques by up to an order of magnitude.

本文提出了在多目标最短路径问题中使用平衡二叉搜索树来维护非支配前沿集，以更高效地找到帕累托最优解的方法。实验表明，该方法在三、四、五个目标的问题中比现有技术快一个数量级。