有缺陷的2-opt搜索实现？

Question

我正在尝试为Java中的TSP设计2-opt本地搜索启发式，但我的算法似乎有缺陷。给定最近的邻居电路，它会以某种方式使电路变得更糟。最近的邻居：http://goo.gl/uI5X6; 10秒后2-opt：http://goo.gl/5AGJ1。我的代码如下。我的实现有什么问题？位置[]位置只是“图形”节点的列表，每个节点都与其他节点之间的纬度和经度以及距离计算。

public HamiltonianCircuit execute(Location[] locations) { 
    long startTime = System.currentTimeMillis(); 
    while (true) { 
     for (int i = 0; i < locations.length; i++) { 
      for (int k = 0; k < locations.length; k++) { 
       if (System.currentTimeMillis() - startTime >= 10000) { 
        return new HamiltonianCircuit(locations); 
       } 
       Location a = locations[i]; 
       Location b = locations[(i + 1) % locations.length]; 
       Location c = locations[k]; 
       Location d = locations[(k + 1) % locations.length]; 
       double distanceab = a.distanceBetween(b); 
       double distancecd = c.distanceBetween(d); 
       double distanceac = a.distanceBetween(c); 
       double distancebd = b.distanceBetween(d); 
       double change = (distanceab + distancecd) - 
        (distanceac + distancebd); 
       if (change > 0) { 
        locations[k] = a; 
        locations[i] = c; 
       } 
      } 
     } 
    } 
} 

Answer 1

2-OPT与替换边缘AB和CD，这意味着边缘AC和BD，如果我们有局部电路0 AB XYZ CD 1，开始时，我们希望0 AC ZYX BD 1，当我们”重做。
您的代码会生成0 C B x y z A D 1.

您想交换B和C，但也需要将中间的所有内容都撤消。

Answer 2

Java中的可能的解决办法是这样的：（注：详细）

public HamiltonianCircuit execute(){ 
ArrayList<Vehicle> locations= new ArrayList<Locations>; 
//populate array 

    for (int i = 1; i < locations.size()-3; i++) { 
      Location a = locations.get(i); 
      Location b = locations.get(i+1); 
      Location c = locations.get(i+2); 
      Location d = locations.get(i+3); 

      double distanceab = EuclidianDistance.pair(a, b); 
      double distancebd = EuclidianDistance.pair(b, d); 
      double distanceac = EuclidianDistance.pair(a, c); 
      double distancecd = EuclidianDistance.pair(c, d); 
      double abcd = distanceab+distancecd; 
      double acbd = distanceac+distancebd; 

      if(acbd<abcd){ 
       Collections.swap(locations, i+1, i+2); 
       System.out.println("swapped"+vehicles); 
      } 
    } 
    Locations.setDistance(EuclidianDistance.Collection(locations)); 
    return locations; 
}