I'm trying to implement 2-opt optimization for finding "good enough" solutions to the TSP, with no edge crossings. I was under the impression running 2-opt until no more improvements can be made, will result in a tour with no crossings. However the below code isn't removing all crossed edges for some reason. In some runs with 1000's of cities there remain several crossings.

Code notes: \_solution is a List. Rather than creating a new tour and calculating the entire distance the code computes the difference between the two edges removed and the two edges created for speed. Also I duplicate the first point and add to the end of the list for making calculations simpler. Hence the i & j ranges.

Can anyone see why this isn't working?

```
        while (!done)
        {
            bool improved = false;

            for (int i = 1; i < _solution.Count - 2; i++)
            {
                OptimizeSteps++;

                for (int j = i + 1; j < _solution.Count - 1; j++)
                {
                    // calculate new tour distance 
                    double newDist = TourLength - CalcPointDistanceL2(_solution[i-1], _solution[i]);
                    newDist -= CalcPointDistanceL2(_solution[j], _solution[j + 1]);
                    newDist += CalcPointDistanceL2(_solution[i-1], _solution[j]);
                    newDist += CalcPointDistanceL2(_solution[i], _solution[j + 1]);

                    // if shorter make the improved tour
                    if (newDist < TourLength)
                    {
                        // reverse subtour
                        TSPPoint[] reversedSubTour = new TSPPoint[j-i+1];
                        _solution.CopyTo( i, reversedSubTour, 0, reversedSubTour.Length );
                        Array.Reverse( reversedSubTour );

                        for ( int n = 0; n < reversedSubTour.Length; n++ )
                        {
                            _solution[n + i] = reversedSubTour[n];
                        }
                        TourLength = newDist;

                        // debug
                        double d = GetTotalDistance(_solution);

                        improved = true;
                    }

                    if ( improved ) break;
                }

                DoNotify(500);

                if ( improved ) break;
            }
            if (!improved) done = true;
        }

```