fast-tsp

A fast local-search solver for the TSP (Travelling Salesman Problem), written in Rust with Python bindings. Give it a symmetric integer distance matrix and a time budget, and it returns a near-optimal tour: optimal on most TSPLIB instances below 1000 nodes within a second or two, and within a few tenths of a percent of the optimum on instances of several thousand nodes.

Documentation Status Pip Actions Status PyPI - Version License Issues

Quickstart

Install the module:

$ pip install fast-tsp

Create a distance matrix and run the solver:

import fast_tsp
dists = [
   [ 0, 63, 72, 70],
   [63,  0, 57, 53],
   [72, 57,  0,  4],
   [70, 53,  4,  0],
]
tour = fast_tsp.find_tour(dists)
print(tour)
# [0, 1, 3, 2]

The returned tour is the list of indices of the nodes in the order they are visited. find_tour takes a time budget (duration_seconds, default 2), a thread count (max_threads) and two tuning options; see Usage.

Contents