vrp-gpu

vrp-gpu provides CVRP data structures, CPU reference heuristics and optional CUDA evaluation of 2-opt moves. It parses Solomon-style text, constructs routes with a greedy nearest-neighbor heuristic, and improves routes on the CPU. The GPU API computes candidate deltas or selects a single move; it does not run a complete GPU search loop or mutate a route.

The current alpha is 0.1.1-alpha. The API may change before a stable release. See the documentation for that version.

Features

Without gpu, the library has no third-party runtime dependencies. Enabling gpu requires a working NVIDIA driver when a GPU operation is executed. The PTX is precompiled; consumers do not need cuda-oxide or a nightly Rust compiler.

Installation

To use the published alpha, specify its prerelease version:

[dependencies]
vrp-gpu = "0.1.1-alpha"

For changes not yet published, pin a tested Git revision:

[dependencies]
vrp-gpu = { git = "https://github.com/pedrozaz/vrp-gpu", rev = "<tested-commit>" }

Example

use std::error::Error;

use vrp_gpu::{
    construct::nearest_neighbor,
    instance::SolomonInstance,
    local_search::cpu::two_opt,
};

fn main() -> Result<(), Box<dyn Error>> {
    let input = "\
DEMO
VEHICLE
2 10
CUSTOMER
0 0 0 0 0 100 0
1 1 0 5 0 100 0
2 0 1 5 0 100 0
";
    let instance: SolomonInstance = input.parse()?;
    let mut solution = nearest_neighbor(&instance);

    assert!(solution.is_feasible(&instance));
    let before = solution.total_distance(&instance);
    two_opt(&mut solution, &instance);
    assert!(solution.is_feasible(&instance));
    assert!(solution.total_distance(&instance) <= before);
    Ok(())
}

nearest_neighbor panics on malformed instances, a customer whose demand exceeds vehicle capacity, or exhaustion of the configured fleet. Fleet exhaustion only means this greedy construction failed. If instance data are constructed or changed through public fields, call SolomonInstance::validate before passing them to CPU routines.

To use the optional GPU API in the published alpha, enable the feature:

[dependencies]
vrp-gpu = { version = "0.1.1-alpha", features = ["gpu"] }

gpu::evaluate_two_opt_deltas returns a row-major n × n matrix with computed f32 deltas for valid i < j and positive infinity elsewhere. Extreme finite input distances can still yield non-finite arithmetic results. gpu::best_two_opt_move returns the best finite negative delta as Option<TwoOptMove>. Exact ties choose the lowest row-major (i, j). Both functions return GpuEvaluationError for invalid input, size overflow or CUDA driver failure. Empty and singleton routes return without creating a CUDA context. A returned move is only a proposal: apply it with cpu::apply_two_opt if your application accepts it.

After enabling gpu, one selection and application can be written as follows. The documentation build compiles this example without running it because a GPU and driver are required:

#[cfg(feature = "gpu")]
fn main() -> Result<(), Box<dyn std::error::Error>> {
    use vrp_gpu::{
        instance::SolomonInstance,
        local_search::{cpu, gpu},
        solution::Route,
    };

    let input = r#"DEMO
VEHICLE
1 10
CUSTOMER
0 0 0 0 0 100 0
1 1 0 0 0 100 0
2 0 1 0 0 100 0
3 2 1 0 0 100 0
"#;
    let instance: SolomonInstance = input.parse()?;
    let mut route = Route::from_nodes(vec![1, 2, 3]);
    if let Some(best) = gpu::best_two_opt_move(&route, &instance)? {
        cpu::apply_two_opt(&mut route, best.i, best.j);
    }
    Ok(())
}

#[cfg(not(feature = "gpu"))]
fn main() {}

Each nontrivial GPU call currently creates a CUDA context, loads the embedded PTX and transfers the matrix and route. There is no reusable device session or GPU convergence loop. The checked-in artifact targets sm_120 and has been hardware-validated on an NVIDIA GeForce RTX 5060 Ti. Other devices have no compatibility claim. The recorded validation found this end-to-end GPU API slower than the CPU reference for all measured nontrivial routes; no speedup is claimed. See the input and algorithm guide for exact model and numerical contracts.

Minimum supported Rust version

The supported feature set requires Rust 1.88 or newer (edition 2024). Raising the MSRV is a release-level change and must be recorded in the changelog.

See the repository documentation for architecture, kernel contracts and release procedures.

Licensed under Apache-2.0.