traveling salesman problem, 2-opt algorithm c# implementation

Question

Hello Can someone give me a code sample of 2-opt algorithm for traveling salesman problem. For now im using nearest neighbour to find the path but this method is far from perfect, and after some research i found 2-opt algorithm that would correct that path to the acceptable level. I found some sample apps but without source code.

Answer 1

this is not in c# but it is a sample: SHORTEST PATH HEURISTICS (NEAREST NEIGHBORHOOD, 2 OPT, FARTHEST AND ARBITRARY INSERTION) FOR TRAVELLING SALESMAN PROBLEM

Answer 2

Well, your solution to TSP is always going to be far from perfect. No code, but here's how to go about 2-Opt. It's not too bad:

1. You need a class called Stop that has a Next, Prev, and City property, and probably a Stops property that just returns the array containing Next and Prev.
2. When you link them together, we'll call that a Tour. Tour has a Stop property (any of the stops will do), and an AllStops property, whose getter just walks the stops and returns them
3. You need a method that takes a tour and returns its cost. Let's call that Tour.Cost().
4. You need Tour.Clone(), which just walks the stops and clones them individually
5. You need a method that generates the set of tours with two edges switched. Call this Tour.PossibleMutations()
6. Start with your NN solution
7. Call PossibleMutations() on it
8. Call Cost() on all of them and take the one with the lowest result
9. Repeat until the cost doesn't go down

Answer 3

Have you thought about using A*? http://en.wikipedia.org/wiki/A*_search_algorithm

Answer 4

So I got bored and wrote it. It looks like it works, but I haven't tested it very thoroughly. It assumes triangle inequality, all edges exist, that sort of thing. It works largely like the answer I outlined. It prints each iteration; the last one is the 2-optimized one.

I'm sure it can be improved in a zillion ways.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TSP
{
    static class Program
    {
  static void Main(string[] args)
  {
   //create an initial tour out of nearest neighbors
   var stops = Enumerable.Range(1, 10)
    .Select(i => new Stop(new City(i)))
    .NearestNeighbors()
    .ToList();

   //create next pointers between them
   stops.Connect(true);

   //wrap in a tour object
   Tour startingTour = new Tour(stops);

   //the actual algorithm
   while (true)
   {
    Console.WriteLine(startingTour);
    var newTour = startingTour.GenerateMutations()
     .MinBy(tour => tour.Cost());
    if (newTour.Cost() < startingTour.Cost())
     startingTour = newTour;
    else break;
   }

   Console.ReadLine();
  }

  class City
  {
   private static Random rand = new Random();

   public City(int cityName)
   {
    X = rand.NextDouble() * 100;
    Y = rand.NextDouble() * 100;
    CityName = cityName;
   }

   public double X { get; private set; }
   public double Y { get; private set; }
   public int CityName { get; private set; }
  }

  class Stop
  {
   public Stop(City city)
   {
    City = city;
   }

   public Stop Next { get; set; }
   public City City { get; set; }

   public Stop Clone()
   {
    return new Stop(City);
   }

   public static double Distance(Stop first, Stop other)
   {
    return Math.Sqrt(Math.Pow(first.City.X - other.City.X, 2) + 
     Math.Pow(first.City.Y - other.City.Y, 2));
   }

   //list of nodes, including this one, that we can get to
   public IEnumerable<Stop> CanGetTo()
   {
    var current = this;
    while (true)
    {
     yield return current;
     current = current.Next;
     if (current == this)
      break;
    }
   }

   public override bool Equals(object obj)
   {
    return City == ((Stop)obj).City;
   }

   public override int GetHashCode()
   {
    return City.GetHashCode();
   }

   public override string ToString()
   {
    return City.CityName.ToString();
   }
  }

  class Tour
  {
   public Tour(IEnumerable<Stop> stops)
   {
    Anchor = stops.First();
   }

   //the set of tours we can make with 2-opt out of this one
   public IEnumerable<Tour> GenerateMutations()
   {
    for (Stop stop = Anchor; stop.Next != Anchor; stop = stop.Next)
    {
     //skip the next one, since you can't swap with that
     Stop current = stop.Next.Next;
     while (current != Anchor)
     {
      yield return CloneWithSwap(stop.City, current.City);
      current = current.Next;
     }
    }
   }

   public Stop Anchor { get; set; }

   public Tour CloneWithSwap(City firstCity, City secondCity)
   {
    Stop firstFrom = null, secondFrom = null;
    var stops = UnconnectedClones();
    stops.Connect(true);

    foreach (Stop stop in stops)
    {
     if (stop.City == firstCity)
      firstFrom = stop;

     if (stop.City == secondCity)
      secondFrom = stop;
    }

    //the swap part
    var firstTo = firstFrom.Next;
    var secondTo = secondFrom.Next;

    //reverse all of the links between the swaps
    firstTo.CanGetTo()
     .TakeWhile(stop => stop != secondTo)
     .Reverse()
     .Connect(false);

    firstTo.Next = secondTo;
    firstFrom.Next = secondFrom;

    var tour = new Tour(stops);
    return tour;
   }

   public IList<Stop> UnconnectedClones()
   {
    return Cycle().Select(stop => stop.Clone()).ToList();
   }

   public double Cost()
   {
    return Cycle().Aggregate(0.0, (sum, stop) => 
     sum + Stop.Distance(stop, stop.Next));
   }

   private IEnumerable<Stop> Cycle()
   {
    return Anchor.CanGetTo();
   }

   public override string ToString()
   {
    string path = String.Join("->", 
     Cycle().Select(stop => stop.ToString()).ToArray());
    return String.Format("Cost: {0}, Path:{1}", Cost(), path);
   }

  }

  //take an ordered list of nodes and set their next properties
  static void Connect(this IEnumerable<Stop> stops, bool loop)
  {
   Stop prev = null, first = null;
   foreach (var stop in stops)
   {
    if (first == null)
     first = stop;
    if (prev != null)
     prev.Next = stop;
    prev = stop;
   }

   if (loop)
   {
    prev.Next = first;
   }
  }

  //T with the smallest func(T)
  static T MinBy<T, TComparable>(this IEnumerable<T> xs, 
                                                Func<T, TComparable> func) 
   where TComparable : IComparable<TComparable>
  {
   return xs.DefaultIfEmpty().Aggregate((maxSoFar, elem) => 
    func(elem).CompareTo(func(maxSoFar)) > 0 ? maxSoFar : elem);
  }

  //return an ordered nearest neighbor set
  static IEnumerable<Stop> NearestNeighbors(this IEnumerable<Stop> stops)
  {
   var stopsLeft = stops.ToList();
   for (var stop = stopsLeft.First(); 
    stop != null; 
    stop = stopsLeft.MinBy(s => Stop.Distance(stop, s)))
   {
    stopsLeft.Remove(stop);
    yield return stop;
   }
  }
    }
}