2-opt

import random


random.seed(213)
d = []

length_of_instance = 10

for i in range(length_of_instance):
    d.append([])
    for _i in range(length_of_instance):
        if i != _i: d[i].append(random.randint(1, 2000));
        else: d[i].append(0)
print("Current distance matrix")
print(d)

route = [j for j in range(length_of_instance)]
random.shuffle(route)

def route_cost(rout):
    total_dist = d[rout[0]][rout[-1]]
    for i in range(len(rout)-1):
        total_dist+= d[rout[i]][rout[i+1]]
    return total_dist

print(f'For route before opt-2: {route} the total cost equals to {route_cost(route)}')

def opt_2_shift(rout, A, C):
    midpath = rout[A+1:C]
    midpath.reverse()
    return rout[:A+1] + midpath + rout[C:]


for i in range(length_of_instance):
    for j in range(i,length_of_instance):
        new_route = opt_2_shift(route,i,j)
        if route_cost(new_route)< route_cost(route):
            route = new_route

print(f'For route after initial round of opt-2: {route} the total cost equals to {route_cost(route)}')