python - 2-Opt Algorithm for Traveling Salesman Problem

Question

I have created a solution for the multiple Traveling Salesman Problem (mTSP). My next goal is to implement a 2-opt algorithm from the existing solutions. Below is a snippet of my code:

for j in range(len(solutions[i].nodes)-3):
    for k in range(j+2, len(solutions[i].nodes)-1):
        dist_a = graph.edges[solutions[i].nodes[j], solutions[i].nodes[j + 1]]['weight']
        dist_b = graph.edges[solutions[i].nodes[k], solutions[i].nodes[k + 1]]['weight']
        dist_c = graph.edges[solutions[i].nodes[j], solutions[i].nodes[k]]['weight']
        dist_d = graph.edges[solutions[i].nodes[j + 1], solutions[i].nodes[k + 1]]['weight']
        
        if dist_a + dist_b > dist_c + dist_d:
            solutions[i].nodes[j + 1: k + 1] = reversed(solutions[i].nodes[j + 1: k + 1])
            solutions[i].cost += (dist_c + dist_d - dist_a - dist_b)
            solutions[i].path = []
            for l in range(x):
                solutions[i].path.append((solutions[i].nodes[l], solutions[i].nodes[(l + 1) % len(solutions[i].nodes)]))

This works well. But if I change the code a little bit to a higher integer subtraction, for example for j in range(len(solutions[i].nodes)-4), sometimes it will produce a lower cost solution than for j in range(len(solutions[i].nodes)-3). How could this happen? Can anyone explain it? Thanks in advance

Answer 1

等待大神答复