Lib.rs

elkai-rs - 解决 TSP 问题的 Rust 库

• 基于 fikisipi 的 elkai (Keld Helsgaun 的 LKH)：已证明 N=315 以上的最优解，比 Google 的 OR 工具更准确
• 支持非对称和对称 旅行商问题
• 简洁简单的 API：一行代码即可获得结果

安装

[dependencies]
elkai-rs = "0.1.7"

示例用法

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));
}

许可协议

Helsgaun 的 LKH 原生代码仅限非商业用途发布。因此，elkai-rs 也适用同样的限制，这在 LICENSE 文件中有解释。

内部工作原理

• 我们使用 cc-rs 将 elkai 的 C API 连接到 Rust。

⚠️ elkai-rs 在解决阶段会使用 全局互斥锁（与 elkai 一样），这意味着不能同时有两个线程解决问题。如果您想同时运行其他工作负载，您必须运行另一个进程。