Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
2.4k views
in Technique[技术] by (71.8m points)

python - 2-Opt Algorithm for Traveling Salesman Problem

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


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)
等待大神答复

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...