Document Open Access Logo

Bi-Objective Search with Bi-Directional A*

Authors Saman Ahmadi , Guido Tack, Daniel Harabor, Philip Kilby

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2021.3.pdf
  • Filesize: 1.25 MB
  • 15 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Computing methodologies → Search methodologies
  • Theory of computation → Shortest paths
Keywords
  • Bi-objective search
  • heuristic search
  • shortest path problem

Metrics

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.

Cite As Get BibTex

Saman Ahmadi, Guido Tack, Daniel Harabor, and Philip Kilby. Bi-Objective Search with Bi-Directional A*. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.ESA.2021.3

Author Details

Saman Ahmadi
  • Department of Data Science and AI, Monash University, Clayton, Australia
  • CSIRO Data61, Canberra, Australia
Guido Tack
  • Department of Data Science and AI, Monash University, Clayton, Australia
Daniel Harabor
  • Department of Data Science and AI, Monash University, Clayton, Australia
Philip Kilby
  • CSIRO Data61, Canberra, Australia

Funding

Research at Monash University is supported by the Australian Research Council (ARC) under grant numbers DP190100013 and DP200100025 as well as a gift from Amazon.

References

  1. W. Matthew Carlyle and R. Kevin Wood. Near-shortest and k-shortest simple paths. Networks, 46(2):98-109, 2005. URL: https://doi.org/10.1002/net.20077.
  2. Kalyanmoy Deb. Multi-objective optimization. In Search methodologies, pages 403-449. Springer, 2014. Google Scholar
  3. Eric V. Denardo and Bennett L. Fox. Shortest-route methods: 1. reaching, pruning, and buckets. Oper. Res., 27(1):161-186, 1979. URL: https://doi.org/10.1287/opre.27.1.161.
  4. DIMACS. 9th dimacs implementation challenge - shortest paths, 2005. URL: http://users.diag.uniroma1.it/challenge9.
  5. Daniel Duque, Leonardo Lozano, and Andrés L. Medaglia. An exact method for the biobjective shortest path problem for large-scale road networks. Eur. J. Oper. Res., 242(3):788-797, 2015. URL: https://doi.org/10.1016/j.ejor.2014.11.003.
  6. F Guerriero and R Musmanno. Label correcting methods to solve multicriteria shortest path problems. Journal of optimization theory and applications, 111(3):589-613, 2001. Google Scholar
  7. Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybern., 4(2):100-107, 1968. URL: https://doi.org/10.1109/TSSC.1968.300136.
  8. Enrique Machuca and Lawrence Mandow. Multiobjective heuristic search in road maps. Expert Syst. Appl., 39(7):6435-6445, 2012. URL: https://doi.org/10.1016/j.eswa.2011.12.022.
  9. Francisco Javier Pulido, Lawrence Mandow, and José-Luis Pérez-de-la-Cruz. Dimensionality reduction in multiobjective shortest path search. Comput. Oper. Res., 64:60-70, 2015. URL: https://doi.org/10.1016/j.cor.2015.05.007.
  10. Andrea Raith. Speed-up of labelling algorithms for biobjective shortest path problems. In Proceedings of the 45th annual conference of the ORSNZ , 29-30 Nov 2010, Auckland, New Zealand, page 313–322. Operations Research Society of New Zealand, 2010. URL: http://hdl.handle.net/2292/9789.
  11. Andrea Raith and Matthias Ehrgott. A comparison of solution strategies for biobjective shortest path problems. Comput. Oper. Res., 36(4):1299-1331, 2009. URL: https://doi.org/10.1016/j.cor.2008.02.002.
  12. Antonio Sedeño-Noda and Marcos Colebrook. A biobjective dijkstra algorithm. Eur. J. Oper. Res., 276(1):106-118, 2019. URL: https://doi.org/10.1016/j.ejor.2019.01.007.
  13. Liang Shen, Hu Shao, Ting Wu, William HK Lam, and Emily C Zhu. An energy-efficient reliable path finding algorithm for stochastic road networks with electric vehicles. Transportation Research Part C: Emerging Technologies, 102:450-473, 2019. Google Scholar
  14. Shahaf S. Shperberg, Ariel Felner, Nathan R. Sturtevant, Solomon Eyal Shimony, and Avi Hayoun. Enriching non-parametric bidirectional search algorithms. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, The Thirty-First Innovative Applications of Artificial Intelligence Conference, IAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honolulu, Hawaii, USA, January 27 - February 1, 2019, pages 2379-2386. AAAI Press, 2019. URL: https://doi.org/10.1609/aaai.v33i01.33012379.
  15. Anders J. V. Skriver and Kim Allan Andersen. A label correcting approach for solving bicriterion shortest-path problems. Comput. Oper. Res., 27(6):507-524, 2000. URL: https://doi.org/10.1016/S0305-0548(99)00037-4.
  16. Nathan R. Sturtevant and Ariel Felner. A brief history and recent achievements in bidirectional search. In Sheila A. McIlraith and Kilian Q. Weinberger, editors, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 8000-8007. AAAI Press, 2018. URL: https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/17232.
  17. Carlos Hernández Ulloa, William Yeoh, Jorge A. Baier, Han Zhang, Luis Suazo, and Sven Koenig. A simple and fast bi-objective search algorithm. In J. Christopher Beck, Olivier Buffet, Jörg Hoffmann, Erez Karpas, and Shirin Sohrabi, editors, Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling, Nancy, France, October 26-30, 2020, pages 143-151. AAAI Press, 2020. URL: https://aaai.org/ojs/index.php/ICAPS/article/view/6655.
  18. Aphrodite Veneti, Angelos Makrygiorgos, Charalampos Konstantopoulos, Grammati E. Pantziou, and Ioannis A. Vetsikas. Minimizing the fuel consumption and the risk in maritime transportation: A bi-objective weather routing approach. Comput. Oper. Res., 88:220-236, 2017. URL: https://doi.org/10.1016/j.cor.2017.07.010.
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact