Generate all neighbors for 2OPT in python

Question

I am trying to implement to the 2opt optimization algorithm for the undirected Traveling Salesman Problem. For given cities:

cities = [[ 72.06557466,   5.73765812],
   [ 94.50272578,  68.95162393],
   [ 58.53952609,  15.12518299],
   [ 94.64599891,  34.65906808],
   [ 62.42311036,  45.8430048 ],
   [ 24.73697454,   4.4159545 ],
   [ 15.71071819,  81.27575127],
   [ 65.65743227,  54.90239983],
   [  5.07828178,  47.34845887],
   [ 88.98592652,  48.14959719]]

My understanding for the general algorithm is that starting from a random tour (in this example 10 nodes):

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

I need to generate all the 2opt neighbors for this solution (by removing two edges and introducing two new edges). Then, compute the cost for each such neighboring solution.

def total_length( nodes, solution ):
    objective = distance( solution[-1], solution[0])
    for index in range(0, len(solution)-1):
        objective += distance(solution[index], solution[index+1])
    return objective

Where the distance function is the Euclidian distance between the two points.

Then choosing the best (lowest cost). For example, this neighboring tour:

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

What would be an easy-way in python to iterate over all the neighboring tours (avoiding redundancy) for a given solution?

score 1 · Accepted Answer · answered Nov 17 '15 at 13:58

You don't need to iterate over all tours (I'm not sure what you mean by "neighboring tours"); you need to iterate over all pairs of edges in the existing tour. Since you have stored the tour as a sequence of nodes, you just need to iterate through the nodes, something like:

for i in range(0, len(solution)-3):
    for j in range(i+2, len(solution)-1):
        # evaluate 2-opt on edge (solution[i],solution[i+1]) and 
        # edge (solution[j],solution[j+1])

Note that the two edges can't share a node, which is why the j loop starts at i+2. Also note that (solution[j],solution[j+1]) should be interpreted as (solution[j],solution[0]) when j = =len(solution)-1.

Generate all neighbors for 2OPT in python

1 Answers1

Linked