旅行推销员 2-opt 代码留下交叉边

Question

我正在尝试实施 2-opt 优化以找到 TSP 的 "good enough" 解决方案，没有边缘交叉。我的印象是运行 2-opt 直到无法进行更多改进，才会导致没有交叉路口的游览。但是，由于某种原因，下面的代码并没有删除所有的交叉边。在一些有 1000 个城市的跑步中，仍然有几个十字路口。

代码说明：_solution 是一个列表。代码不是创建新的游览并计算整个距离，而是计算移除的两条边与为速度创建的两条边之间的差异。我还复制了第一点并添加到列表的末尾以使计算更简单。因此 i 和 j 范围。

谁能看出为什么这不起作用？

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

Answer 1

你是对的，在完成 2-opt 过程后（即，在执行所有导致较短游览的 2-opts 之后），游览不应自行交叉。

您当前的代码忽略 "j+1" = 起始节点的移动。您的 for j 循环应该进一步进行一次迭代：

for (int j = i + 1; j < _solution.Count; j++)

如果 j == _solution.Count-1，则不应使用 _solution[j + 1] 作为您的 j+1 节点，而应使用 _solution[0]。

Answer 2

您用于改进游览的代码是否正确处理了最后的重复节点？如果重复节点是正在交换的边之一的端点，我认为您没有正确调整起始节点——如果节点 0 是交换边的端点，也是一样。

旅行推销员 2-opt 代码留下交叉边

Travelling salesman 2-opt code leaving crossed edges

c#

optimization

traveling-salesman