tsp-rs

Library for traveling salesman problem algorithms.

Example

Basic

For 2d point datasets:

use std::time;

use tsp_rs::Tour;
use tsp_rs::point::Point;

let tour: Vec<Point> = vec![
    Point::new(0., 0.),
    Point::new(0., 1.),
    Point::new(1., 0.),
    Point::new(1., 1.),
];

let mut tour = Tour::from(&tour);

tour.optimize_kopt(std::time::Duration::from_secs(1));

Using traits

Same as above, but instead of using tsp::point::Point, just implement the trait tsp::metrizable::Metrizable for your type T by defining a distance function between two T. Your type will also need Clone, Borrow, maybe another.. the compiler will remember.

Performance

Path::solve_kopt uses a 2-opt heuristic with 3-opt thrown in if it hits a wall for too long. Gets to within ~8% of the optimal solution for the b52 and ~10% of qa194 on average in a run of solve_nn + 1 second of optimization. The larger the problem, the longer you should allow for optimization.

For the constructive solution, Path::solve_nn, gets to within ~15% of the optimal solution on average.

Comments

Just for my own entertainment while learning rust, don't trust this but the implementation should be correct.