#tsp #salesman #lkh #atsp

elkai-rs

elkai-rs is a rust library for solving travelling salesman problems (TSP) based on elkai (LKH 3)

8 releases

0.1.7 Jul 31, 2024
0.1.6 Jul 20, 2024
0.1.3 Feb 14, 2024

#2 in #tsp

Custom license

1MB
20K SLoC

C 20K SLoC // 0.2% comments Rust 209 SLoC // 0.0% comments

elkai-rs - a Rust library for solving TSP problems

crates.io docs repo


Installation

[dependencies]
elkai-rs = "0.1.7"

Example usage

use std::collections::HashMap;
use elkai_rs::Coordinates2D;

fn main() {
    let cities = Coordinates2D::new(HashMap::from_iter([
        ("city1", (0.0, 0.0)),
        ("city2", (0.0, 4.0)),
        ("city3", (5.0, 0.0))
    ]));
    println!("{:?}", cities.solve(10));
}
use elkai_rs::DistanceMatrix;

fn main() {
    let cities = DistanceMatrix::new(vec![
        vec![0, 4, 0],
        vec![0, 0, 5],
        vec![0, 0, 0]
    ]);
    println!("{:?}", cities.solve(10));
}

License

The LKH native code by Helsgaun is released for non-commercial use only. Therefore the same restriction applies to elkai-rs, which is explained in the LICENSE file.

How it works internally

  • We link the C api of elkai to Rust with cc-rs.

⚠️ elkai-rs takes a global mutex (just like what elkai did) during the solving phase which means two threads cannot solve problems at the same time. If you want to run other workloads at the same time, you have to run another process.

Dependencies