PYME.Analysis.points.traveling_salesperson.two_opt module¶
- PYME.Analysis.points.traveling_salesperson.two_opt.calculate_path_length(distances, route)¶
- Parameters
- distances: ndarray
distance array, for which distances[i, j] is the distance from the ith to the jth point
- route: ndarray
array of indices defining the path
- PYME.Analysis.points.traveling_salesperson.two_opt.timeout_two_opt(distances, epsilon, timeout, initial_route=None)¶
Solves the traveling salesperson problem (TSP) using two-opt swaps to untangle a route.
- Parameters
- distances: ndarray
distance array, which distances[i, j] is the distance from the ith to the jth point
- epsilon: float
exit tolerance on relative improvement. 0.01 corresponds to 1%
- timeout: float
number of seconds to allow computation
- initial_route: ndarray
[optional] route to initialize search with. Note that the first position in the route is fixed, but all others may vary. If no route is provided, the initial route is the same order the distances array was constructed with.
- Returns
- route: ndarray
“solved” route
- best_distance: float
distance of the route
- og_distance: float
distance of the initial route.
Notes
see https://en.wikipedia.org/wiki/2-opt for pseudo code
- PYME.Analysis.points.traveling_salesperson.two_opt.two_opt(distances, epsilon, initial_route=None, fixed_endpoint=False)¶
Solves the traveling salesperson problem (TSP) using two-opt swaps to untangle a route.
- Parameters
- distances: ndarray
distance array, which distances[i, j] is the distance from the ith to the jth point
- epsilon: float
exit tolerence on relative improvement. 0.01 corresponds to 1%
- initial_route: ndarray
[optional] route to initialize search with. Note that the first position in the route is fixed, but all others may vary. If no route is provided, the initial route is the same order the distances array was constructed with.
- Returns
- route: ndarray
“solved” route
- best_distance: float
distance of the route
- og_distance: float
distance of the initial route.
Notes
see https://en.wikipedia.org/wiki/2-opt for pseudo code
- PYME.Analysis.points.traveling_salesperson.two_opt.two_opt_swap(route, i, k)¶
Take everything the same up to i, then reverse i:k, then take k: normally. Parameters ———- route: ndarray
Path to swap postions in
- i: int
first swap index
- k: int
second swap index
Returns¶
two-opt swapped route
Notes
Returns a copy. Temping to do something in place, e.g. route[i:k + 1] = route[k:i - 1: -1], but the algorithm seems to require a copy somewhere anyway, so might as well do it here.
- PYME.Analysis.points.traveling_salesperson.two_opt.two_opt_test(route, i, k, distances, k_max)¶
Test to see what distance change we’d get doing a two_opt_swap. Take everything the same up to i, then reverse i:k, then take k: normally.
- Parameters
- route: ndarray
Path to swap postions in
- i: int
first swap index
- k: int
second swap index
- distances: NxN matrix of float
distances between points
- k_max: pre-computed maximum value of k == distances.shape[0] -1
- Returns
- distance change on swap
Notes
There is a cythonized version in two_opt_utils which is considerably faster.