We introduce $\texttt{bucket-graph-spprc}$ (shortened as $\texttt{bgspprc}$), an open-source, header-only C++23 library for the shortest path problem with resource constraints (SPPRC), which is a core subproblem in branch-cut-and-price for vehicle routing and related issues. The library implements the bucket-graph labeling algorithm by Sadykov, Uchoa, and Pessoa (2021), featuring bidirectional labeling, across-arc concatenation, bucket fixing, and arc elimination, along with a SIMD-accelerated structure-of-arrays label store.
A central design feature is the compile-time resource concept: new SPPRC variants can be added by implementing a fixed seven-function interface, and resources compose into a label state without runtime dispatch, with the state layout fixed at compile time. Five resources are built-in: time/capacity, ng-path elementarity relaxation, rank-1 cuts, cumulative cost, and pickup-and-delivery.
In a reproducible head-to-head comparison on shared public instances at identical bounds, $\texttt{bgspprc}$ outperforms PathWyse (Salani, Basso, and Giuffrida, 2024), the main open-source comparator, by $1.3\times$--$2.35\times$ in shifted geometric mean (and by $1.3\times$--$2.3\times$ even when run single-threaded), and runs within $1.9\times$--$2.4\times$ of parallel pull labeling (Petersen and Spoorendonk, 2025), a different labeling technique for the same problem. The library, benchmark scripts, and pinned instances are publicly available.
Blogger's Review: This library's design leverages compile-time features to significantly enhance algorithm efficiency, especially in solving resource-constrained problems. For applications requiring efficient path planning, this open-source library is undoubtedly a crucial tool. Its outstanding performance in comparative tests also provides a solid foundation for further research.