2-opt for TSP – Python

I have a problem with my 2-opt code to solve the Traveling Salesman Problem… I give a set of points [(x1,y1),…..,(xn,yn)].

Here is my code:

    def swap(i,j,S):
        a=min(i,j)
        b=max(i,j)
        A=S[a:b+1]
        A.reverse()
        S=S[:a]+A+S[b+1:]
        return(S)


   def opt_g_bis(S,n):
        S_bis=S[:]
        Mod=False
        for i in range(0,n-2):
            for j in  range(0,n-2) :
                if j != i-1 and j != i+1:
                    if norme(S_bis[i],S_bis[i+1])+norme(S_bis[j],S_bis[j+1])>norme(S_bis[i],S_bis[j])+norme(S_bis[i+1],S_bis[j+1]):
                        S_bis=swap(i+1,j+1,S_bis) 
                        Mod=True
            if norme(S_bis[i],S_bis[i+1])+norme(S_bis[n-1],S[0])>norme(S_bis[i],S_bis[n-1])+norme(S_bis[i+1],S_bis[0]):
                if n-1 != i+1 or 0 != i-1:
                    S_bis=swap(i+1,n-1,S_bis)
                    Mod=True
        return(Mod,S_bis)

    def opt_tot(S):
       S_bis=S[:]
       n=len(S)
       Mod=True
       while Mod==True:
            Mod=False
            S_bis=S[:]
            Mod,S=opt_g_bis(S_bis,n)
       return(cout_2(S),S)

I know my code is not optimal, but for now, it never ends….
The function norme calculates the distance between two points.
I have tried with a journey that is optimal and has no crosses, but it never ends…
Do you have an idea?

Thanks a lot,
Rémi


Source: python

Leave a Reply