Projects per year
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 bidirectional 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.
Original language | English |
---|---|
Title of host publication | 29th Annual European Symposium on Algorithms, ESA 2021 |
Editors | Petra Mutzel, Rasmus Pagh, Grzegorz Herman |
Place of Publication | Saarbrücken/Wadern Germany |
Publisher | Schloss Dagstuhl |
Number of pages | 15 |
ISBN (Electronic) | 9783959772044 |
DOIs | |
Publication status | Published - 2021 |
Event | Annual European Symposium on Algorithms 2021 - Online, Lisbon, Portugal Duration: 6 Sept 2021 → 8 Sept 2021 Conference number: 29th http://chrome-extension://efaidnbmnnnibpcajpcglclefindmkaj/https://drops.dagstuhl.de/opus/volltexte/2021/14581/pdf/LIPIcs-ESA-2021-0.pdf (Proceedings) http://algo2021.tecnico.ulisboa.pt/ESA2021/ (Website) |
Publication series
Name | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Publisher | Schloss Dagstuhl |
Volume | 204 |
ISSN (Print) | 1868-8969 |
Conference
Conference | Annual European Symposium on Algorithms 2021 |
---|---|
Abbreviated title | ESA 2021 |
Country/Territory | Portugal |
City | Lisbon |
Period | 6/09/21 → 8/09/21 |
Internet address |
Keywords
- Bi-objective search
- Heuristic search
- Shortest path problem
Projects
- 2 Finished
-
Improved Constraint Reasoning for Robust Multi-agent Path Planning
Stuckey, P., Harabor, D., Le Bodic, P., Gange, G. & Koenig, S.
1/01/20 → 31/12/24
Project: Research
-
Personalised Public Transport
Harabor, D., Moser, I. & Ronald, N.
24/06/19 → 31/12/24
Project: Research