EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

APULSE: A Scalable Hybrid Algorithm for the RCSPP on Large-Scale Dense Graphs

Nuno A. D. Soares, António M. R. C. Grilo

IEEE Access · 2026 · 14 · 40690-40706

DOI: 10.1109/access.2026.3669807 ↗

Kurz gefasst

Fachartikel in der Zeitschrift IEEE Access, 2026. Verfasst von Nuno A. D. Soares und 1 weiteren Autor:innen. Die Arbeit nennt 14 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Funds through—Fundação para a Ciência e a Tecnologia (FCT), I.P.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The Resource-Constrained Shortest Path Problem (RCSPP) is a fundamental NP-hard optimization challenge with broad applications ranging from network routing and logistics to autonomous navigation. Although a rich body of exact RCSPP solvers exists, their practical applicability is severely limited on large-scale, dense graphs, where classical label-setting methods suffer from exponential growth in the number of non-dominated labels. This limitation is particularly critical for Uncrewed Ground Vehicle (UGV) mission planning, where route generation is performed prior to deployment using high-resolution terrain representations and heterogeneous threat models that naturally induce dense grid-based graphs and strict travel-time budgets. This paper introduces APULSE, a hybrid search algorithm designed to address this scalability gap by combining A* heuristic guidance, aggressive Pulse-style pruning, and a time-bucketing mechanism that bounds memory consumption through a controlled relaxation of the dominance relation. As a consequence of this discretization, APULSE is not guaranteed to return the exact RCSPP optimum for all instances; instead, it offers a tunable accuracy–efficiency trade-off governed by an auto-tuning parameter that adjusts temporal granularity. A comprehensive computational study evaluates APULSE against state-of-the-art exact solvers and Beam Search heuristics on a large, dense UGV planning graph. Under the default auto-tuning configuration, APULSE matches the empirical reference solution returned by exact solvers in 8 out of 9 evaluated scale and slack configurations, with a maximum observed optimality gap of 0.01% in the remaining case, and empirically converges to the reference solution as the bucketing resolution is increased. At the same time, APULSE remains orders of magnitude faster and substantially more memory-efficient than exact methods on the largest dense instances. These results demonstrate that APULSE enables practical constrained route generation and rapid what-if analysis on dense graphs within operationally realistic decision-making windows.

Förderung

  • National Funds through—Fundação para a Ciência e a Tecnologia (FCT), I.P

Zitieren

APA

Soares, N. A. D., & Grilo, A. M. R. C. (2026). APULSE: A Scalable Hybrid Algorithm for the RCSPP on Large-Scale Dense Graphs. IEEE Access, 14, 40690-40706. https://doi.org/10.1109/access.2026.3669807

Vancouver

Soares NAD, Grilo AMRC. APULSE: A Scalable Hybrid Algorithm for the RCSPP on Large-Scale Dense Graphs. IEEE Access. 2026;14:40690-40706. doi:10.1109/access.2026.3669807

BibTeX
@article{Soares2026,
  author = {Soares, Nuno A. D. and Grilo, António M. R. C.},
  title = {APULSE: A Scalable Hybrid Algorithm for the RCSPP on Large-Scale Dense Graphs},
  journal = {IEEE Access},
  year = {2026},
  volume = {14},
  pages = {40690--40706},
  doi = {10.1109/access.2026.3669807}
}
Kostenlos starten →