lkh-rs 0.1.0

Python bindings for the LKH-rs solver wrapper

LKH-rs

Rust bindings and safe wrappers for LKH3, Keld Helsgaun's heuristic solver for TSP (traveling salesperson problems) and related routing problems.

The crate builds the vendored LKH C sources with cc, generates Rust bindings with bindgen, and exposes safe Rust APIs for both in-memory programmatic solves and existing LKH parameter files.

Requirements

The build uses bindgen, so your system needs a working Clang/libclang installation. See the rust-bindgen requirements.

Building

git clone https://github.com/Euraxluo/LKH-rs
cd LKH-rs
cargo build

For verbose platform diagnostics:

cargo build --vv

CLI usage

Run the included example parameter file:

cargo run --bin lkh -- --par source_code/pr2392.par

After installing the binary, use:

lkh --par source_code/pr2392.par

Rust API usage

use lkh_rs::{solve_problem, RoutingProblem, SearchParameters};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let problem = RoutingProblem::euclidean_2d([
        (0.0, 0.0),
        (0.0, 1.0),
        (1.0, 1.0),
        (1.0, 0.0),
    ])?;
    let report = solve_problem(&problem, &SearchParameters::new())?;
    println!("best cost: {}", report.best_cost);
    println!("tour length: {}", report.tour.len());
    Ok(())
}

Complete examples are available in examples/solve_programmatic.rs and examples/solve_parameter_file.rs.

Run them with:

cargo run --example solve_programmatic
cargo run --example solve_parameter_file -- source_code/pr2392.par

FastAPI JSON backend

A browser-friendly JSON backend is available in examples/fastapi_backend. It serves a small route visualizer and exposes POST /api/solve, where the frontend sends JSON problem data and receives a JSON solve report from the real lkh_rs Python package.

python -m venv /tmp/lkh-rs-api-venv
source /tmp/lkh-rs-api-venv/bin/activate
python -m pip install -r examples/fastapi_backend/requirements.txt
maturin develop
uvicorn app:app --app-dir examples/fastapi_backend --host 127.0.0.1 --port 8877

Then open http://127.0.0.1:8877/.

See docs/fastapi.md for the JSON payload shape.

Cargo features

Feature	Description
demo	Builds the lightweight C demo configuration.
unsafe-ffi	Exposes raw bindgen-generated LKH symbols under lkh_rs::ffi. Prefer the safe API when possible.
python	Enables the PyO3 module used by maturin.
wasm-experimental	Marks WebAssembly evaluation work; the full LKH backend is not yet browser-ready.

Python bindings

Build and install the Python extension locally with maturin:

python -m pip install maturin
maturin develop
python -c "import lkh_rs; print(lkh_rs.solve_parameter_file('tests/fixtures/tiny.par'))"

The Python package wraps the same safe Rust solver and returns a dictionary containing best_cost, best_penalty, runs, dimension, and tour.

See docs/python.md for details.

After maturin develop, run the Python programmatic example with:

python examples/python/solve_programmatic.py

Release

Pushes to main run the release workflow. When the package version in Cargo.toml and pyproject.toml has not been published yet, the workflow publishes:

• the Rust crate to crates.io using CARGO_REGISTRY_TOKEN in the crates.io environment;
• Python wheels for Linux, macOS, and Windows plus an sdist to PyPI using PyPI Trusted Publishing in the pypi environment.

See docs/release.md for the required repository environments and publishing credentials.

Programmatic API

LKH-rs also exposes an object-based API for callers that do not want to write TSPLIB and .par files by hand:

use lkh_rs::{solve_problem, RoutingProblem, SearchParameters};

let problem = RoutingProblem::euclidean_2d([
    (0.0, 0.0),
    (0.0, 1.0),
    (1.0, 1.0),
    (1.0, 0.0),
])?;
let report = solve_problem(&problem, &SearchParameters::new())?;
println!("{:?}", report.tour);
# Ok::<(), Box<dyn std::error::Error>>(())

The core model is generic over LKH problem types. Convenience builders such as euclidean_2d, distance_matrix, and asymmetric_distance_matrix are thin wrappers over the same RoutingProblem representation, while with_keyword and with_section allow callers to express CVRP, TSPTW, pickup-and-delivery, clustered, prize-collecting, or other LKH variants using their native TSPLIB/LKH fields:

use lkh_rs::{solve_problem, ProblemKind, RoutingProblem, SearchParameters};

let problem = RoutingProblem::named("tiny_cvrp", ProblemKind::Cvrp, 4)?
    .with_keyword("CAPACITY", "3")?
    .with_keyword("EDGE_WEIGHT_TYPE", "EXPLICIT")?
    .with_keyword("EDGE_WEIGHT_FORMAT", "FULL_MATRIX")?
    .with_section(
        "EDGE_WEIGHT_SECTION",
        ["0 1 1 2", "1 0 2 1", "1 2 0 1", "2 1 1 0"],
    )?
    .with_section("DEMAND_SECTION", ["1 0", "2 1", "3 1", "4 1"])?
    .with_section("DEPOT_SECTION", ["1", "-1"])?;

let report = solve_problem(&problem, &SearchParameters::new())?;
# Ok::<(), Box<dyn std::error::Error>>(())

Native solving renders the problem and parameter data in memory and feeds LKH's existing parser without creating temporary files. TSPLIB and LKH parameter text can still be rendered or written explicitly with to_tsplib, write_tsplib, to_lkh_parameter_file, and write_lkh_parameter_file when callers want files for compatibility, inspection, or debugging.

Safety model

The upstream LKH C library uses process-global mutable state and C error paths that can call exit(EXIT_FAILURE). LKH-rs serializes safe API calls with a global mutex and returns Result for Rust-side validation errors, but malformed inputs that reach deep C parsing may still terminate the process.

Use subprocess isolation for untrusted inputs or service workloads. See docs/safety.md.

Performance and browser integration

• docs/performance.md describes the current benchmark baseline and why safe parallelism should use multiple processes rather than multiple in-process threads.
• docs/fastapi.md describes the current browser integration path using FastAPI and JSON.
• docs/wasm.md records the WebAssembly evaluation and current blockers. Browser-ready Wasm deployment is not currently supported.

Roadmap

This project aims to provide full Rust bindings and practical integrations for LKH3.

Near Term Goals

• Complete cross-platform bindings for LKH using bindgen and cc-rs (#1)
• Implement an end-to-end demo app matching the LKH C demo (#2)
• Set up GitHub Actions for CI/CD across platforms (#3)
  • Build and test on Windows, Linux, macOS
  • Add crates.io publishing workflow scaffold
• Add documentation and examples (#4)
• Generate Python bindings using PyO3 with maturin (#5)

Longer Term Goals

• Explore safety improvements using Rust abstractions (#6)
  • Add a default safe parameter-file API around LKH's global C state
  • Return Result errors for Rust-side validation failures
  • Copy solver results into owned Rust structures
  • Gate raw pointer/global access behind the unsafe-ffi feature
  • Document remaining C-side safety limitations
• Expose more LKH functionality as safe Rust APIs and expose it to other languages like Python (#7)
• Optimize performance critical sections with Rust implementations (#8)
  • Add a benchmark baseline and performance roadmap
  • Document process-level parallelism as the safe path for concurrent solves
• Evaluate WebAssembly integration for web deployment (#9)

Overall, LKH-rs uses Rust language features to minimize the unsafe code that application users need to write, while still making the underlying LKH capabilities available for advanced integrations.

Contribution

We welcome bug reports, feature requests, and other contributions from the community.

Changelog

See CHANGELOG.md.