Abstract
Multi-objective search (MOS) is essential for finding Pareto-optimal paths in networks with conflicting goals, but it is often bottlenecked by computationally intensive dominance checks. This paper introduces two logical pruning techniques (R1 and R2) and a novel "bucket array" data structure to optimize these checks. Evaluated on real-world road networks, the combined approach (LTMOA*+R+Bucket) achieves up to a 10x speedup and a 95% reduction in vector comparisons compared to state-of-the-art baselines.
Introduction
Standard navigation algorithms typically optimize for a single metric, such as the fastest route. However, real-world scenarios often involve multiple conflicting objectives—time, distance, tolls, and fuel consumption. Multi-Objective Search (MOS) addresses this by finding the Pareto frontier, a set of solutions where no objective can be improved without sacrificing another. The primary computational bottleneck in MOS is the dominance check: determining if a newly discovered path is inferior to any previously found path across all objectives. As the number of objectives increases, these checks become the dominant factor in execution time.
Proposed Enhancements
The authors build upon the state-of-the-art LTMOA* algorithm, introducing three primary enhancements to streamline dominance checks:
- Dominance-Check Reduction (R1 & R2): These techniques utilize the search tree's logical structure to bypass redundant comparisons. R1 identifies that paths sharing the same parent node cannot dominate each other, allowing the algorithm to partition stored vectors and skip unnecessary checks. R2 avoids re-checking dominance against the goal state if the path's estimated total cost (f-value) has not changed since its parent was processed.
- Bucket Array Data Structure: To manage undominated vectors, the authors introduce a "bucket array" where each bucket corresponds to a specific range of costs. This structure allows for rapid pruning; if a bucket's entire range is inferior to the current path, all vectors within it can be ignored. Conversely, if a bucket's range is superior, dominance can often be confirmed without inspecting individual vectors.
Experimental Results
The techniques were evaluated using the New York road network benchmark from the 9th DIMACS Implementation Challenge, testing scenarios with 3, 4, and 5 objectives.
As shown in Table 1, the LTMOA*+R+Bucket configuration significantly outperforms the baseline and other data structures like ND-Trees. In 5-objective problems, the optimized version reduced the average number of operations from 19,078K to just 886K—a 95% reduction in computational workload.
The scatter plot in Figure 1 further illustrates the efficiency gains, with many problem instances approaching a 10x speedup. The optimized algorithm also demonstrated higher robustness, solving 28 instances within the 10-minute time limit for 5-objective sets, compared to 23 for the baseline.
Discussion and Conclusion
A key insight of this work is that the history of vector generation in a search tree provides "free" information that can simplify geometric dominance problems. While complex data structures like ND-trees are often favored for high-dimensional data, the simpler Bucket Array proved more effective for the 3–5 objective range typical of road networks due to lower maintenance overhead. Future work may explore dynamic bucket sizing to address the "curse of dimensionality" in many-objective scenarios.
Summary updated