solve_tsp_with_2opt

mrinufft.trajectories.maths.tsp_solver.solve_tsp_with_2opt(locations, improvement_threshold=1e-08)

Solve the TSP problem using a 2-opt approach.

A sub-optimal solution to the Travelling Salesman Problem (TSP) is provided using the 2-opt approach in O(n²) where chunks of an initially random route are reversed, and selected if the total distance is reduced. As a result the route solution does not cross its own path in 2D.

Parameters:

• locations (array_like) – An array of N points with shape (N, D) with D the space dimension.

• improvement_threshold (float) – Threshold used as progress criterion to stop the optimization process.

Returns:

The new positions order of shape (N,).

Return type:

array_like