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);
    existingRoute.Add(pts[0]);


    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;
  }

  // <Custom additional code> 
  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[0] to route[i-1] and add them in order to new_route
    for (int c = 0; c < i - 1; c++)
      swapped.Add(route[c]);

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

    // 3. take route[k+1] to end and add them in order to new_route
    for ( int c = k; c < route.Count; c++ )
      swapped.Add(route[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[0]};
  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;
}
// <Custom additional code> 
Polyline swap(Polyline route, int i, int k)
{
  var swapped = new Polyline();
  //1. take route[0] to route[i-1] and add them in order to new_route
  for (int c = 0; c < i - 1; c++)
    swapped.Add(route[c]);
   // 2. take route[i] to route[k] and add them in reverse order to new_route
  for ( int c = k; c-- > i - 1 ; )
    swapped.Add(route[c]);
   // 3. take route[k+1] to end and add them in order to new_route
  for ( int c = k; c < route.Count; c++ )
    swapped.Add(route[c]);
  swapped.Add(swapped[0]);
  return swapped;
}
// </Custom additional code> 

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)
{
  pts.Add(pts[0]);
  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;
}
// <Custom additional code> 
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;
}
// </Custom additional code> 

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[0])
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! :slight_smile: