 # Traveling salesman is not returning to start(C#)

Hi everyone,

I tried to implement the TSP -2Opt algorithm, follwong these steps here : https://en.wikipedia.org/wiki/2-opt
it is working so far(no line crossings), its just not returning to te start position.

``````private void RunScript(List<Point3d> pts, int its, ref object A)
{
List<Point3d> existingRoute = new List<Point3d>(pts);

for (int it = 0; it < its; it++)
{
double bestDistance = getDistance(existingRoute);
for (int i = 1; i < existingRoute.Count - 1; i++)
{
for (int k = i + 1; k < existingRoute.Count; k++)
{
List<Point3d> newRoute = swap(existingRoute, i, k);//swap
double newDistance = getDistance(newRoute);
if(newDistance < bestDistance)
{
existingRoute = newRoute;
bestDistance = newDistance;
}
}
}
}
A = existingRoute;
}

public double getDistance (List<Point3d> pts)
{
double d = 0;
for (int i = 0; i < pts.Count - 1 ; i++)
{
double newDist = pts[i].DistanceTo(pts[i + 1]);
d += newDist;
}
return d;
}

public List<Point3d>  swap(List<Point3d> route, int i, int k)
{
var swapped = new List<Point3d>();
//1. take route to route[i-1] and add them in order to new_route
for (int c = 0; c < i - 1; c++)

// 2. take route[i] to route[k] and add them in reverse order to new_route
for ( int c = k; c-- > i - 1 ; )

// 3. take route[k+1] to end and add them in order to new_route
for ( int c = k; c < route.Count; c++ )

return swapped;
}
``````

Maybe someone sees the error.
Also any tips about optimizing are welcome.
File:20200614_TSP.gh (5.9 KB)
Thanks everybody!

``````private void RunScript(List<Point3d> pts, int its, ref object A)
{
var existingRoute = new Polyline(pts){pts};
for (var it = 0; it < its; it++)
{
var bestDistance = existingRoute.Length;
for (var i = 1; i < existingRoute.Count - 1; i++)
for (var k = i + 1; k < existingRoute.Count; k++)
{
var newRoute = swap(existingRoute, i, k);
var newDistance = newRoute.Length;
if (newDistance >= bestDistance) continue;
existingRoute = newRoute;
bestDistance = newDistance;
}
}
A = existingRoute;
}
Polyline swap(Polyline route, int i, int k)
{
var swapped = new Polyline();
//1. take route to route[i-1] and add them in order to new_route
for (int c = 0; c < i - 1; c++)
// 2. take route[i] to route[k] and add them in reverse order to new_route
for ( int c = k; c-- > i - 1 ; )
// 3. take route[k+1] to end and add them in order to new_route
for ( int c = k; c < route.Count; c++ )
return swapped;
}
``````

TSP.gh (4.9 KB)

1 Like

Nice!
Thanks a lot @Mahdiyar !

Here is a slightly faster version that uses Array.Reverse(Array, Int32, Int32):

``````private void RunScript(List<Point3d> pts, int n, ref object A)
{
var route = pts.ToArray();
var shortest = Length(route);
for (var k = 0; k < n; k++)
for (var i = 1; i < route.Length - 1; i++)
for (var j = i + 1; j < route.Length; j++)
route = Swap(route, ref shortest, i, j);
A = route;
}
double Length(Point3d[] route)
{
var d = 0.0;
for(var i = 0; i < route.Length - 1; i++)
d += route[i].DistanceTo(route[i + 1]);
return d;
}
Point3d[] Swap(Point3d[] route, ref double shortest, int i, int j)
{
var swapped = (Point3d[]) route.Clone();
Array.Reverse(swapped, i, j - i);
var len = Length(swapped);
if (len < shortest)
{
shortest = len;
return swapped;
}
return route;
}
``````

Python:

``````def length(pts):
d = 0.0
for i in range(len(pts) - 1):
d += pts[i].DistanceTo(pts[i + 1])
return d
def swap(route, shortest, i, j):
swapped = route[:i]+route[i:j][::-1]+route[j:]
len = length(swapped)
if len < shortest:
return swapped, len
return route, shortest

pts.append(pts)
route = pts
shortest = length(route)
for k in range(n):
for i in range(1, len(route) - 1):
for j in range(i+1, len(route)):
route, shortest = swap(route, shortest, i, j)
a = route
``````

TSP.gh (5.4 KB)

3 Likes

Hi @Mahdiyar,

thanks for this one!
It´s as twice as fast on my machine and also without duplicate points!

Thanks for the study material.

for k in range(n)… what does the variable “n” stand for?
thanks in advance! 