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}
}

Document

DOI: 10.4230/LIPIcs.CP.2021.11

Vehicle Dynamics in Pickup-And-Delivery Problems Using Electric Vehicles

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

Published in: LIPIcs, Volume 210, 27th International Conference on Principles and Practice of Constraint Programming (CP 2021)

Abstract

Electric Vehicles (EVs) are set to replace vehicles based on internal combustion engines. Path planning and vehicle routing for EVs need to take their specific characteristics into account, such as reduced range, long charging times, and energy recuperation. This paper investigates the importance of vehicle dynamics parameters in energy models for EV routing, particularly in the Pickup-and-Delivery Problem (PDP). We use Constraint Programming (CP) technology to develop a complete PDP model with different charger technologies. We adapt realistic instances that consider vehicle dynamics parameters such as vehicle mass, road gradient and driving speed to varying degrees. The results of our experiments show that neglecting such fundamental vehicle dynamics parameters can affect the feasibility of planned routes for EVs, and fewer/shorter charging visits will be planned if we use energy-efficient paths instead of conventional shortest paths in the underlying system model.

Cite as

Saman Ahmadi, Guido Tack, Daniel Harabor, and Philip Kilby. Vehicle Dynamics in Pickup-And-Delivery Problems Using Electric Vehicles. In 27th International Conference on Principles and Practice of Constraint Programming (CP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 210, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ahmadi_et_al:LIPIcs.CP.2021.11,
  author =	{Ahmadi, Saman and Tack, Guido and Harabor, Daniel and Kilby, Philip},
  title =	{{Vehicle Dynamics in Pickup-And-Delivery Problems Using Electric Vehicles}},
  booktitle =	{27th International Conference on Principles and Practice of Constraint Programming (CP 2021)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-211-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{210},
  editor =	{Michel, Laurent D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2021.11},
  URN =		{urn:nbn:de:0030-drops-153020},
  doi =		{10.4230/LIPIcs.CP.2021.11},
  annote =	{Keywords: Electric vehicle routing, pickup-and-delivery problem, vehicle dynamics}
}

Document

DOI: 10.4230/LIPIcs.ESA.2021.3

Bi-Objective Search with Bi-Directional A*

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

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

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

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)

Copy BibTex To Clipboard

@InProceedings{ahmadi_et_al:LIPIcs.ESA.2021.3,
  author =	{Ahmadi, Saman and Tack, Guido and Harabor, Daniel and Kilby, Philip},
  title =	{{Bi-Objective Search with Bi-Directional A*}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{3:1--3:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus 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.2021.3},
  URN =		{urn:nbn:de:0030-drops-145849},
  doi =		{10.4230/LIPIcs.ESA.2021.3},
  annote =	{Keywords: Bi-objective search, heuristic search, shortest path problem}
}

Search Results

Documents authored by Ahmadi, Saman

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

Abstract

Cite as

Vehicle Dynamics in Pickup-And-Delivery Problems Using Electric Vehicles

Abstract

Cite as

Bi-Objective Search with Bi-Directional A*

Abstract

Cite as

Thanks for your feedback!

Could not send message