Tspf

Tspf is a library for parsing the TSPLIB file format, a text-based file format often used in the research field of travelling salesman problem (TSP), vehicle routing problem and other related problems. Some well-known TSP solvers (e.g. Concorde or LKH) work mainly with this file format as inputs.

The parser is implemented based on the documentation from the Department of Discrete and Combinatorial Optimization at Ruprecht-Karls-Universität Heidelberg.

The library can fully parse all problem datasets hosted on TSPLIB's website:

• TSP - symmetric travelling salesman problem
• HCP - Hamiltonian cycle problem
• ATSP - asymmetric travelling salesman problem
• SOP - sequential ordering problem
• CVRP - capacitated vehicle routing problem
• Tour - a collection of tours

Moreover, it also provides common metric functions to calculate edge weights (or cost/distance) between nodes in public interface. Among them are:

• 2D- and 3D-Euclidean distance
• 2D- and 3D-Manhattan distance
• Geographical distance

This is a sister project from cykl-rs, a heuristic solver for TSP, which is still under-development.

Usage

To parse an input string, we use the function parse_str from the struct TspBuilder:

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

On the other hand, the function parse_path handles the parsing from files:

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

NOTES:

• The files si175.tsp, si535.tsp, si1032.tsp from the TSP dataset require a small change: the type entry in the second line TYPE: TSP (M.~Hofmeister) is wrong according to the format definition. Instead, that line should simply be TYPE: TSP.
• For the HCP dataset, the file alb4000.hcp has a wrong entry in line 8005. The line should reads FIXED_EDGES_SECTION, instead FIXED_EDGES.

Datasets

The following list doesn't contain all test instance datasets used in academia. If you have any interesting datasets that are not included in the list, please let me know:

Name	Links	Note
TSPLIB Travelling salesman problem	[Website]	Optimal solution: [website]
TSPLIB Asymmetric travelling salesman problem	[Website]	Optimal solution: [website]
TSPLIB Hamiltonian cycle problem	[Website]
FHCP Hamiltonian cycle challenge set	[Website]
TSPLIB Sequential ordering problem	[Website]	Optimal solution: [website]
TSPLIB Capacitated vehicle routing problem	[Website]
Shortest tour to nearly every pub in UK	[Website] [Download]	Distance function not yet implemented
Orienteering problem	[Github]	Parser not yet implemented

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.