有缺陷的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; 
}