License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2021.3
URN: urn:nbn:de:0030-drops-145849
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14584/
Ahmadi, Saman ;
Tack, Guido ;
Harabor, Daniel ;
Kilby, Philip
Bi-Objective Search with Bi-Directional A*
Abstract
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.
BibTeX - Entry
@InProceedings{ahmadi_et_al:LIPIcs.ESA.2021.3,
author = {Ahmadi, Saman and Tack, Guido and Harabor, Daniel and Kilby, Philip},
title = {{Bi-Objective Search with Bi-Directional A*}},
booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)},
pages = {3:1--3:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-204-4},
ISSN = {1868-8969},
year = {2021},
volume = {204},
editor = {Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14584},
URN = {urn:nbn:de:0030-drops-145849},
doi = {10.4230/LIPIcs.ESA.2021.3},
annote = {Keywords: Bi-objective search, heuristic search, shortest path problem}
}
Keywords: |
|
Bi-objective search, heuristic search, shortest path problem |
Collection: |
|
29th Annual European Symposium on Algorithms (ESA 2021) |
Issue Date: |
|
2021 |
Date of publication: |
|
31.08.2021 |