BALDES: A Bucket Graph Labeling Algorithm for Vehicle Routing

BALDES (pronounced /'baw-dɨs/) is a C implementation of a Bucket Graph-based labeling algorithm designed to solve the Resource-Constrained Shortest Path Problem (RCSPP), commonly used as a subproblem in state-of-the-art Branch-Cut-and-Price algorithms for various Vehicle Routing Problems (VRPs).

The algorithm is based on state-of-the-art RCESPP techniques, including interior point stabilization, limited memory subset row cuts, clustering branching, and the so called bucket graph labelling.

• 📋 Table of Contents
• 📝 Overview
  • 🚀 Key Features
• ⚠️ Disclaimer
• 📋 TODO
• 🛠️ Building
  • 📋 Prerequisites
  • ⚙️ Compiling
    •  macOS users
    • MDM-HGS-VRPTW
  • 🛠️ Compilation Options
• 📂 Input File Format
  • 🚀 Running the Example Algorithm
  • 🐍 Python Wrapper
• 📖 Documentation
• 📜 License
• 🖊️ Cite
• 🙏 Acknowledgements
• 📚 References

The Bucket Graph-based labeling algorithm organizes labels into buckets based on vertex and resource consumption intervals. This structure reduces the number of dominance checks, making the algorithm highly efficient, particularly in large VRP instances with extensive resource constraints.

Efficient resource-constrained routing: Scales well for large VRP instances with complex constraints.

State-of-the-art heuristic integration: Uses top-performing heuristics from HGS-VRPTW for initial solutions.

Flexible, customizable configuration: Optimized for various constraints and resource types.

• Bucket Graph Organization

  Grouping labels by vertex and resource consumption to minimize dominance checks, using n-dimensional Splay Trees to keep the most acessed buckets easier to reach.

• Parallel Bi-Directional Labeling

  Supports paralell forward and backward search strategies.

• Dominance Rules

  Efficient dominance checks using resource-based comparisons and integration of additional criteria from Limited-Memory Subset Row Cuts (SRCs) for enhanced speed. AVX can be enabled for faster dominance check.

• Multi-phase solving

  Out-of-the-box multi-phase solving that begins with heuristics and dynamically guides the algorithm towards an exact solution.

  • Stage 1: Retain min cost per bucket, filter search space.
  • Stage 2: Relax dominance, expand label retention.
  • Stage 3: Estimate bounds, discard suboptimal paths.
  • Stage 4: Apply exact dominance for optimal path.

• Limited-Memory Subset Row Cuts

  Performs the separation of the SRCs in paralell, even for high order cuts.

• High-quality initial solutions

  Employs the state-of-the-art HGS-VRPTW algorithm to generate high-quality initial bounds and routes, an extension of the HGS-CVRP method employed by the ORTEC team to win the VRPTW track at the DIMACS Implementation Challenge. We also enchanced the HGS-VRPTW with the concepts proposed in MDM-HGS-CVRP, resulting in what we call the MDM-HGS-VRPTW.

• Multi-stage branching

  Performs a multi-stage branching, including the recent cluster branching. In each node, branching variables are selected through a hierarchical evaluation. The evaluation involves three phases: in Phase 0, candidates are chosen based on pseudo-cost history, fractional proximity to integers, and, for edges, distance to the depot. Phase 1 evaluates these by solving a restricted master LP for each child node without new columns, using the Product Rule to select candidates maximizing lower bound increases. In Phase 2, the best candidates undergo further relaxation with heuristic column generation, again selected by the Product Rule. This structured approach adapts to tree depth, prioritizing impactful selections early on.

• Adaptive Bucket-Size

  In addition to automatically increasing the bucket step size when the number of dominance checks reach a certain level, we also introduce the concept of "sub-buckets". Sub-buckets are created when the number of labels in a bucket gets to "BUCKET_CAPACITY", and their dominance-order is automatically handled.

• Improvement Heuristics: Optional fast improvement heuristics are applied at the end of each labeling phase to enhance label quality. The improvement heuristics are based on an iterated local search with adaptive operators weight in a ANLS-like heuristic.

Some features are experimental and subject to ongoing improvements:

• [experimental] Branching (Branch-Cut-and-Price) for the CVRP/VRPTW

• Fix branching duals
• Refactor high order SRC cuts
• Change pybind to nanobind
• Enchance the improvement heuristics.

• C 23 compliant compiler (tested with GCC 14.* and Clang 19.*)
• Parallel Tasks: NVIDIA/stdexec
• Console Output: fmt
• Memory Allocation: jemalloc (recommended)
• Hashing and Storage: xxHash and ankerl::unordered_dense
• Optional: pybind11 for Python wrapper, Gurobi for MIP solver

cmake -S . -B build
cd build
make -j$nprocs

Make sure the GUROBI_HOME environment variable is set if Gurobi is to be used.

For macOS, it is recommended to install latest llvm via homebrew.

brew install llvm
export CC=/opt/homebrew/opt/llvm/bin/clang
export CXX=/opt/homebrew/opt/llvm/bin/clang  
export PATH=/opt/homebrew/opt/llvm/bin:$PATH

To compile only MDM-HGS-VRPTW:

cmake -S . -B build
cd build
make -j$nprocs -DHGS=ON -DBALDES=OFF

Boolean Options

Solvers

Numerical and Other Definitions

Note 1: Including depot and depot copy (end node).

Note 2: Only one stabilization can be selected.

Resource Disposability Definition

To control how each resource is treated (whether disposable, non-disposable, or binary), define the disposability type for each resource in the BucketOptions struct. Each position in the resource_disposability vector corresponds to a specific resource and should be assigned a value of 0, 1, or 2 to indicate the disposability type:

• 0: Disposable resource – the resource can be consumed or reset during the routing process.
• 1: Non-disposable resource – the resource is conserved and cannot be disposed of.
• 2: Binary resource – the resource toggles between two states (e.g., 0 for off and 1 for on).

Example configuration:

struct BucketOptions {
    int depot                   = 0;
    int end_depot               = N_SIZE - 1;
    int max_path_size           = N_SIZE / 2;
    int main_resources          = 1;
    std::vector<std::string> resources = {"time", "capacity"};
    std::vector<int> resource_type = {1, 1}; // 1=disposable, 0=non-disposable
    std::vector<int> or_resources = {1};
};

In this example:

• "time" is treated as a disposable resource (0).
• "capacity" is treated as a non-disposable resource (1).

TUI

If you prefer, you can run the configurer tool, which provides a TUI for configuring BALDES.

./configurer.sh

The input file should specify the number of nodes, time horizon, vehicle capacities, and other VRP constraints.
See examples in the examples/ directory.

To run Solomon-like instances:

./baldes vrptw ../examples/C203.txt

To run CVRP-like instance like the 10k instance proposed by Uchoa et al..

./baldes cvrp ../examples/XML100_1111_01.vrp

We also provide a Python wrapper, which can be used to instantiate the bucket graph labeling:

# Import external libraries
import random

# Now you can import the BALDES module
import pybaldes as baldes

# Define nodes
nodes = [baldes.VRPNode() for _ in range(102)]
num_intervals = 1

# Set random bounds for each node
id = 0
for node in nodes:
    # Set random lower bounds
    node.lb = [random.randint(0, 9500) for _ in range(num_intervals)]  
    # Set random upper bounds greater than lb
    node.ub = [random.randint(lb   1, 10000) for lb in node.lb]
    # Set random duration
    node.duration = random.randint(1, 100)
    # Set random cost
    node.cost = random.randint(1, 100)
    # Set random start time
    node.start_time = random.randint(0, 10000)
    # Set random end time greater than start time
    node.end_time = random.randint(node.start_time, 10000)
    # Set random demand
    node.demand = random.randint(1, 100)
    # Set random consumption
    node.consumption = [random.randint(1, 100) for _ in range(num_intervals)]
    # Set random location
    node.set_location(random.randint(0, 100), random.randint(0, 100))
    node.id = id
    id  = 1

# Create fake distance matrix with size equal to the number of nodes
distances = [[random.randint(1, 100) for _ in range(len(nodes))] for _ in range(len(nodes))]

# Initialize BucketGraph using these nodes
bg = baldes.BucketGraph(nodes, 12000, 1)

# Create random duals with size equal to the number of nodes
duals = [random.random() for _ in range(len(nodes))]

# Set the distance matrix, adjacency list, and duals
bg.set_distance_matrix(distances)
bg.set_adjacency_list()
bg.set_duals(duals)
bg.setup()

# Call the solve method
labels = bg.solve()

You can access the doxygen documentation here.

This project is licensed under the MIT License - see the LICENSE file for details.

If you use this library, please cite it as follows:

@Misc{BucketGraphLabeling,
 author       = {Laio Oriel Seman and Pedro Munari and Teobaldo Bulhões and Eduardo Camponogara},
 title        = {BALDES: a modern C   Bucket Graph Labeling Algorithm for Vehicle Routing},
 howpublished = {\url{https://github.com/lseman/baldes}},
 year         = {2024},
 note         = {GitHub repository},
 urldate      = {2024-09-17},
 month        = sep
}

We want to thank Vladislav Nepogodin for his insights into C .

1. A Bucket Graph Based Labeling Algorithm for Vehicle Routing. Ruslan Sadykov, Eduardo Uchoa, Artur Alves Pessoa. Transportation Science, 2021. DOI: 10.1287/trsc.2020.0985
2. Limited memory rank-1 cuts for vehicle routing problems. Diego Pecin, Artur Pessoa, Marcus Poggi, Eduardo Uchoa, Haroldo Santos. Operations Research Letters 45.3 (2017): 206-209. DOI: 10.1016/j.orl.2017.02.006
3. Hybrid Genetic Search for the Vehicle Routing Problem with Time Windows: a High-Performance Implementation. Wouter Kool, Joep Olde Juninck, Ernst Roos, Kamiel Cornelissen, Pim Agterberg, Jelke van Hoorn, Thomas Visser. 12th DIMACS Implementation Challenge Workshop, 2022.
4. Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Thibaut Vidal. Computers & Operations Research, 140 (2022): 105643. DOI: 10.1016/j.cor.2021.105643