A fast exact algorithm for the Resource Constrained Shortest Path Problem

Saman Ahmadi, Guido Tack, Daniel Harabor, Philip Kilby

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

3 Citations (Scopus)

Abstract

Resource constrained path finding is a well studied topic in AI, with real-world applications in different areas such as transportation and robotics. This paper introduces several heuristics in the resource constrained path finding context that significantly improve the algorithmic performance of the initialisation phase and the core search. We implement our heuristics on top of a bidirectional A∗ algorithm and evaluate them on a set of large instances. The experimental results show that, for the first time in the context of constrained path finding, our fast and enhanced algorithm can solve all of the benchmark instances to optimality, and compared to the state of the art algorithms, it can improve existing runtimes by up to four orders of magnitude on large-size network graphs.

Original languageEnglish
Title of host publicationProceedings of the AAAI Conference on Artificial Intelligence, AAAI-21
EditorsKevin Leyton-Brown, Mausam
Place of PublicationPalo Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Pages12217-12224
Number of pages8
ISBN (Electronic)9781713835974
DOIs
Publication statusPublished - 2021
EventAAAI Conference on Artificial Intelligence 2021 - Online, United States of America
Duration: 2 Feb 20219 Feb 2021
Conference number: 35th
https://aaai.org/Conferences/AAAI-21/ (Website)

Publication series

Name35th AAAI Conference on Artificial Intelligence, AAAI 2021
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number14A
Volume35
ISSN (Print)2159-5399
ISSN (Electronic)2374-3468

Conference

ConferenceAAAI Conference on Artificial Intelligence 2021
Abbreviated titleAAAI 2021
Country/TerritoryUnited States of America
Period2/02/219/02/21
Internet address

Cite this