{"ID":5439485,"CreatedAt":"2026-07-01T01:17:58.482524686Z","UpdatedAt":"2026-07-02T19:06:01.127452785Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.30847","arxiv_id":"2606.30847","title":"$\\texttt{bucket-graph-spprc}$: an extensible C++ library for the shortest path problem with resource constraints","abstract":"We present $\\texttt{bucket-graph-spprc}$ ($\\texttt{bgspprc}$ for short), an open-source, header-only C++23 library for the shortest path problem with resource constraints (SPPRC), the pricing subproblem at the heart of branch-cut-and-price for vehicle routing and related problems. The library implements the bucket-graph labelling algorithm of Sadykov, Uchoa and Pessoa (2021), with bidirectional labelling, across-arc concatenation, bucket fixing and arc elimination, and a structure-of-arrays label store with SIMD-accelerated dominance. Its central design feature is a compile-time resource concept: a new SPPRC variant is added by implementing a fixed seven-function interface, and resources compose into a label state with no runtime dispatch, the state layout fixed at compile time. Five resources ship 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 an identical bound, $\\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 itself run single-threaded), and runs within $1.9\\times$--$2.4\\times$ of parallel pull labelling (Petersen and Spoorendonk, 2025), a different labelling technique for the same problem. The library, benchmark scripts, and pinned instances are publicly available.","short_abstract":"We present $\\texttt{bucket-graph-spprc}$ ($\\texttt{bgspprc}$ for short), an open-source, header-only C++23 library for the shortest path problem with resource constraints (SPPRC), the pricing subproblem at the heart of branch-cut-and-price for vehicle routing and related problems. The library implements the bucket-grap...","url_abs":"https://arxiv.org/abs/2606.30847","url_pdf":"https://arxiv.org/pdf/2606.30847v1","authors":"[\"Simon Spoorendonk\"]","published":"2026-06-29T19:23:57Z","proceeding":"math.OC","tasks":"[\"math.OC\",\"cs.DS\",\"cs.MS\"]","methods":"[]","has_code":false}