traveling salesman problem, 2-opt algorithm c# implementation

Question

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

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;


namespace TSP
{
    internal static class Program
    {
        private 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();
        }


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


        private 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();
            }
        }


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

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

If the problem is euclidian distance and you want the cost of the solution produced by the algorithm is within 3/2 of the optimum then you want the Christofides algorithm. ACO and GA don't have a guaranteed cost.