Function define part

dist[source]

dist(p1, p2)

calculate the distance between two waypoints. Args: p1 : point's (x,y) position. p2 : point's (x,y) position. Returns: distance between two points.

distanceGenerate[source]

distanceGenerate(point_set)

generate a distance matrix based on the waypoints. Args: point_set : a set that contains all waypoint. Returns: a square matrix, which shows the distance between pairs of waypoint.

sortWaypoint[source]

sortWaypoint(permutation, point_set)

accoriding to permutation calculated by tsp solver, return new set of waypoint which is sorted. Args: permutation : the order of waypoints calculated by tsp solver. point_set : a set that contains all waypoint. Returns: new set of waypoint which is sorted.

solve_tsp_nearest_neighbor[source]

solve_tsp_nearest_neighbor(distance_matrix)

calculate tsp problem based on nearest neighbor, an algorithm that solves tsp using greedy assumption. Args: distance_matrix : a square matrix, which shows the distance between pairs of waypoint. Returns: A tuple, (path, cost) cost : optimal cost of tsp path : a orderd list of waypoint index based on distance matrix.

solve_tsp_held_karp[source]

solve_tsp_held_karp(distance_matrix)

calculate tsp problem based on Held-Karp, an algorithm that solves tsp using dynamic programming with memoization. Args: distance_matrix : a square matrix, which shows the distance between pairs of waypoint. Returns: A tuple, (path, cost) cost : optimal cost of tsp path : a orderd list of waypoint index based on distance matrix.

Testing example

we will move to 'data' directory to start all examples, this directory have been added to '.gitignoe' , so is convenient to test in local and light in cloud

cd data

/home/arg/arg_robotics_tools/data

Example task

we set a list that contains 11 waypoint(the first one is the starting point)

point_set = [
    [0, 0],
    [-13, 10],
    [-7, 6],
    [-1, 20],
    [3, 15],
    [10, 18],
    [13, 14],
    [16, 10],
    [24, 14],
    [25, 17],
    [33, 8]
]

Generate distance matrix

generate distance matrix for tsp_solver

distance_matrix = distanceGenerate(point_set)
print(distance_matrix)

Solve tsp

here display three ways to solve tsp

• Held Karp alogrithm(dynamic programming)
• simulated annealing alogrithm(heuristics alogrithm)
• nearest neighbor alogrithm(greedy alogrithm)

permutation_hk, distance_hk = solve_tsp_held_karp(distance_matrix)
result_hk = sortWaypoint(permutation_hk, point_set)

permutation_sa, distance_sa = solve_tsp_simulated_annealing(distance_matrix)
result_sa = sortWaypoint(permutation_sa, point_set)

permutation_nn, distance_nn = solve_tsp_nearest_neighbor(distance_matrix)
result_nn = sortWaypoint(permutation_nn, point_set)

Show result

print(permutation_hk)
print(distance_hk)
print(result_hk)

[0, 7, 10, 9, 8, 6, 5, 4, 3, 1, 2]

print(permutation_sa)
print(distance_sa)
print(result_sa)

print(permutation_nn)
print(distance_nn)
print(result_nn)