solve_tsp

m4opt.utils.optimization.solve_tsp(distances, **kwargs)

Solve the Traveling Salesman problem.

Parameters:

• distances (ndarray) – A square matrix of size (2, 2) or greater representing the distances between each pair of nodes.

• kwargs – Additional arguments passed to m4opt.milp.Model.

Returns:

• sequence – The indices that place the nodes in the order to visit, of length 1 greater than the rank of the distance matrix. The first and last value must be equal.

• length – The total path length of the tour.

Return type:

tuple[ndarray, float]

Notes

This uses the Miller-Tucker-Zemlin formulation.

Examples

from scipy.spatial.distance import pdist, squareform
import numpy as np
from matplotlib import pyplot as plt
from m4opt.utils.optimization import solve_tsp

# Construct a random cloud of points.
points = np.random.default_rng(1234).random((30, 2))

# Calculate the Euclidean distances between each pair of points.
dist = squareform(pdist(points))

# Find the shortest path, and the path length.
indices, path_length = solve_tsp(dist)

# Plot the points and the path.
ax = plt.axes(aspect=1, xlim=(0, 1), ylim=(0, 1))
ax.plot(*points[indices].T, "o-")

(Source code)