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 ↗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.
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}
}
EUVIMED