2025/11/13 by Shahaf Shperberg, Shperberg, Shahaf S., Morad, Natalie +6
Computer Science · Engineering · #Artificial Intelligence (cs.AI) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.2511.10272
openalex publication_date 2025/11/13 · openalex created_date 2025/11/15 · openalex updated_date 2026/07/28
Recent advancements in bidirectional heuristic search have yielded significant theoretical insights and novel algorithms. While most previous work has concentrated on optimal search methods, this paper focuses on bounded-suboptimal bidirectional search, where a bound on the suboptimality of the solution cost is specified. We build upon the state-of-the-art optimal bidirectional search algorithm, BAE*, designed for consistent heuristics, and introduce several variants of BAE* specifically tailored for the bounded-suboptimal context. Through experimental evaluation, we compare the performance of these new variants against other bounded-suboptimal bidirectional algorithms as well as the standard weighted A* algorithm. Our results demonstrate that each algorithm excels under distinct conditions, highlighting the strengths and weaknesses of each approach.