DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2025.97

A Fast and Simple Algorithm for the Resource Constrained Shortest Path Problem

Authors: Saman Ahmadi, Andrea Raith, and Mahdi Jalili

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract

Constrained pathfinding is a classic yet challenging network optimization problem with broad applicability across many real-world domains. The Resource-Constrained Shortest Path (RCSP) problem focuses on finding cost-optimal paths that satisfy multiple resource constraints. In this paper, we propose a novel heuristic-guided search framework that accelerates constrained search in large-scale networks, including those with negative costs and resources, by leveraging efficient queuing and pruning strategies. Experimental results on real-world benchmark maps show that our framework achieves up to two orders of magnitude speedup over state-of-the-art methods, demonstrating its effectiveness in solving challenging RCSP instances within limited time.

Cite as

Saman Ahmadi, Andrea Raith, and Mahdi Jalili. A Fast and Simple Algorithm for the Resource Constrained Shortest Path Problem. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 97:1-97:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ahmadi_et_al:LIPIcs.ESA.2025.97,
  author =	{Ahmadi, Saman and Raith, Andrea and Jalili, Mahdi},
  title =	{{A Fast and Simple Algorithm for the Resource Constrained Shortest Path Problem}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{97:1--97:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.97},
  URN =		{urn:nbn:de:0030-drops-245668},
  doi =		{10.4230/LIPIcs.ESA.2025.97},
  annote =	{Keywords: constrained pathfinding, shortest path problem, heuristic search}
}

Search Results

Documents authored by Raith, Andrea

A Fast and Simple Algorithm for the Resource Constrained Shortest Path Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message