pith. sign in

arxiv: 2606.30847 · v1 · pith:UIZS4KJ7new · submitted 2026-06-29 · 🧮 math.OC · cs.DS· cs.MS

texttt{bucket-graph-spprc}: an extensible C++ library for the shortest path problem with resource constraints

Simon Spoorendonk This is my paper

Pith reviewed 2026-07-01 01:24 UTC · model grok-4.3

classification 🧮 math.OC cs.DScs.MS
keywords SPPRCbucket-graph labellingC++ libraryvehicle routingbranch-cut-and-priceshortest pathresource constraintsopen source
0
0 comments X

The pith

bgspprc is a new open-source C++ library for the shortest path problem with resource constraints that outperforms PathWyse by 1.3 to 2.35 times.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents bucket-graph-spprc, an extensible header-only C++ library implementing the bucket-graph labelling algorithm for the shortest path problem with resource constraints. This subproblem is central to branch-cut-and-price methods for vehicle routing. The library's key innovation is a compile-time resource concept that allows adding new resource types by implementing a seven-function interface without runtime dispatch. Benchmarks on public instances show it runs 1.3 to 2.35 times faster than the main open-source alternative PathWyse. A sympathetic reader would care because faster exact solutions to routing problems can improve logistics and transportation planning.

Core claim

The bucket-graph-spprc library implements the bucket-graph labelling algorithm of Sadykov, Uchoa and Pessoa with bidirectional labelling, across-arc concatenation, bucket fixing, arc elimination, and SIMD-accelerated dominance, achieving better performance than PathWyse through its compile-time resource composition design.

What carries the argument

The compile-time resource concept, where a new SPPRC variant is added by implementing a fixed seven-function interface and resources compose into a label state with layout fixed at compile time.

If this is right

  • New SPPRC variants can be implemented without modifying the core library code.
  • The library supports five built-in resources including time/capacity and ng-path elementarity.
  • It can be integrated into branch-cut-and-price solvers for vehicle routing problems.
  • Performance improvements in the pricing subproblem can lead to faster overall optimization.
  • Single-threaded execution still shows speedups over the comparator.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The design pattern could be applied to other combinatorial optimization libraries to reduce overhead.
  • Reproducibility through public instances and scripts sets a standard for benchmarking in the field.
  • Extensibility might encourage development of custom resources for specific problem variants.
  • Comparison to parallel pull labelling suggests potential for hybrid approaches.

Load-bearing premise

The performance comparison assumes that running both libraries to the same bound on the same public instances produces a fair, unbiased measure of algorithmic speed without hidden differences in implementation quality or instance selection affecting the outcome.

What would settle it

Running both libraries on the shared public instances to the same bound and finding that PathWyse achieves equal or better shifted geometric mean times would falsify the performance superiority claim.

Figures

Figures reproduced from arXiv: 2606.30847 by Simon Spoorendonk.

Figure 1
Figure 1. Figure 1: Performance profile on the shared spprclib and roberti instances: for each solver, the fraction of instances [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript presents bgspprc, an open-source header-only C++23 library implementing the bucket-graph labelling algorithm of Sadykov et al. (2021) for the shortest path problem with resource constraints (SPPRC). Key features include bidirectional labelling, across-arc concatenation, bucket fixing, arc elimination, a structure-of-arrays label store with SIMD dominance, and a compile-time resource concept allowing new variants via a seven-function interface with no runtime dispatch. Five built-in resources are provided. The central empirical claim is that, on shared public instances run to an identical bound, bgspprc outperforms PathWyse by 1.3×–2.35× in shifted geometric mean (and 1.3×–2.3× single-threaded) while remaining within 1.9×–2.4× of parallel pull labelling; the library, benchmark scripts, and pinned instances are publicly released.

Significance. If the reported timings hold under the stated reproducibility conditions, the work supplies a practical, extensible open-source component for the pricing subproblem in branch-cut-and-price algorithms for vehicle routing and related problems. Explicit credit is due for the public release of the implementation, benchmark scripts, and pinned instances, which directly supports verification of the performance claims against external comparators.

minor comments (2)
  1. [Abstract] Abstract: the speedup ranges (1.3×–2.35× and 1.9×–2.4×) are stated without identifying which instance classes or resource combinations produce the lower versus upper ends; a brief clarification or reference to a supplementary table would improve interpretability.
  2. [§3 or §4] The description of the compile-time resource interface (seven-function contract and fixed state layout) is central to the extensibility claim; a short code snippet or explicit listing of the seven functions in §3 or §4 would make the mechanism concrete for readers wishing to add a new resource.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript and the recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The manuscript is an implementation and benchmarking paper for an SPPRC library. It implements the bucket-graph labelling algorithm from an external 2021 citation and reports shifted-geometric-mean speedups on public instances against two external open-source comparators. No equations, derivations, fitted parameters, or uniqueness theorems appear; the central claim is a reproducible empirical timing result whose validity does not reduce to any self-citation chain or definitional loop. Self-citations (e.g., to Petersen & Spoorendonk 2025) are incidental and not load-bearing for any claimed derivation.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

This is a software library and benchmarking paper; it introduces no free parameters, mathematical axioms, or invented entities. The contribution consists of code, an implementation of a previously published algorithm, and timing measurements.

pith-pipeline@v0.9.1-grok · 5849 in / 1242 out tokens · 51675 ms · 2026-07-01T01:24:53.872077+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 2 canonical work pages

  1. [1]

    A bucket graph–based labeling algorithm with application to vehicle routing.Transportation Science, 55(1):4–28, 2021

    Ruslan Sadykov, Eduardo Uchoa, and Artur Pessoa. A bucket graph–based labeling algorithm with application to vehicle routing.Transportation Science, 55(1):4–28, 2021

    2021

  2. [2]

    PathWise

    Matteo Salani, Saverio Basso, and Vincenzo Giuffrida. PathWyse: a flexible, open-source library for the resource constrained shortest path problem.Optimization Methods and Software, 39(2):298–320, 2024. Earlier preprint: arXiv:2306.08622, titled “PathWise”

    work page arXiv 2024

  3. [3]

    A parallel pull labelling algorithm for the resource constrained shortest path problem, 2025

    Bjørn Petersen and Simon Spoorendonk. A parallel pull labelling algorithm for the resource constrained shortest path problem, 2025

    2025

  4. [4]

    A generic exact solver for vehicle routing and related problems.Mathematical Programming, 183(1–2):483–523, 2020

    Artur Pessoa, Ruslan Sadykov, Eduardo Uchoa, and François Vanderbeck. A generic exact solver for vehicle routing and related problems.Mathematical Programming, 183(1–2):483–523, 2020

    2020

  5. [5]

    A new optimization algorithm for the vehicle routing problem with time windows.Operations Research, 40(2):342–354, 1992

    Martin Desrochers, Jacques Desrosiers, and Marius Solomon. A new optimization algorithm for the vehicle routing problem with time windows.Operations Research, 40(2):342–354, 1992

    1992

  6. [6]

    Shortest path problems with resource constraints

    Stefan Irnich and Guy Desaulniers. Shortest path problems with resource constraints. In Guy Desaulniers, Jacques Desrosiers, and Marius M. Solomon, editors,Column Generation, pages 33–65. Springer, Boston, MA, 2005

    2005

  7. [7]

    An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems.Networks, 44(3):216–229, 2004

    Dominique Feillet, Pierre Dejax, Michel Gendreau, and Cyrille Gueguen. An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems.Networks, 44(3):216–229, 2004

    2004

  8. [8]

    New route relaxation and pricing strategies for the vehicle routing problem.Operations Research, 59(5):1269–1283, 2011

    Roberto Baldacci, Aristide Mingozzi, and Roberto Roberti. New route relaxation and pricing strategies for the vehicle routing problem.Operations Research, 59(5):1269–1283, 2011

    2011

  9. [9]

    Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints.Discrete Optimization, 3(3):255–273, 2006

    Giovanni Righini and Matteo Salani. Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints.Discrete Optimization, 3(3):255–273, 2006

    2006

  10. [10]

    Bucket graph meta-solver for the resource constrained shortest path problem, 2026

    Ruslan Sadykov, Aurélien Froger, Eduardo Uchoa, Artur Pessoa, Teobaldo Bulhões, and Daniel de Araujo. Bucket graph meta-solver for the resource constrained shortest path problem, 2026. Preprint, HAL hal-05486295, https://inria.hal.science/hal-05486295

    2026

  11. [11]

    New dynamic programming algorithms for the resource constrained elementary shortest path problem.Networks, 51(3):155–170, 2008

    Giovanni Righini and Matteo Salani. New dynamic programming algorithms for the resource constrained elementary shortest path problem.Networks, 51(3):155–170, 2008

    2008

  12. [12]

    cspy: A Python package with a collection of algorithms for the (resource) constrained shortest path problem.Journal of Open Source Software, 5(49):1655, 2020

    David Torres Sánchez. cspy: A Python package with a collection of algorithms for the (resource) constrained shortest path problem.Journal of Open Source Software, 5(49):1655, 2020. 15 bucket-graph-spprc: an extensible C++ library for the shortest path problem with resource constraintsA PREPRINT

    2020

  13. [13]

    BALDES: a modern C++ bucket graph labeling algorithm for vehicle routing

    Laio Oriel Seman, Pedro Munari, Teobaldo Bulhões, and Eduardo Camponogara. BALDES: a modern C++ bucket graph labeling algorithm for vehicle routing. https://github.com/lseman/baldes, 2024. Software, MIT license

    2024

  14. [14]

    Exact branch-price-and-cut algorithms for vehicle routing.Transportation Science, 53(4):946–985, 2019

    Luciano Costa, Claudio Contardo, and Guy Desaulniers. Exact branch-price-and-cut algorithms for vehicle routing.Transportation Science, 53(4):946–985, 2019

    2019

  15. [15]

    Subset-row inequalities applied to the vehicle-routing problem with time windows.Operations Research, 56(2):497–511, 2008

    Mads Jepsen, Bjørn Petersen, Simon Spoorendonk, and David Pisinger. Subset-row inequalities applied to the vehicle-routing problem with time windows.Operations Research, 56(2):497–511, 2008

    2008

  16. [16]

    Limited memory rank-1 cuts for vehicle routing problems.Operations Research Letters, 45(3):206–209, 2017

    Diego Pecin, Artur Pessoa, Marcus Poggi, Eduardo Uchoa, and Haroldo Santos. Limited memory rank-1 cuts for vehicle routing problems.Operations Research Letters, 45(3):206–209, 2017

    2017

  17. [17]

    Jepsen, Bjørn Petersen, Simon Spoorendonk, and David Pisinger

    Mads K. Jepsen, Bjørn Petersen, Simon Spoorendonk, and David Pisinger. A branch-and-cut algorithm for the capacitated profitable tour problem.Discrete Optimization, 14:78–96, 2014

    2014

  18. [18]

    A branch-and-cut algorithm for the elementary shortest path problem with a capacity constraint

    Mads Jepsen, Bjørn Petersen, and Simon Spoorendonk. A branch-and-cut algorithm for the elementary shortest path problem with a capacity constraint. Technical Report 08/01, DIKU, Department of Computer Science, University of Copenhagen, 2008

    2008

  19. [19]

    Marius M. Solomon. Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2):254–265, 1987

    1987

  20. [20]

    Resource constrained shortest path problem instances with time windows, capacity, and neighbourhoods.https://github.com/spoorendonk/rcspp_dataset, 2025

    Simon Spoorendonk. Resource constrained shortest path problem instances with time windows, capacity, and neighbourhoods.https://github.com/spoorendonk/rcspp_dataset, 2025. Dataset

    2025

  21. [21]

    Flowty: a network optimization solver for routing and resource-constrained flow problems

    Flowty. Flowty: a network optimization solver for routing and resource-constrained flow problems. https: //flowty.ai, 2026. Optimization software

    2026

  22. [22]

    bucket-graph-spprc: a header-only C++23 bucket graph labeling library for the SPPRC

    Simon Spoorendonk. bucket-graph-spprc: a header-only C++23 bucket graph labeling library for the SPPRC. Zenodo, version v0.1.0, https://doi.org/10.5281/zenodo.20819209, 2026. Concept DOI https://doi. org/10.5281/zenodo.20819208resolves to the latest version. 16 bucket-graph-spprc: an extensible C++ library for the shortest path problem with resource const...

    work page doi:10.5281/zenodo.20819209 2026