Skip to main content

CI

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.

Metadata

Release files for lkh-rs 0.1.0

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for lkh-rs 0.1.0
File Size Uploaded Provenance Actions
lkh_rs-0.1.0.tar.gz 2.6 MB Without provenance Details for lkh_rs-0.1.0.tar.gz

Built distribution (wheel)

Table of built distributions (wheels) for lkh-rs 0.1.0
File Interpreter ABI Platform Actions
lkh_rs-0.1.0-cp38-abi3-macosx_11_0_arm64.whl CPython 3.8 abi3 macOS 11.0+ ARM64 Details for lkh_rs-0.1.0-cp38-abi3-macosx_11_0_arm64.whl

Total release size: 3.1 MB

Release files / lkh_rs-0.1.0.tar.gz

Download URL lkh_rs-0.1.0.tar.gz
Size 2.6 MB
Tags Source
SHA-256 checksum
How to use checksums
5145451a35ccef3f456e2083651bf0c8e64285a69139da51cf9a07c1e541e08c
BLAKE2b-256 checksum
How to use checksums
ca31c3b44a5faea578910d585b7def83e89b2cb4a44c4ba1326a649394236a26
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/6.2.0 CPython/3.14.5

Release files / lkh_rs-0.1.0-cp38-abi3-macosx_11_0_arm64.whl

Download URL lkh_rs-0.1.0-cp38-abi3-macosx_11_0_arm64.whl
Size 489.7 kB
Tags CPython 3.8 abi3 macOS 11.0+ ARM64
SHA-256 checksum
How to use checksums
13593818e6d0ca9fb3ade37e90db45280c1636e788236d5824e870cb0490656a
BLAKE2b-256 checksum
How to use checksums
ab93f1869c6818d40c484df97f0bac22d792474a0919155efb5d7fb9b197371c
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
No
Uploaded via twine/6.2.0 CPython/3.14.5

Security for lkh-rs 0.1.0

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

No provenance found

None of the files in this release were uploaded with provenance metadata.

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Release history Release notifications | RSS feed

This release

0.1.0 This release

2 release files No provenance

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page