Skip to content

Latest commit

 

History

History
355 lines (250 loc) · 14.6 KB

README.md

File metadata and controls

355 lines (250 loc) · 14.6 KB
Raw

doc status License

BALDES: A Branch-Cut-and-Price Bucket Graph Labeling Algorithm for Vehicle Routing

BALDES BALDES (pronounced /'baw-dɨs/) is a high-performance C++ implementation of a Branch-Cut-and-Price algorithm. It features a custom version of the Bucket Graph-based labeling algorithm tailored to efficiently solve the Resource-Constrained Shortest Path Problem (RCSPP). Currently, BALDES is optimized for tackling two key problem classes: (i) Capacitated Veichle Routing Problem (CVRP) and (ii) Vehicle Routing Problems with Time-Windows (VRPTW).

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

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.

🚀 Key Features

  • 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.

⚠️ Disclaimer

Some features are experimental and subject to ongoing improvements:

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

📋 TODO

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

🛠️ Building

📋 Prerequisites

⚙️ Compiling

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

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

 macOS users

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

MDM-HGS-VRPTW

To compile only MDM-HGS-VRPTW:

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

🛠️ Compilation Options

Boolean Options

Option Description Default
FIXED_BUCKETS Enable bucket arc fixing ON
JEMALLOC Enable jemalloc ON
SORTED_LABELS Sort labels on bucket insertion ON
SRC Enable limited memory SRC cuts ON
LIMITED_BUCKETS Limit the capacity of the buckets OFF
MCD Perform MCD on instance capacities OFF
RCC Enable RCC cuts OFF
RIH Enable improvement heuristics OFF
SCHRODINGER Enable schrodinger pool OFF
STAB$^2$ Use dynamic-alpha smooth stabilization OFF
TR Use trust region stabilization OFF
WITH_PYTHON Enable the python wrapper OFF

Solvers

Option Description Default
IPM$^2$ Use interior point stabilization with the in-house solver ON
HIGHS Enable HiGHS as the IP Solver ON
GUROBI Enable GUROBI as the IP Solver OFF

Numerical and Other Definitions

Option Description Default
R_SIZE Number of resources 1
N_SIZE$^1$ Number of customers 102
BUCKET_CAPACITY Maximum bucket capacity if LIMITED_BUCKETS is enabled 50
N_ADD Number of columns to be added for each pricing 10
HGS Maximum HGS running time 5

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

configurer configurer

📂 Input File Format

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

🚀 Running the Example Algorithm

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

🐍 Python Wrapper

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, 9000) 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()

📖 Documentation

You can access the doxygen documentation here.

📜 License

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

🖊️ Cite

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
}

🙏 Acknowledgements

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

📚 References

  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