2026-08-07T00:08:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14584 2024-03-06T10:54:22Z ddc:004 open_access

Bi-Objective Search with Bi-Directional A* Ahmadi, Saman Tack, Guido Harabor, Daniel Kilby, Philip Bi-objective search heuristic search shortest path problem Bi-objective search is a well-known algorithmic problem, concerned with finding a set of optimal solutions in a two-dimensional domain. This problem has a wide variety of applications such as planning in transport systems or optimal control in energy systems. Recently, bi-objective A*-based search (BOA*) has shown state-of-the-art performance in large networks. This paper develops a bi-directional and parallel variant of BOA*, enriched with several speed-up heuristics. Our experimental results on 1,000 benchmark cases show that our bi-directional A* algorithm for bi-objective search (BOBA*) can optimally solve all of the benchmark cases within the time limit, outperforming the state of the art BOA*, bi-objective Dijkstra and bi-directional bi-objective Dijkstra by an average runtime improvement of a factor of five over all of the benchmark instances. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Saman Ahmadi and Guido Tack and Daniel Harabor and Philip Kilby 2021 Is Part Of LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2021.3 urn:nbn:de:0030-drops-145849 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.3 eng https://creativecommons.org/licenses/by/4.0/legalcode