bucket-graph-spprc : an extensible C++ library for the shortest path problem with resource constraints
Simon Spoorendonk · 2026
Read bucket-graph-spprc : an extensible C++ library for the shortest path problem with resource constraints by Simon Spoorendonk (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-30847.txt.
Introduction
Simon Spoorendonk releases bucket-graph-spprc, an open-source C++ library for the shortest path problem with resource constraints. That problem, finding the cheapest route that respects limits on resources like time or load, is the pricing subproblem inside branch-cut-and-price solvers for vehicle routing. The library implements a bucket-graph labelling algorithm with two-way search, bucket fixing and arc elimination, storing labels in a layout built for fast vectorised dominance checks.
Its key design choice is a compile-time resource concept, through which a new variant is added via a fixed seven-function interface, and resources combine into the label state with no run-time dispatch. Five resources ship built in. On the shared public benchmark instances, at an identical bound, the library beat the main open-source rival, PathWyse, by factors of 1.3 to 2.35 in shifted geometric mean.
Catalog record
| CREATOR | Simon Spoorendonk |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.30847
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
bucket-graph-spprc : an extensible C++ library for the shortest path problem with resource constraints Simon Spoorendonk Abstract We present bucket-graph-spprc ( 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 [ 16 ] , 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, bgspprc outperforms PathWyse [ 17 ] , the main open-source comparator, by 1.3 × 1.3\times – 2.35 × 2.35\times in shifted geometric mean (and by 1.3 × 1.3\times – 2.3 × 2.3\times even when itself run single-threaded), and runs within 1.9 × 1.9\times – 2.4 × 2.4\times of parallel pull labelling [ 12 ] , a different labelling technique for the same problem. The library, benchmark scripts, and pinned instances are publicly available. Keywords Shortest path problem with resource constraints \cdot Labelling algorithm \cdot Bucket graph \cdot Column generation \cdot Open-source software 1 Introduction The shortest path problem with resource constraints (SPPRC) is the workhorse pricing subproblem in column-generation and branch-cut-and-price approaches to vehicle routing and related problems [ 11 ] . Given a directed graph with arc costs and one or more resources that accumulate along a path subject to per-vertex windows, the SPPRC asks for a minimum-cost source–sink path that respects every resource constraint. In a column-generation context the arc costs are reduced costs, so the subproblem must be solved to optimality, many times, and is typically the computational bottleneck of the overall method. Decades of work on labelling algorithms (dominance-based dynamic programming [ 3 , 6 ] , elementarity relaxations [ 4 , 1 ] , bidirectional search [ 13 ] , and acceleration by completion bounds [ 16 ] ) have made the SPPRC tractable at the scales modern routing solvers require. The most effective recent development is the bucket-graph labelling algorithm of Sadykov, Uchoa and Pessoa [ 16 ] , which partitions labels into buckets along the main resources and uses completion bounds to fix buckets and eliminate arcs, drastically pruning the search. It is a core ingredient of the state-of-the-art VRPSolver [ 11 ] . A subsequent line of work [ 15 ] casts the family of SPPRC variants encountered in routing (elementarity, rank-1 cuts, cumulative cost, pickup-and-delivery) behind a small resource interface , so that one labelling engine serves many problems. Despite the maturity of these methods, the open-source landscape is thin. VRPSolver is academic and closed. PathWyse [ 17 ] is an open (GPLv3) and well-engineered library, but it implements standard labelling with decremental state-space relaxation (DSSR) [ 14 ] , not the bucket-graph algorithm, and resources are added at runtime by subclassing a resource class. cspy [ 22 ] is a Python package aimed at flexibility rather than performance. Open implementations of bucket-graph labelling do exist inside full vehicle-routing solvers; for example BALDES [ 18 ] , a branch-cut-and-price solver for vehicle routing, embeds the labelling in the solver, where it is not readily extractable or reusable as a standalone, extensible SPPRC library. To our knowledge no open, high-performance, and extensible bucket-graph SPPRC library is available to the community. This paper fills that gap. We stress at the outset that the algorithms we implement are published; our contribution is a faithful, performant, and extensible library , together with a reproducible benchmark, not a new algorithm. The contributions of this paper are: • An open, extensible, header-only library. We organize the implementation around a compile-time resource concept : a new SPPRC variant is added by implementing a fixed seven-function interface, and resources compose into a single label state via template metaprogramming, with no runtime dispatch and a state layout fixed at compile time ( section 3 ). The resource interface itself, across-arc concatenation, and the ng-path destination-marking rule are due to the Meta-Solver work [ 15 ] ; our increment is to realize them as a compile-time C++ concept, so that these mechanisms compose for an arbitrary, user-defined set of resources, not only the built-in ones. • A faithful, performant bucket-graph implementation. We implement the bucket-graph algorithm [ 16 ] with bidirectional labelling and across-arc concatenation, bucket fixing and arc elimination from completion bounds, a structure-of-arrays label store with SIMD-accelerated dominance, and a pluggable parallel executor ( section 2 , section 3 ). • A reproducible benchmark study. We compare bgspprc head-to-head against PathWyse on shared public instances, with open data and scripts and a parity construction that makes the linear-programming bound identical on both sides. At that equal bound bgspprc is 1.3\times – 2.35\times faster than PathWyse (and 1.3\times – 2.3\times faster even when run single-threaded) and runs within 1.9\times – 2.4\times of parallel pull labelling [ 12 ] , a different labelling technique for the same problem ( section 4 ). The remainder of the paper is organized as follows. section 2 recalls the SPPRC, the ng-path relaxation, and the bucket-graph labelling algorithm. section 3 presents the library design, centred on the resource concept and its composition. section 4 reports the computational study: the head-to-head comparison with PathWyse, a mode and SIMD ablation, and a comparison with parallel pull labelling for context. section 5 concludes. 2 Background This section fixes notation and recalls the SPPRC and the bucket-graph labelling algorithm at the level needed to follow the library design. The algorithm and its analysis are due to Sadykov, Uchoa and Pessoa [ 16 ] , and the resource interface it can be cast behind is due to [ 15 ] ; we summarize rather than reproduce them, and refer the reader to those papers for the details. Our aim is only to surface the few resource-dependent operations the library factors out. Labelling algorithms solve the SPPRC by propagating partial paths as states ( labels ) and discarding any label dominated by another at the same vertex; we refer to the survey of Irnich and Desaulniers [ 6 ] for a comprehensive treatment. The dynamic-programming formulation with resource extension functions and dominance traces to the column-generation pricing of Desrochers, Desrosiers and Solomon [ 3 ] . Because the elementary variant is strongly NP-hard, early exact methods enforced elementarity directly through node-resource labelling [ 4 ] , but this proved too costly at scale. Two ideas made the relaxation practical: decremental state-space relaxation recovers elementarity incrementally [ 14 ] , and the ng-path relaxation of Baldacci, Mingozzi and Roberti [ 1 ] forbids only cycles local to a per-vertex neighbourhood, trading a small bound loss for a far cheaper subproblem; bounded bidirectional labelling, introduced by Righini and Salani [ 13 ] , halves the effective path length by extending forward and backward labels to a midpoint and joining