Bi-objective search with Bi-directional A*

Saman Ahmadi, Guido Tack, Daniel Harabor, Philip Kilby

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

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 languageEnglish
Title of host publication29th Annual European Symposium on Algorithms, ESA 2021
EditorsPetra Mutzel, Rasmus Pagh, Grzegorz Herman
PublisherSchloss Dagstuhl
Number of pages15
ISBN (Electronic)9783959772044
ISBN (Print)Saarbrücken/Wadern Germany
DOIs
Publication statusPublished - 2021
EventAnnual European Symposium on Algorithms 2021 - Online, Lisbon, Portugal
Duration: 6 Sep 20218 Sep 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

NameLeibniz International Proceedings in Informatics, LIPIcs
PublisherSchloss Dagstuhl
Volume204
ISSN (Print)1868-8969

Conference

ConferenceAnnual European Symposium on Algorithms 2021
Abbreviated titleESA 2021
Country/TerritoryPortugal
CityLisbon
Period6/09/218/09/21
Internet address

Keywords

  • Bi-objective search
  • Heuristic search
  • Shortest path problem

Cite this