tsp-rs
Library for traveling salesman problem algorithms.
Example
Basic
For 2d point datasets:
use time;
use Tour;
use Point;
let tour: = vec!;
let mut tour = from;
tour.optimize_kopt;
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.