tskf

tskf 是一个用于解析 TSPLIB 文件格式的库，TSPLIB 是一种基于文本的文件格式，常用于旅行商问题（TSP）、车辆路径问题和其他相关问题的研究领域。一些著名的 TSP 求解器（例如 Concorde 或 LKH）主要使用此文件格式作为输入。

该解析器基于海德堡鲁佩雷特-卡尔大学离散与组合优化系的 文档 实现。

该库可以完全解析 TSPLIB 网站上托管的全部问题数据集。

• TSP - 对称旅行商问题
• HCP - 汉密尔顿回路问题
• ATSP - 非对称旅行商问题
• SOP - 顺序排序问题
• CVRP - 容量车辆路径问题
• Tour - 一系列旅行

此外，它还提供了公共接口中计算节点之间边权重（或成本/距离）的常用度量函数。其中包含

• 2D 和 3D 欧几里得距离
• 2D 和 3D 曼哈顿距离
• 地理距离

这是来自 cykl-rs 的姐妹项目，cykl-rs 是一个 TSP 的启发式求解器，目前仍在开发中。

用法

要解析一个输入字符串，我们使用结构 TspBuilder 中的函数 parse_str

use tspf;

match TspBuilder::parse_str("some input string") {
    Ok(tsp) => {
        // tsp is an instance of struct Tsp.
        // From tsp, one can access all data.
    }
    Err(e) => eprint!("{:?}", e),
}

另一方面，函数 parse_path 用于处理文件解析

use std::path::Path;
use tspf;

let path = ;
match TspBuilder::parse_path(Path::new("path/to/some_file.tsp")) {
    Ok(tsp) => {
        // tsp is an instance of struct Tsp.
        // From tsp, one can access all data.
    }
    Err(e) => eprint!("{:?}", e),
}

注意:

• 来自 TSP 数据集的文件 si175.tsp、si535.tsp、si1032.tsp 需要一个小改动：第二行中的类型条目 TYPE: TSP (M.~Hofmeister) 根据格式定义是错误的。相反，该行应该是简单的 TYPE: TSP。
• 对于HCP数据集，文件alb4000.hcp在第8005行有一个错误。这一行应该读取为FIXED_EDGES_SECTION，而不是FIXED_EDGES。

数据集

以下列表并不包含所有在学术界使用的测试实例数据集。如果您有任何未包含在列表中的有趣数据集，请告知我。

许可证

许可以下任何一种

• Apache License，版本2.0（《LICENSE-APACHE》或http://www.apache.org/licenses/LICENSE-2.0）
• MIT许可证（《LICENSE-MIT》或http://opensource.org/licenses/MIT）

由您选择。

贡献

除非您明确声明，否则根据Apache-2.0许可证定义的，任何有意提交以包含在您的工作中的贡献，将按照上述方式双许可，不附加任何额外条款或条件。